Szerkesztő:Gubbubu/Halmazrendszerek geometriája/Hipergráfok izomorfiája

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

Az előző fejezetben megismerkedtünk egy igen elvont „felsőfokú” kombinatorikai fogalommal, a hipergráfokkal, továbbá olyan eszközökkel és módszerekkel, melyek egyrészt a véges struktúrák kezeléséhez, a végesség fogalmának meghatározásához általában szükségesek vagy nagyon hasznosak (sorbarendezések, karakterisztikus függvények), másrészt pedig a hipergráfokkal kapcsolatosak, azok szemléltetésére és leírására jól használhatóak. E fejezetben még folytatjuk az „alapozást”, minthogy egy alapvető probléma nyitva maradt.

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

Elöljáróban[szerkesztés]

Az előző fejezetben egy U véges halmaz feletti hipergráfhoz a következőképp rendeltünk egy - amint kiderült, nem egészen egyedi - azonosító rendszámot:


ami mellesleg

.

Rájöttünk, hogy csakis egy rendszámból nem jöhetünk rá, melyik hipergráf rendszáma, ismernünk kell a tartóhalmazt és a sorbarendezést.

Van egyáltalán értelme az olyan neveknek, hogy a tulajdonosukat látva bárki kitalálja, hogy hívják, de ha csak a nevet ismeri, akkor akár végtelen sok különböző személyre is gondolhat? Ha az illető egy bűnöző, aki bűntényt követett el, a szemtanú megmondhatja a nevét a rendőrségnek, de a rendőrség esetleg egy egészen másik személyt fog letartóztatni! Bármilyen meglepő, mégis mindennap használunk ilyen neveket. Ezek a faj- vagy fajtanevek. Pl. egy zebrát látva egy zebracsordában, azonnal meg tudjuk nevezni, hogy az illető egy zebra, de ha csak annyit mond valaki nekünk: "Lődd meg a zebrát", akkor meg kell kérdeznünk, melyik zebrára gondolt pontosan.

Ezek, természetüknél fogva, bár fontos, de nem elegendő eszközök egy hipergráf azonosítására abban az értelemben, hogy a rendszámából nem kapható vissza egyértelműen egy hipergráf, hanem egy egész seregnyi. Emiatt célszerű megvizsgálni, szerkezetileg mi közös van az azonos rendszámú hipergráfokban. Ez a kérdés egész természetesen vezet az ún. izomorfia fogalmához.

A rendszámkonstruálási folyamat elemzése[szerkesztés]

Hogy megérthessük, mi a közös az azonos rendszámú hipergráfok szerkezetében, elemezzük a rendszám definícióját. Egy rendszám kiszámolásához a következő dolgok szükségesek (szürkével szedtük azokat a komponenseket, melyek nem független összetevők, hanem egyértelműen adódnak valamely előző komponensből:

Absztrakt Konkrét
Egy U alaphalmaz {a,b,c}
Egy ν sorbarendezés ν(1)=a;
ν(2)=b;
ν(3)=c;
ν(4)=d;
Az U néhány részhalmaza
(maga a hipergráf-szerkezet)
{a}, {b}, {abc}
E részhalmazok „o(R)” rendszámai 1, 2, 7
Az „o(R)” rendszámokkal azonos kitevőjű
kitevőjű kettőhatványok
2, 4, 256
Ezen kettőhatványok összege 262
Kész.

Kezdjük az utolsó független összetevővel, a szerkezettel. Ha megváltoztatjuk (miközben a többi független összetevő változatlan marad), akkor azonnal megváltozik a rendszám. Ennek oka egy közismert számelméleti tétel. Minden U-beli részhalmazhoz egyértelműen tartozik egy rendszám, ahogyan ezt korábban már beláttuk. Ha megváltozik a részhalmaz, a rendszáma is megváltozik ezért, és így a rendszámhoz tartozó helyiértéken álló jegy is változik (0-ról egyre változik, azaz nő, vagy 1-ről 0-ra, azaz csökken). Ezzel a hipergráf rendszámának kettes számrendszerbeli előállítása is megváltozik, tehát maga a hipergráf-rendszám is. Ugyanis a számok kettes számrendszerbeli előállítása egyértelmű. A helyzeten az sem segít, ha pl. a részhalmazhoz tartozó jegy törlését azzal kívánjuk kompenzálni, hogy egy magasabb rendszámú részhalmazt hozzáveszünk a hipergráfhoz, azaz „kompenzálni” próbáljuk a változást. Ahogy mondtuk: a számok kettes számrendszerbeli előállítása egyértelmű, ha bárhogy is megváltoztatjuk a hipergráfot, változni fog a karakterisztikus függvénye (avagy: a Boole-vektora), a bijektivitás miatt a másik részhalmazhoz egyértelműen egy másik karakterisztikus függvény fog tartozni (ha ugyanaz tartozhatna, a „bijekció” nem lenne injektív, és így bijekció sem), ahhoz pedig a rendszám bijektivitása miatt egyértelműen egy másik kettes számrendszerbeli rendszám, ahhoz pedig egyértelműen egy másik tízes számrendszerbeli rendszám. Mese nincs.

Gyakorló feladatok:

  1. Hogyan változik egy U={a,b,c,d} halmaz feletti hipergráf rendszáma, ha
    1. az (abcd) sorbarendezés mellett minden éléhez hozzávesszük az a elemet?
    2. ha szerkezetét nem változtatjuk, de a (dcba) sorbarendezést vesszük?
    3. ha az (abcd) sorbarendezés helyett a (dcba)-t vesszük, és minden éléhez hozzáadjuk az a elemet?

Korábban már említettük, hogy a sorbarendezés megváltoztathatja a Boole-vektort, ez pedig azt jelenti, hogy a rendszámot is, hiszen a rendszám nem egyéb, mint azon kettőhatványok összege, melyek kitevőire igaz, hogy a Boole-vektor felülről annyiadik (i-edik, ha a kitevő i) koordinátája 1. Hogy a Boole-vektor mely sorába kerül 1-es, az azonban nemcsak a szerkezettől függ, hanem a sorbarendezéstől is, ugyanis a sorbarendezés változása megváltoztatja a részhalmazok rendszámait, ám ez utóbbiak a Boole-vektor sorainak indexei, tehát ezek is megváltoznak, azaz más sorokba kerülnek az 1-esek. A Boole-vektor Hamming-súlya (a benne lévő egyesek száma) változatlan marad, de az egyesek és nullák sorrendje megváltozik. Ez pedig azt jelenti, hogy a rendszám 1-es jegyei más helyiértékeken fognak állni, és emiatt, a már említett számelméleti tétel értelmében, maga a rendszám is óhatatlanul megváltozik.


Új szakasz[szerkesztés]

- u1 u2 ... un-1 un
χ(∅,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
  1. Gyakorló feladat:

Feladat: Nemsokára a Boole-vektornál is fontosabb szemléltető eszközöket is megismerünk.

Jegyzetek[szerkesztés]



Lap teteje