Halmazrendszerek geometriája/Halmazrendszerek és hipergráfok

• Témák jegyzéke
• Előző fejezet (Halmazrendszerek geometriája)
• Következő fejezet (Hipergráfok izomorfiája)

Bevezetés

A halmazrendszerek, ill. hipergráfok fogalmát a huszadik század hatvanas éveiben vezették be kombinatorikával foglalkozó matematikusok. Elméletük (amint erre már a „hipergráf” név is utal) a gráfelmélet továbbfejlesztése, ezért nyugodtan mondhatjuk, hogy a hipergráf fogalma is részben a geometriában gyökerezik . Egy U halmaz, néhány részhalmaza (piros); és egy ${\mbox{ }}_{\color {Blue}{\mathcal {H}}}$ hipergráf (kék). A fenti szemléltető képen pl. az U részhalmazai mint szabálytalan síkidomok jelennek meg, egy U feletti hipergráf pedig mint ezek egy halmaza, szintén szabálytalan síkidommal van szemléltetve (Venn-diagramm). A gráfelmélethez sokkal közelebb álló szemlélet lenne, ha a részhalmazokat síkgörbékkel próbálnánk szemléltetni, összekötve az egy részhalmazba tartozó elemeket egy folytonos vonallal.

A hipergráfelmélet az ún. francia ill. magyar kombinatorikai iskolák működésének köszönhető, magát a „hipergráf” szót az új fogalom elnevezésére Claude Berge (1926 – 2002) francia kombinatorikaprofesszor javasolta egy tihanyi matematikustalálkozón (Tihany Colloquium) 1966-ban, és ő írta később a témakör (halmazrendszerek kombinatorikája) első nagyobb összefoglaló műveit is . Az első hipergráfelméleti dolgozat, amely használta is a terminust, Erdős Pál és Hajnal András On the chromatic number of graphs and set systems c. 1966-os munkája (Gráfok és halmazrendszerek kromatikus számáról).

Véges halmazok leírására használatos néhány fogalom

Mindenekelőtt vezessünk be pár fogalmat és jelölést, ami nagyon megkönnyíti a véges halmazokról való beszédet.

Diszkrét intervallumok

Definíció:
Az {0,1,2,...,n} halmazra, ahol n∈N, alkalmazni fogjuk a 0,n jelölést. Rekurzív definícióval: 0,0 := {0} és ha n∈N⁺, akkor 0,n := 1,n-1∪{n} .

Definiálható még a következő is:

1,n := 0,n \ {0} .

Tehát például 0,5 := {0, 1, 2, 3, 4, 5} és 1,5 := {1, 2, 3, 4, 5}.

---

⍰ Gyakorló feladatok:

1. Fejezzük az alábbi halmazokat diszkrét intervallumok és véges sok halmazműveleti jel (unió, metszet, különbség) segítségével (N használata is megengedett):
   1. {2, 3, 4, 5, 6, ...}
   2. {10, 11, 12, ..., 20}
   3. {2, 4, 6, 8, 10, 12}
2. Bizonyítsuk be indukcióval, hogy 0,n⊆0,m akkor és csak akkor teljesül, ha n≤m.

Sorbarendezések

Definíció:
Ha n∈N természetes szám, akkor egy ν:1,n→U alakú bijektív függvényt az U egy sorbarendezésének nevezünk. Az ilyenek száma egyébként n! = 1·2·3·...·(n-1)·n.

Egy halmazt sorbarendezhetőnek vagy végesnek mondunk, ha létezik sorbarendezése.

Halmazelméletileg a sorbarendezés egy, a 1,n-ból az U-ba képező függvény, vagyis az 1,n×U halmaz egy speciális ν részhalmaza, (n,u) alakú párok olyan halmaza, amelyre n∈1,n és u∈U, továbbá:

1. minden n elemhez van olyan u, hogy (n,u)∈ν
2. de másik ilyen u' már nincs, azaz ha (n,u),(n,u')∈ν akor u = u'; (e két tulajdonság adja ν függvénységét);
3. minden u-hoz van olyan n, hogy (n,u)∈ν (szürjektivitás);
4. de másik ilyen n' már nincs, azaz ha (n,u),(n',u)∈ν, akkor n = n'.

Lásd még a Fogalommutatót.

Példák:

---

---

Megjegyzés: Nem minden halmaznak létezik sorbarendezése. Nyilvánvaló, hogy csakis a véges halmazok sorbarendezhetőek, azok mindegyike, a végtelen halmazoknak viszont egyike sem.

Egy tetszőleges halmaz ún. számosságát |U| jelöli a következőkben (két halmaz számossága azonos, ha található köztük kölcsönösen egyértelmű, bijektív leképezés ). Ha U véges, akkor |U| egyszerűen az elemeinek a száma. Egy halmazt akkor nevezünk végesnek, ha van olyan n∈N, hogy a halmaz kölcsönösen egyértelműen leképezhető legyen az 1,n diszkrét intervallumra, azaz ha sorbarendezhető.

A sorbarendezéseket gyakran írjuk a következő rövid alakba:

( ν(1) ν(2) ... ν(n) )

tehát zárójelek közé egy egysoros választójelek nélküli táblázatot írunk, úgy hogy az első helyre az 1 képe, ... i-edik helyre az i∈1,n képe, ... n-edik helyre az n elem képe kerüljön. Pl. az U = {a, b, c, d} halmaz azon μ sorbarendezését, amelyre μ(1) = c, μ(2) = b, μ(3) = d, μ(4) = a, röviden (cbda) jelöli. Ha a halmazelemek nevei tüöbb betűből állnak, szóközzel vagy vesszővel elválaszthatóak: (c b d a).

Részhalmaz, hatványhalmaz

Részhalmaz karakterisztikus függvénye

Definíció:
Legyen U tetszőleges halmaz, és R⊆U; ekkor az $\chi _{_{R}}\left(u\right):U\rightarrow \left\{0,1\right\};\ \ \chi \left(u\right):={\begin{cases}0,&{\mbox{ha }}u\not \in R;\\1,&{\mbox{ha }}u\in R\end{cases}}$

előírással értelmezett függvényt az R részhalmaz U feletti karakterisztikus függvényének nevezzük.

Formulamentes nyelven arról van szó, hogy az összes U-beli elemre értelmezzük a karakterisztikus függvényt, és ennek értéke 1, ha az illető elem eleme az R részhalmaznak, 0 pedig, ha nem eleme. Ha az 1-et az „igazságot”, a 0-t pedig a „hamisságot” kifejező szimbólumoknak gondoljuk, akkor azt mondhatjuk, hogy a karakterisztikus függvény a „benne van-e egy elem az adott részhalmazban” kérdésre felel igennel vagy nemmel.

A H₀(x) Heaviside-függvény grafikonja

Példák (karakterisztikus függvényekre):

---

1. Tetszőleges U halmazban az üres halmaz karakterisztikus függvénye azonosan nulla, a teljes U halmazé pedig azonosan egy.
2. Az ún H₀(x) módosított Heaviside-függvény a pozitív számok részhalmazának karakterisztikius függvénye a valós számok felett.
3. Az ún Dirichlet-függvény a racionális számok részhalmazának karakterisztikius függvénye a valós számok felett.

⍰ Gyakorló feladat: Bizonyítsuk, hogy ha egy halmaz hatványhalmazának minden eleméhez hozzárendeljük a halmaz felett értelmezett karakterisztikus függvényét, akkor egy bijektív leképezést kapunk! Megoldás: coming soon hopely.

Részhalmaz karakterisztikus vektora

A karakterisztikus függvényeket gyakran írjuk sorvektor alakjába. Ezt úgy tehetjük meg, ha rögzítjük az U halmaz egy ún. sorbarendezését, azaz egy ν: 1,n→U függvényt. Ezután az R⊆U-hoz készítünk egy n-elemű κ_U,ν(R) sorvektort (avagy rendezett n-est avagy n-dimenziós sorvektort), amely a következőképp néz ki:

κ_U,ν(R) := ( χ_R(ν(n)), χ_R(ν(n-1)), ..., χ_R(ν(2)), χ_R(ν(1)) ) ahol i∈1,n.

avagy:

[κ_U,ν(R)]_n+1-i := χ_R(ν(i)), ahol i∈1,n.

⍰ Gyakorló feladat: Írjuk fel az U = {a,b,c,d} halmaz összes részhalmazainak karakterisztikus vektorait, ha a sorbarendezés (d, b, a, c}! Megoldás ...

Hatványhalmaz

Definíció:
Legyen U tetszőleges halmaz.
℘(U)   -val
fogjuk jelölni az U halmaz összes részhalmazai halmazát, azaz hatványhalmazát. Tehát ℘(U) := { R | R⊆U )

Következésképp:

R⊆U    ⇔    R∈℘(U).

Ha E olyan halmaz, amelyre E⊆℘(U), azt tehát az új jelöléssel úgy is leírhatjuk, hogy E∈℘(℘(U)); és mindkét formális jelsor pontosan ugyanazt jelenti, hogy E-nek minden eleme az U egy részhalmaza.

Példák:

---

---

A karakterisztikus függvény erejének demonstrálására bizonyítunk egy jól ismert kombinatorikai tételt.

Tétel:

---

Legyenek U tetszőleges véges halmaz, ekkor részhalmazainak száma 2-nek |U| kitevőjű hatványa. Röviden:

|℘(U)| = ${\mbox{ }}^{2^{|U|}}$

Bizonyítás:

---

Az alapvető trükk az lesz, hogy nem a részhalmazokat, hanem a karakterisztikus függvényeket számoljuk meg (ami persze ugyanaz), ráadásul nem tízes, hanem kettes számrendszerbeli számokkal fogunk számlálni. Egy karakterisztikus függvényt úgy kapunk, hogy minden U-beli elemhez hozzárendeljük a 0 és 1 értékek egyikét. Rendezzük sorba az U elemeit, azaz tekintsünk valamely s(u): {1,2,..., |U|}→U kölcsönösen egyértelmű (bijektív) függvényt (ilyen természetesen létezik, hiszen U nyilván azonos számosságú az {1,2,...,|U|} halmazzal). Ha R az U bármely részhalmaza, tekintsük a következő számokat:

m(R) = 2⁰·χ_R(s(1))+2¹·χ_R(s(2))+...+2^|U|-1·χ_R(s(|U|)).

Az m(R) függvény tehát a ℘(U) halmazból N-be képez. Ennél többet is tudunk mondani. Minthogy minden j∈1,|U| indexre χ_R(s(1)) vagy nulla, vagy 1, ezért az összes m(R) szám tekinthető kettes számrendszerbeli számnak. A legkisebb köztük az azonosan 0 karakterisztikus függvényű R=∅ üres részhalmazhoz tartozó, a legnagyobb pedig nyilván az azonosan 1 karakterisztikus függvényű U univerzális részhalmazhoz tartozó szám. Tehát az m(R) függvény Ran(m(R)) értékkészletére: Ran(m(R))⊆0, A, ahol

${\mbox{ }}_{A=\underbrace {{\mbox{ }}_{11\cdots 1_{(2)}}} _{n\ db.1-es}}$ = 2⁰+2¹+...+2^|U|-1.

Ez az A szám épp 2^|U|-1. Ezt vagy úgy látjuk be, hogy alkalmazzuk a mértani sorozat összegképletét, vagy ha ezt nem ismerjük, meggondolhatjuk, hogy az A után melyik szám következik a kettes számrendszerben: minden helyiértéken egyes áll, tehát új helyiértéket kell „nyitnunk” egy egyesnek az A elé írásával (ez pedig épp a 2^|U|), és az ezt tartalmazó számok között pedig az a legkisebb, amelyiknek minden további helyiértékén 0 áll, tehát az A összes egyesét nullára kell változtatnuk. Azaz az A-ra következő szám épp ${\mbox{ }}_{\underbrace {{\mbox{ }}_{100\cdots 0_{(2)}}} _{n\ db.0}}$ = 2^|U|, maga az A meg ennél eggyel kisebb, tehát 2^|U|-1.

A következő lépés meggondolni, hogy az m(R): ℘(U)→0, A, azaz m(R): ℘(U)→0, 2^|U|-1 függvény bijektív. Valóban, ha két R részhalmazhoz ugyanazt az m(R) számot lehetne rendelni, akkor a j-edik helyiértéken (az összes j indexre) egyszerre áll 0 avagy 1 mindkét m számban, ami azt jelenti, a karakterisztikus függvények értékei megegyeznek, vagyis bármely u_beli elem egyszerre eleme vagy nem eleme a két részhalmaznak, azaz a két részhalmaz egyenlő. Eszerint az m(R) leképezés injektív. Szürjektív is, mert ha felírunk egy, az {0,1,2,...,A} halmazbeli m számot a kettes számrendszerben, akkor a j-1-edik helyen álló alaki értéket az s(j) elem karakterisztikus függvényének tekinthetjük, azaz az

R(m) := {x∈U | Az s^-1(u)+1 = m helyiértéken 1 áll}

halmaz az R(m) definíciójából következően részhalmaza U-nak.

Ezért m(R) bijektív leképezése az U részhalmazai halmazának a 0,2^|U|-1 halmazra, azaz

|℘(U)| = |0,2^|U|-1| = (2^|U|-1)+1 = 2^|U|.

☑

---

Megjegyzés: Az iménti bizonyítás az adott tételhez elképzelhető leghosszadalmasabb bizonyítások egyike, annak ellenére, hogy nagyon egyszerű, elemi alapgondolatokra épül. A benne felhasznált megszámolásos módszer (az m(R) függvény bevezetése) azonban igen hasznos eszköz a kombinatorikában, más problémákra is alkalmazható, azonkívül egy lentebbi fogalom definíciójához felhasználjuk majd.

⍰ Gyakorló feladat: Bizonyítsuk, hogy ha egy halmaz hatványhalmazának minden eleméhez hozzárendeljük a halmaz felett értelmezett karakterisztikus függvényét, akkor egy bijektív leképezést kapunk! Megoldás: coming soon hopely.

Halmazrendszerek avagy hipergráfok

Halmazrendszer, hipergráf

Definíció:
Legyen U tetszőleges halmaz. Ha E ⊆ ℘(U), azaz E∈℘(℘(U)), akkor az E halmazt az U halmaz egy halmazcsaládjának, vagy halmazrendszerének, avagy egy U feletti (vagy U-n értelmezett) halmazcsaládnak v. halmazrendszernek . Az (U,E) rendezett párokat az U feletti hipergráfoknak nevezzük .

Egy U halmaz feletti halmazrendszer (vagy inkább halmazcsalád) tehát a ℘(℘(U)) halmaz egy eleme, míg egy U feletti hipergráf az {U}×℘(℘(U))-é.

Definíció:
Az U halmazt a hipergráf alap- vagy tartóhalmazának nevezzük, elemeit a hipergráf csúcsainak; az E halmaz(rendszer)t a hipergráf szerkezetének, elemeit a hipergráf éleinek (esetleg tagjainak) . Az |U| számosságot néha a hipergráf rendjének, míg az (|U|, |E|) párt a hipergráf típusának nevezzük.

Megjegyzés: 1). lazább szövegkontextusban (ha nem tételt v. definíciót mondunk ki v. bizonyítunk) előfordulhat, hogy a „halmazrendszer” szót a „hipergráf” szóval azonos értelemben (szinonim módon) használjuk (mint pl. e könyv címében is ...). 2). A hipergráfokról szokás kikötni, hogy ne legyenek üresek, sőt, hogy üres élt se tartalmazzanak; mi nem gondoljuk, hogy ennek túl nagy jelentősége volna.

Példák (halmazrendszerekre és hipergráfokra):

---

1. Legyen U = {a,b,c}. Akkor

E₀ = ∅, E₁ = { {a} }, E₂ = {∅, {a} }, E₃ = { {a}, {a,b,c} }

mind-mind halmazrendszerek U felett, és például

(U, E₀) = ( {a,b,c}, ∅ ), (U, E₂) = ( {a,b,c}, { ∅,{a} } )

illetve

(U, E₃) = ( {a,b,c}, { {a}, {a,b,c} } )

mind hipergráfok U felett.

2. Ha U tetszőleges halmaz, akkor a H_z = (U, ∅ ) és H_u = (U, ℘(U)) hipergráfokat az U feletti üres- vagy zéróhipergráfnak, illetve univerzális vagy teljes hipergráfnak nevezzük. A két hipergráfot együttes néven az U feletti triviális hipergráfoknak is szoktuk hívni (néha).

3. Legyen U véges halmaz, amelyre |U|=n. Az U felett annyi hipergráf van, ahány halmazrendszer, azaz ahányféleképp ℘(U) egy részhalmazát ki tudjuk választani; azaz az U feletti hipergráfok száma az U hatványhalmazának hatványhalmazának számosságával egyenlő, ami tehát $2^{\left|\wp (U)\right|}=2^{2^{n}}$.

Ezt a megállapítást mondjuk is ki tételként:

Tétel (véges halmaz feletti hipergráfok számáról):

---

Legyen U tetszőleges véges halmaz, ekkor az U feletti hipergráfok száma kettőnek 2^|U| kitevőjű hatványa.

Bizonyítás:

---

Ld. a fenti, példákat taglaló rész utolsó bekezdését.

☑

---

Mire jó mindez? - Az egyenesek (bár nem szükségszerűen kellene így lennie) alapvető szerepet játszanak az euklideszi geometriában. Ha U a „hagyományos” euklideszi sík pontjainak halmaza, akkor bármely e egyenese ennek egy speciális részhalmaza (e⊆U), tehát az összes egyenesek E halmazára E∈℘(℘(U)). A véges geometria kialakulásához az az egyszerű észrevétel szükséges, hogy a hagyományos geometriában a pontok és egyenesek halmaza úgy viszonylik egymáshoz (halmazelméletileg úgy írható le), mint egy halmaz és ennek részhalmazai egy speciális halmaza, azaz mint egy halmaz és egy ún. halmazrendszere. A hagyományos geometria egy speciális végtelen halmaz egy speciális halmazrendszerét vizsgálja. Ha tetszőleges véges halmaz speciális halmazrendszereit tekintjük, ezeket is szemlélhetjük geometriai szemüvegen át. Tetszőleges halmazrendszerekben értelmezhetünk hasonló viszonyokat, relációkat, fogalmakat, mint amelyek az euklideszi geometriában érvényesek, ezzel az euklideszi geometriát is jobban megérthetjük, de a halmazrendszerek közti absztrakt viszonyokat is szemléletesebbé tehetjük.

⍰ Gyakorló feladatok:

1. Mekkora egy véges U halmaz feletti nem üres hipergráfok száma?
2. Mekkora egy véges U halmaz feletti olyan hipergráfok száma, amelyek nem tartalmazzák élként az üres halmazt? Megoldás: ld. később.

Hipergráf Boole-vektora

Legyen U tetszőleges halmaz. Ennek minden R részhalmazához tartozik egy χ(R) karakterisztikus függvény. Tehát ℘(U) minden eleme megfelel egy U→{0,1} alakú függvénynek, azaz a 2^U halmaz egy elemének. Ugyanakkor hasonló a ℘(℘(U)) halmazra is igaz, ennek minden E eleme ℘(U) egy részhalmaza, vagyis U egy halmazcsaládja, tehát E-hez tartozik egy ℘(℘(U))-beli χ(E) karakterisztikus függvény, ami egy χ: ℘(U)→{0,1} alakú függvény, azaz egy $2^{2^{U}}$ halmazbeli elem.

Ha tehát az U egy hipergráfjára gondolunk, akkor ezt megadhatjuk egy olyan hozzárendeléssel (a hipergráf karakterisztikus függvénye a hatványhalmaz felett), amely a hatványhalmaz minden eleméhez 0-t vagy 1-et rendel aszerint, hogy az elem éle-e a hipergráfnak. De a hatványhalmaz elemei meg U részhalmazai, ezeket meg megadhatjuk egy U-beli karakterisztikus függvénnyel, azaz |U| elemű nulla-egy-sorozatokkal. Összességében tehát a hipergráfra úgy is gondolhatunk, mint egy olyan hozzárendelésre, amely a 2^|U| darab |U| tagú 0/1-sorozat mindegyikéhez a 0 vagy az 1 számot, összesen 2^|U| darab bináris, {0,1}-beli jegyet rendel.

Most már definiálhatjuk egy hipergráf Boole-vektorát.

Definíció:
Legyen U tetszőleges véges halmaz, |U| = n, és legyen ν:1,n→U bijektív leképezés, amit az U egy sorbarendezésének nevezünk. A ν(n) elemet u_n-nel jelöljük. Rendeljük hozzá minden R ∈℘(U) részhalmazhoz az o(R) := 2⁰·χ_R(u₁)+2¹·χ_R(u₂)+...+2^n-2·χ_R(u_n-1))+2^n-1·χ_R(u_n).

ún. rendszámot, ami (amellett, hogy ugyanaz, mint egy fentebbi tételben definiált m(R) szám) bijektív leképezése U hatványhalmazának a 0,2ⁿ-1 intervallumra (ld. egy fentebbi tétel bizonyításában). Mármost egy U feletti (U, E) hipergráf Boole-vektora az a 2ⁿ komponensű, a 0 és 1 számokat tartalmazó vektor, amelynek i-edik (i∈1,2ⁿ) komponense pontosan akkor 1, ha az o^-1(i) = R részhalmazra R∈E. A Boole-vektor jele ß(·).

Megjegyzések: 1). A Boole-vektor függhet az U sorbarendezésétől is, pontosabban, a komponensek sorrendje függhet ettől. Azonban, ha a sorbarendezést megváltoztatnánk (amit sosem teszünk), akkor a komponensek minden egyes Boole-vektor esetében ugyanolyan módon változnának meg, tehát lényegi változás nem történne (pl. vektort komponensenként adunk össze, ha mondjuk a harmadik komponensek a negyedik helyére kerülnének, akkor ugyanazt a két számot fogjuk összeadni, csak más helyre kerül az eredmény). Az U elemeinek sorbarendezése szükséges ugyan ahhoz, hogy a hatványhalmaz elemeinek karakterisztikus függvényeit vektorokká alakítsuk, és így (természetes) sorrendbe szedhessük – ezt valósítják meg az o(R) rendszámok – a sorrendezés az alapja annak, hogy a hipergráf „rendezetlen” karakterisztikus függvénye „rendezett” vektorrá legyen alakítható, i-eik koordinátának az i-edik legkisebb rendszámú részhalmaz karakterisztikus függvényértékét választva. De hogy ehhez a két rendezésből álló művelethez az U elemeinek konkrétan melyik sorbarendezését vesszük alapul, az általában teljesen lényegtelen. 2). Mielőtt megpróbálnánk „helyből nekifutva” megérteni a fenti definíciót, tanulmányozzuk az alábbi ábrát, hogy átlássuk, miről van szó!

Illusztráció:

---

Az U = {u₁, u₂, ... ,u_n} halmaz feletti E := { {u₁}, {u₂}, U\{u₁} } hipergráf ß(E) Boole-vektorának megkonstruálása, illetve (jobbról balra haladva), hipergráf megkonstruálása a Boole-vektorából.

- un un-1 ... u2 u1 χ(∅,u) 0 0 ... 0 0 χ(R2,u) 0 0 ... 0 1 χ(R3,u) 0 0 ... 1 0 χ(R4,u) 0 0 ... 1 1 ... χ(R|℘(U)|-1,u) 1 1 ... 1 0 χ(R|℘(U)|,u) 1 1 ... 1 1

↔

ß({R2, R3, R|℘(U)|-1 }) 0 1 1 0 ... (csupa 0) 1 0

Ha akadnak, akiket a 3. példában kapott eredmény az n elemű halmaz feletti hipergráfok számáról kísértetiesen emlékeztetett az n-változós logikai függvények számáról szóló tételre, ezek után talán jobban belelátnak összefüggésekbe.

1. ⍰ Gyakorló feladat:
   1. Bizonyítsuk be, hogy egy véges, legalább két elemű U halmazt véve, az olyan U feletti hipergráfok száma, melyek minden éle két elemű, négyzetszám!
   2. Bizonyítsuk be, hogy véges, legalább n elemű U halmazt véve, az olyan U feletti hipergráfok száma, melyeknek minden éle n elemű, n-edik hatvány! (megjegyzés: üres hipergráfot is megengedünk).
   3. Adjunk képletet egy véges, n elemű U halmaz azon hipergráfjainak számára, melyek minden éle v-elemű (v∈0,n)
   4. Legyen az U feletti H hipergráf Boole-vektora b(H), a J hipergráfé pedig b(J). (Milyen) halmazművelettel keletkezik a b^-1(b(H)@b(J)) hipergráf a H,J hipergráfokból, ha @ a modulo 2 összeadás, a szorzás, a kivonás, a minimumképzés, a maximumképzés?
   5. Hogyan néz ki egy U feletti hipergráfnak az U hatványhalmazára vonatkozó komplementerének Boole-vektora?
2. ⍰ Gyakorló feladat: Egy, az u 1,2,...,n változókon értelmezett n-változós f logikai függvény hipergráfjának nevezzük az {u_i | i=1,2,...,n} halmaz azon halmazcsaládját, amely U pontosan azon R részhalmazait tartalmazza, melyekre χ(R,u_i)=f(u_i) minden i-re teljesül. Mit jelent a logikai függvény hipergráfjára nézve az, hogy az u₁ változó fiktív (fiktívnek nevezünk egy független függvényváltozót, hogyha a többi változó rögzített értéke mellett értéke bárhogy is változik, a függvényérték állandó marad)?

☠ Nehezebb feladat:

1. Általánosítsuk a Boole-vektor fogalmát végtelen halmazokra! A jólrendezési tétel használata megengedett.
2. Véletlenszerűen választunk két n-edrendű hipergráfot (ugyanabból az U halmazból). Mekkora a valószínűsége, hogy a nagyobb rendszámú hipergráf több elemet fog tartalmazni?
3. Írjuk fel annak az eseménysorozatnak a valószínűségeloszlását (ha lehet, adjunk képletet), hogy egy k rendszámú és n-edrendű hipergráf (n rögzített, k nem) több elemet tartalmaz, mint az összes őt megelőző rendszámú! Készítsünk grafikont!

A Boole-vektor az első hatásos eszköz arra, hogy a hipergráfokat valemiféle rendezett és kényelmesebben elgondolható alakban képzelhessük el; a rengeteg idegölő, a szó szoros értelmében szemkápráztató kapcsos zárójelet és alsó indexet tartalmazó halmazelméleti formulák erre kevéssé alkalmasak. Nemsokára a Boole-vektornál is fontosabb szemléltető eszközöket is megismerünk.

A hipergráfok nevezéktanáról

Véges hipergráf rendszáma

Amikor a biológus felismer egy új növény- vagy állatfajt, megilleti őt az elnevezés joga; hasonlóan van ez az ásványkutató geológussal. A tudományok által vizsgált tárgyakat célszerű elnevezni, hogy pontosan és körülményesség nélkül beszélhessünk róluk. Az elnevezésnek általában megvannak a sajátos szabályai, hogy a sok különböző névhasználat ne okozzon káoszt.

Néha a konkrét hipergráfokat is célszerű lehet megnevezni. A matematikusok szeretik, de legalábbis használják a számokat, természetesen adódik tehát, hogy a véges hipergráfokat, akárcsak az autókat, vagy a telefonhasználati jogosultságokat, számokból álló (numerikus) azonosítókkal lássuk el. Erre az egyelőre megfelelő eszköz valójában máris a kezünkben van, mert tulajdonképp a Boole-vektor is felfogható, mint egy elég adekvát név egy U halmaz feletti hipergráf számára. A bináris Boole-vektor azonban nagyon hosszú és emberidegen (számítógépek számára inkább megfelel ...), ezért használjuk inkább a rendszámot, ami tulajdonképp szintén definiálva van már. A Boole-vektor definíciójakor bevezettük egy U halmaz valamely ν:1,n→U sorbarendezése esetén tetszőleges R∈℘(U) részhalmazra az

o_{U, ν}(R) := 2⁰·χ_R(u₁)+2¹·χ_R(u₂)+...+2^n-2·χ_R(u_n-1))+2^n-1·χ_R(u_n).

ún. rendszámot, ami szemléletesen azt jelenti, hogy az U elemeivel megcímkézzük egy n db. oszlopot és 2ⁿ sort tartalmazó táblázat oszlopait, jobbról balra növelve a sorbarendezés által kapott indexet (tehát a legbaloldalibb oszlop fejlécébe kerül az az elem, amely a legnagyobb indexet kapja); a táblázat soraiba pedig növekvő lexikografikus rendben beírjuk az U részhalmazait, 0-val jelölve, ha egy részhalmazban nincs az adott oszlopban álló elem, és 1-gyet írva a sor cellájába, ha az abban az oszlopban álló elem eleme a részhalmaznak. Mármost ha az oszlopokat kettes számrendszerbeli helyiértéknek gondoljuk, akkor kapjuk a részhalmaznak megfelelő rendszámot. Amint fentebb már bebizonyítottuk, így a 0,2ⁿ-1 halmazra képezzük le bijektív módon ℘(U)-t. Vegyük észre, hogy akkor ez tulajdonképp a ℘(U) halmaz egy sorbarendezése, pontosabban a μ(k): 1,2ⁿ+1→℘(U); μ(k) := [o_U,ν(R)]^-1(k-1) „inverz” függvény egy sorbarendezése a ℘(U) hatványhalmaznak.

Ezt a megrendszámozási műveletet bármely halmazra elvégezhetjük, így elvégezhetjük az U helyett a ℘(U) halmazzal is, csak azt kötjük ki, hogy a sorbarendezés a μ(j) függvény legyen. Formálisan definiálva, tehát a következőképp rendelhetünk egy U feletti hipergráfhoz rendszámot:

Definíció:

---

Az ν sorbarendezéssel sorbarendezett U halmaz feletti ${\mathcal {H}}$ hipergráf rendszámának mondjuk azt a természetes számot, amit a következőképp rendelünk hozzá:

$O_{U,\nu }\left({\mathcal {H}}\right):\wp \left(\wp \left(U\right)\right)\to {\underline {0,2^{2^{n}}-1}};$ $O_{U,\nu }\left({\mathcal {H}}\right)\ :=\ \sum _{k=0}^{2^{|U|}-1}2^{k}\cdot \chi _{\mathcal {H}}\left(o_{U,\nu }^{-1}\left(\mathbf {k} \right)\right)$ = = $\sum _{k=0}^{2^{|U|}-1}2^{k}\cdot \chi _{\mathcal {H}}\left(o_{U,\nu }^{-1}\left(\mathbf {k} \right)\right)$ = ami mellesleg = $\sum _{k=0}^{2^{|U|}-1}2^{k}\beta \left({\mathcal {H}}\right)_{k}$ .

(β(...)_k a Boole-vektor k-adik koordinátáját, elemét jelöli).

Példa:

---

Például vegyük a lexikografikusan sorbarendezett U = {a,b,c,d} halmaz - tehát ν(1)=a, ν(2)=b, ν(3)=c, ν(4)=d - feletti E := {∅, {a}, {b}, {c}, {b,c}, {a,b,c} } halmazcsaládot. Hogy az ehhez tartozó (U, E) hipergráfnak rednszámot adhassunk az adott ν(...) sorbarendezés mellett, számoljuk ki a családban található élek rendszámát. Az {a}, {b} halmazoké könnyűszerrel leolvasható: 1 és 2. A {c} halmaz karakterisztikus vektora az adott sorbarendezés mellett (0, 1, 0, 0), tehát rendszáma 2² = 4; a {b,c}-é meg (0, 1, 1, 0) és így a rendszám 2¹+2² = 2+4 = 6. Végül az {a,b,c} karakterisztikus vektora {0, 1, 1, 1} és így rendszáma 2²+2¹+2⁰ = 4+2+1 = 7. A hipergráf rendszáma ezen rendszámok összege.

Tehát a rendszám: O_U,ν((U,E)) := 2⁰+2¹+2²+2³+2⁶+ 2⁷ = 11001111₍₂₎ = 1+2+4+8+64+128 = 207. A legkisebb lehetséges rendszám e halmaz felett természetesen 0, az üres hipergráf rendszáma, a legnagyobb pedig a teljes hipergráfé, 2¹⁶ = 1024 · 64 = 65536.

A rendszámos módszer megszámlálható alaphalmaz feletti hipergráfra is kiterjeszthető, ilyenkor bináris tizedestörteket használhatunk, tehát a rendszámok valós racionális számok lesznek. A rendszámra adott képlet elég bonyolult, de gondoljuk meg, hogy valójában csak a következő egyszerű utasítást jelenti: „Add össze pontosan azokat a nemnegatív egész kitevőjű kettőhatványokat, amelyek kitevője a hipergráf valamely élének rendszáma! ”

---

A rendszám viszonylagosságáról

A rendszám adott alaphalmaz felett, az alaphalmaz megnevezésével együtt érvényes. Ha csak egy hipergráf rendszámát ismerjük, visszakapható belőle egy csomó információ a hipergráfról, de maga a hipergráf nem kapható vissza egyértelműen. Tudnunk kell, pontosan milyen U halmazból lett konstruálva. Például vegyünk 5-ös rendszámú hipergráfot. Az 5-öt felírjuk a kettes számrendszerben, 5=4+1 alapján ez 101. Ez tulajdonképp a Boole-vektor, csak -90^o-kal elforgatva, és esetleg le van vágva belőle egy csomó 0. Mármost a jobbról az első helyen, az 1-es helyiértéken 1 van, ami azt méri, eleme-e az üres halmaz a hipergráfnak. Most tehát az eleme. A következő n db. jegy pedig az egyelemű részhalmazok beletartozását méri. Csakhogy tudnunk kell, az alaphalmaz hány elemű. Egyelemű nem lehet, mert akkor a rendszám legfeljebb 2² = 5 lehetne. De ha kételemű, akkor akkor a rendszám bináris alakjának első két jegye a két egyelemű halmaz beletartozását mérné, ha meg háromelemű, akkor az első három jegy a három egyelemű halmaz beletartozását mérné ... kételemű halmaz esetén a sorbarendezés szerinti első elemből álló egyelemű részhalmaz nincs a hipergráfban, míg a másodikból álló igen. De az is lehet, hogy az alaphalmaz három elemű, csakhogy a sorbarendezés szerinti harmadik elemtől kezdve az ilyen elemekből álló egyelemű részhalmazok nem elemei a hipergráfnak, ezért a rendszám bináris alakja 00000101 volt, és az első helyen álló nullákat levágva, adódott a 101.

Mármost ha az alaphalmaz számosságát pontosan ismerjük, akkor sem biztosan kapható vissza a hipergráf, hiszen tudjuk pl., hogy eleme egy {x} alakú egyelemű halmaz, na de mi volt az az x? Ezt csak az alaphalmaz és annak sorbarendezése ismeretében dönthető el. Tehát nem önmagában a rendszám a neve egy hipergráfnak, hanem az (U, ν O_U,ν(H) ) rendezett hármas jelenti egy konkrét hipergráf megnevezését.

De ha a rendszámok nem a hipergráfok nevei, akkor meg miknek? Erre ad választ a következő fejezet; melyben kiderül, hogy nem igazán a konkrét hipergráfok, hanem az ún izomorfiaosztályok megnevezésére van szükség; viszont azok azonosítása is hasonló módszeren alapul majd.

⍰ Gyakorló feladatok:

1. Bizonyítsuk be, hogy adott U halmaz felett az O_U,ν(...) leképezés kölcsönösen egyértelmű megfeleltetést létesít az U feletti hipergráfok {U}×℘(℘(U)) halmaza és a ${\mbox{ }}_{\underline {0,2^{2^{n}}-1}}$ diszkrét intervallum között;
2. Feladatok számelméletkedvelőknek:
   1. Válasszunk egy (lehetőleg háromnál nagyobb) n természetes számot, és egy n elemű U halmazt. Hogyan jellemezhetőek szerkezetileg azok az U feletti hipergráfok, amelyekre igaz, hogy rendszámuk többszöröse valamely Fermat-számnak?
   2. Lássuk be, hogy adott U halmaz és ν sorbarendezés mellett a ${\mbox{ }}_{P_{U,\nu }\left({\mathcal {H}}\right):\wp \left(\wp \left(U\right)\right)\to {\underline {1,2^{2^{n}}}};}$ ${\mbox{ }}_{P_{U,\nu }\left({\mathcal {H}}\right)\ :=\ \log _{2}\left(\prod _{k=0}^{2^{|U|}}2^{k}\cdot \chi _{\mathcal {H}}\left(o_{U,\nu }^{-1}\left(\mathbf {k} \right)\right)\right)}$ függvény nem jelent bijektív leképezést!
   3. Mi az értékkészlete a fenti leképezésnek?

Jegyzetek

---

---

Lap teteje

---