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

• Témák jegyzéke
• Előző fejezet (Halmazrendszerek és hipergráfok)
• Következő fejezet (Illeszkedési struktúrák)

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.

Elöljáróban

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

${\mbox{ }}_{O_{U,\nu }\left({\mathcal {H}}\right):\ \wp \left(\wp \left(U\right)\right)\to {\underline {0,2^{2^{n}}}};}$

${\mbox{ }}_{O_{U,\nu }\left({\mathcal {H}}\right)\ :=\ \sum _{k=1}^{2^{|U|}+1}2^{k-1}\cdot \chi _{\mathcal {H}}\left(o_{U,\nu }^{-1}\left(\mathbf {k} -1\right)\right)}$ $=$ ${\mbox{ }}_{\sum _{k=1}^{2^{|U|}+1}2^{k-1}\cdot \chi _{\mathcal {H}}\left(o_{U,\nu }^{-1}\left(\mathbf {k} -1\right)\right)}$ $=$

ami mellesleg

$=$ ${\mbox{ }}_{\sum _{k=1}^{2^{|U|}+1}2^{k-1}\beta \left({\mathcal {H}}\right)_{k}}$ .

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

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

- 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

---

---

Lap teteje

---