Halmazrendszerek geometriája/Halmazrendszerek és hipergráfok

A Wikikönyvekből, a szabad elektronikus könyvtárból.
Ugrás a navigációhoz Ugrás a kereséshez
Bevezetés

Tartalomjegyzék

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 [1].

Egy U halmaz, néhány részhalmaza (piros); és egy 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. Ha pedig azzal próbálkoznánk, hogy az elemeket egyenes vonallal kössük össze, akkor már egész közel járnánk a jelen jegyzet témájához.

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 [2]. 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). [3]

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

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[szerkesztés]

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} . [4]


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

Gyakorló feladatok: Feladatgyűjtemény: Diszkrét intervallumok 1., 2.



Sorbarendezések[szerkesztés]

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 [5]). 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).

Gyakorló? feladatok: Feladatgyűjtemény: Sorbarendezések  


Részhalmaz, hatványhalmaz[szerkesztés]

Részhalmaz karakterisztikus függvénye[szerkesztés]

Definíció:
Legyen U tetszőleges halmaz, és RU; ekkor az
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 H0(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 H0(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.



Részhalmaz karakterisztikus vektora[szerkesztés]

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. [6]

Gyakorló feladatok: Feladatgyűjtemény: Karakterisztikus vektor  


Hatványhalmaz[szerkesztés]

Definíció:
Legyen U tetszőleges halmaz.
(U)   -val [7]

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:
RU    ⇔[8]    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)| =
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) = 20·χR(s(1))+21·χ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
= 20+21+...+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 = 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ó feladatok: Feladatgyűjtemény: Hatványhalmaz  


Halmazrendszerek avagy hipergráfok[szerkesztés]

Halmazrendszer, hipergráf[szerkesztés]

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 [9].


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) [10]. 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
E0 = ∅,
E1 = { {a} },
E2 = {∅, {a} },
E3 = { {a}, {a,b,c} }
mind-mind halmazrendszerek U felett, és például
(U, E0) = ( {a,b,c}, ∅ ),
(U, E2) = ( {a,b,c}, { ∅,{a} } )
illetve
(U, E3) = ( {a,b,c}, { {a}, {a,b,c} } )
mind hipergráfok U felett.
2. Ha U tetszőleges halmaz, akkor a Hz = (U, ∅ ) és Hu = (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 .

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: Feladatgyűjtemény: Hipergráfok  


Hipergráf Boole-vektora[szerkesztés]

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 2U 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 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,nU bijektív leképezés, amit az U egy sorbarendezésének nevezünk. A ν(n) elemet un-nel jelöljük. Rendeljük hozzá minden R(U) részhalmazhoz az
o(R) := 20·χR(u1)+21·χR(u2)+...+2n-2·χR(un-1))+2n-1·χR(un).
ú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,2n-1 intervallumra (ld. egy fentebbi tétel bizonyításában). Mármost egy U feletti (U, E) hipergráf Boole-vektora az a 2n komponensű, a 0 és 1 számokat tartalmazó vektor, amelynek i-edik (i∈1,2n) komponense pontosan akkor 1, ha az o-1(i) = R részhalmazra RE. 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 = {u1, u2, ... ,un} halmaz feletti E := { {u1}, {u2}, U\{u1} } 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 [11] 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.

Gyakorló feladatok: Feladatgyűjtemény: Gyakorló feladatok  


További feladatok: Feladatgyűjtemény: További feladatok  


Nehezebb feladatok: Feladatgyűjtemény: Nehezebb feladatok  


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.

Részhipergráf[szerkesztés]

Definíció:
Legyen A := {U, E} egy U halmaz feletti hipergráf. Az B := {U, F} U feletti hipergráfot a H részhipergráfjának nevezzük, ha szerkezete részhalmaza az utóbbi szerkezetének, azaz ha B minden éle egyben A-nak is éle. E relációt ⊆ jelöli [12]. Azt is mondjuk,


Néhány megjegyzés:

  1. Részhipergráf karakterisztikus függvényének a bővebb hipergráf „logikai következménye”, a bővebb hipergráf karakterisztikus függvénye minden olyan u∈U elemre 1, amely elemekre a részhipergráf karakterisztikus függvénye is 1-et vesz fel, bár a bővebb hipergráf az U más elemein is vehet fel 1-es értékeket.
  2. Részhipergráf Boole-vektora úgy keletkezik egy bővebb hipergráféból, hogy néhány egyest kitörlünk belőle (0-ra írjuk át).

A hipergráfok nevezéktanáról[szerkesztés]

Véges hipergráf rendszáma[szerkesztés]

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,nU sorbarendezése esetén tetszőleges R℘(U) részhalmazra az

oU, ν(R) := 20·χR(u1)+21·χR(u2)+...+2n-2·χR(un-1))+2n-1·χR(un).

ún. rendszámot, ami szemléletesen azt jelenti, hogy az U elemeivel megcímkézzük egy n db. oszlopot és 2n 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,2n-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,2n+1℘(U); μ(k) := [oU,ν(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 hipergráf rendszámának [13] mondjuk azt a természetes számot, amit a következőképp rendelünk hozzá:
=
= =
ami mellesleg
= .


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

Symbol opinion vote.svg 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 22 = 4; a {b,c}-é meg (0, 1, 1, 0) és így a rendszám 21+22 = 2+4 = 6. Végül az {a,b,c} karakterisztikus vektora {0, 1, 1, 1} és így rendszáma 22+21+20 = 4+2+1 = 7. A hipergráf rendszáma ezen rendszámok összege.

Tehát a rendszám: OU,ν((U,E)) := 20+21+22+23+26+ 27 = 11001111(2) = 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é, 216 = 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[szerkesztés]

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ák:



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: Feladatgyűjtemény: Rendszám  

Számelméletkedvelőknek szánt feladatok: Feladatgyűjtemény: Számelméletkedvelőknek  


Jegyzetek[szerkesztés]

  1. A hipergráfok elmélete természetesen a matematika kombinatorika nevű alágának része, és nem a geometriának. Mégis, aligha tévedünk nagyot, sőt talán egyáltalában nem is tévedünk, ha megkockáztatjuk annak kimondását: a gráfelmélet jórészt annak köszönheti népszerűségét, hogy olyan dolgokkal foglalkozik, amik nemcsak az alkalmazások számára rendkívül hasznosak, de figurálisan, geometriailag ábrázolhatóak is. A hipergráfokra ez már sokkal kevésbé igaz, de mégis, rengeteg velük kapcsolatos fogalom az igencsak szemléletes gráfelméleti fogalmak általánosítása. Ha nem így lenne, ha a hipergráfelméletnek nem lennének mélyen a geometriába nyúló gyökerei, ez a munka nem jöhetett volna létre.
  2. C Berge: Graphs and Hypergraphs, American Elsevier Publishing Company, 1973; ISBN-10 0444103996 ; ISBN-13 978-0444103994 .
  3. A történeti adatok forrása: R. L. Graham - M. Grötschel - Lovász L.: Handbook of combinatorics. MIT Press, 1995.; elektronikus verzió: 2008. 07. 16. de. 9:14; 383. old.
  4. 1). A halmazok kivonására a valós számok kivonásának jelölésére is használt mínuszjelet alkalmazzuk. 2). A szerző emlékezete szerint, a „diszkrét intervallumokra ” használt aláhúzásos jelölésmódot Hermann Péter (ELTE TTK algebra tanszék) vezette be házi használatra algebra előadásain valamikor a kilencvenes években; de a tévedés jogát fenntartjuk.
  5. Ld. a Tárgymutatót.
  6. Egy, elemeit az A halmazból felvevő α∈A×A×..×A  (n db. tényező) n-dimenziós vektor i-edik koordinátáját néha [α]i-vel jelöljük majd; bár gyakrabban előfordul a szakirodalomban, hogy αi-vel jelölik. Utóbbi, bár egyszerűbb, de félreértéshez ill. nyomdatechnikai bonyodalmakhoz vezethet, ha a vektorok maguk is indexelve vannak, néha szükséges kihangsúlyozni egy vektorból koordinátákat képező függvényosztály létezését.
  7. egy nagy írott Pé betű, a latin potentia (hatvány) szó kezdőbetűje.
  8. Olvasd: „ ... akkor és csak akkor igaz, ha ...” vagy „... ugyanazt jelenti, mint ...”. A ⇔ jel az oda-vissza következményesség jele; míg az „A következménye B-nek” rövidítése A⇒B.
  9. Bevett szokás - különösen a kombinatorikai szakirodalomban - az (U,E) rendezett párokat, tehát „hipergráfokat” nevezni az U feletti halmazrendszereknek. Ez két okból is rendkívül szerencsétlen: A). igazából a „halmazcsalád” lenne jobb elnevezés, mert a halmazrendszer mást, általánosabb fogalmat (is) jelent; a halmazcsalád (hipergráf) halmazok halmaza, amelyben egy tag nem fordulhat többször elő és a sorrendnek nincs megkülönböztető ereje; míg a halmazrendszer igazából halmazok sorozata vagy multihalmaza, amelyben az elemek sorrendje sem lényegtelen, és egy elem többször is előfordulhat; B). Az (U,E) párra (ahol E(U) ) ráadásul bevezethető a sokkal szerencsésebb topologikus struktúra, illetve hipergráf elnevezés. A hipergráf a „halmazrendszernél” sokkal jobb (a „topologikus struktúránál” pedig alig rosszabb) terminológia, mert nem „rabolja el” a „halmazrendszer” szótól annak valódi jelentését, azonosítva a struktúrát (a tartóhalmaz és a szerkezet párosát) a strukturális szerkezetével; az egyetlen baj, hogy a szakirodalomban még nem rögzült eléggé a jelentése, ugyanis a lentebb általunk „illeszkedési struktúráknak” nevezett fogalmat is szokás hipergráfoknak nevezni, ld. pl. Hajnal Péter: Halmazrendszerek, Polygon, 2002. A legproblémamentesebb elnevezés tehát a „topologikus struktúra” lenne.
  10. Szokás élek helyett hiperéleket is mondani, hangsúlyozva, hogy nem gráf éleiről (legfeljebb két pontot tartalmaznak), hanem hipergráfélekről van szó. Minthogy számunkra az „él” szó az „egyenes” fogalmának primitív előképét jelenti, ezért megtartjuk az utóbbbival analógabb fogalomra utaló „él” elnevezést.
  11. Miért címkézzük fordítva az oszlopokat, az elsőt az n indexű u-beli elemmel, az utolsót meg az 1 indexűvel?
  12. A jelölések azonossága nem okoz majd félreértést, ugyanis egy hipergráfnak bármely részhipergráfja halmazelméleti értelemben is részhalmaza, bár megfordítva ez nem igaz.
  13. Ne keverjük a hipergráf rendjével, ami tartóhalmazának számosságát jelenti. Két azonos rendű, mondjuk n-edrendű hipergráfnak egészen különböző rendszámai lehetnek, nullától egészen kettő a kettő az n-ediken-ediken-mínusz-egyig.


Lap teteje