Szerkesztő:Gubbubu/Halmazrendszerek geometriája/Illeszkedési struktúrák

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

Illeszkedési struktúra

Az illeszkedési vagy incidencia-struktúrák a hipergráfok általánosításai lesznek abban az értelemben, hogy bármely hipergráf egy illeszkedési struktúra is egyben.

Az illeszkedési struktúrák segítségével bevezethető számtalan olyan hasznos és fontos fogalom, amelyeket a hipergráfokra specializálva, még hasznosabb és még fontosabb fogalmak nyerhetők. Számunkra nagyjából ennyi az értelme annak, hogy illeszkedési struktúrákkal foglalkozzunk, de ezt elegendőnek is tartjuk. Természetesen azt is megtehetnénk, hogy ezen fogalmakat egy az egyben, kerülő nélkül a hipergráfokra vezetjük be; azonban nem árt néha elszakadni a kizárólag a halmazelméleti ∈ relációra hagyatkozó terminológiától (ennek előnyét a térgeometriai fejezetekben talán tapasztalni fogjuk, ha sor kerül rá).

Egyes speciális osztályba tartozó illeszkedési struktúrák (az ún. kombinatorikus konfigurációk), illetve ezek egészen konkrét példáinak tanulmányozása igen régen, az 1800-as évek közepétől megkezdődött. Az illeszkedési struktúra fogalma azonban csak később alakult ki. Mára a fizikában is egész komoly alkalmazásokat nyertek .

Az illeszkedési struktúra fogalma

Definíció:

---

Ha U és E tetszőleges diszjukt (közös elemet nem tartalmazó, azaz az U∩E = ∅ feltételt kielégítő) halmazok, és ι⊆U×E egy U és E közti reláció, vagyis a ℘(E×U) halmaz egy eleme; akkor az (U, E, ι) hármast az U és E feletti egy illeszkedési struktúrának nevezzük. .

Az U elemeit szokás csúcsoknak vagy pontoknak, az E elemeit pedig éleknek nevezni . A ι reláció elemeit - az euklideszi kontinuum-geometriából kölcsönzött kifejezéssel - zászlóknak nevezik.

Az (|U|, |E|, |ι|) hármast az illeszkedési struktúra típusának nevezzük.

Az E×U halmazt, néha „az elvileg elképzelhető összes zászlók halmazának” vagy hasonló néven fogjuk emlegetni. A struktúrát megadó illeszkedési reláció tehát ennek egy részhalmaza.

A legfontosabb illeszkedési struktúrák a hipergráfok. Egy U halmaz feletti (U, E) hipergráf, ahol E⊆℘(U), felfogható olyan (U, E, ∈) illeszkedési struktúraként, ahol ∈ a halmazelméleti „eleme” reláció. Ennek következménye, hogy minden hipergráfnak megfeleltethető egy illeszkedési struktúra. Ez bizonyos mértékben és megszorításokkal fordítva is igaz, de erről bővebben lentebb.

A következő példákból talán ki fog derülni, hogy az illeszkedési struktúra absztrakt fogalmára példákat felhozni kevéssé értelmes dolog. Ez nem az absztrakt fogalom hibája: miután az elektromosságtannal foglalkozó fizikusok nemsokára feltalálják az incidenciamátrix fogalmát (egész pontosan, a következő szakaszban), az illeszkedési struktúrák rögtön kezelhetőbbé válnak majd.

Példa:

---

1. Egy absztrakt példa. Legyen pl. U = {u₁, u₂, u₃, u₄} és E = {e₁, e₂, e₃, e₄, e₅}. Válasszunk ki véletlenszerűen egy pár zászlót: (u₁, e₁), (u₂, e₁), (u₃, e₂), (u₃, e₄). Ezekből a zászlókból a következő illeszkedési struktúra fog összeállni: ( {u₁, u₂, u₃, u₄}, {e₁, e₂, e₃, e₄, e₅} ; { (u₁, e₁), (u₂, e₁), (u₃, e₂), (u₃, e₄) } ).

Karakterisztikus függvény. Incidenciamátrix.

Definíció:

---

Legyenek U és E tetszőleges nem üres és diszjunkt halmazok, és K = $(U,E,\iota )$ egy, az adott halmazok feletti illeszkedési struktúra, ekkor a $\chi \left(\langle u,e\rangle \right):U\times E\rightarrow \left\{0,1\right\};\ \ \chi \left(\langle u,e\rangle \right):={\begin{cases}0,&{\mbox{ha }}\langle u,e\rangle \not \in \iota ;\\1,&{\mbox{ha }}\langle u,e\rangle \in \iota \end{cases}}$ előírással értelmezett függvényt a K illeszkedési struktúra karakterisztikus függvényének nevezzük. Ha szükséges, magát a struktúrát is feltüntethetjük alsó indexben: χK(<u,e>); kényelmi okok miatt a rendezettpár-operátor csúcsos zárójeleit - <...> pedig nem írjuk ki, sőt sokszor csak az indexeket írjuk ki:

χ_ij := χ((<u_i,e_j>)),

ahol i∈1,|U| és j∈1,|I|.

Formulamentes nyelven arról van szó, hogy az összes csúcs-él párra értelmezzük a karakterisztikus függvényt, és ennek értéke 1, ha az illető csúcs eleme az illető élnek (illeszkedik rá, azaz „benne van a struktúrában”), 0 pedig, ha nem (azaz „nincs benne”). 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 „rajta van-e ez a csúcs azon az élen ebben az illeszkedési struktúrában” kérdésre felel igennel vagy nemmel.

A karakterisztikus függvényt, véges sok, n db. csúcsot és véges sok, k db. élt tartalmazó illeszkedési struktúra esetén, gyakran írjuk k×n-es táblázat (mátrix) alakba, melynek k sora és n oszlopa van, ez az incidenciamátrix (illeszkedési mátrix). E hasznos és szemléletes fogalmat állítólag a fizikus Kirchhoff vezette be gráfokra 1847-ben :

Illusztráció:

---

Incidenciamátrix származtatása

u1 u2 ... un i1 χ(<u1,i1>) χ(<u2,i1>) ... χ(<un,i1>) i2 χ(<u1,i2>) χ(<u2,i2>) ... χ(<un,i2>) ... ik χ(<u1,ik>) χ(<u2,ik>) ... χ(<un,ik>)

↔

${\begin{pmatrix}\chi _{1,1}&\chi _{1,2}&...&\chi _{1,n}\\\chi _{2,1}&\chi _{2,2}&...&\chi _{2,n}\\...\\\chi _{k,1}&\chi _{k,2}&...&\chi _{k,n}\end{pmatrix}}$

Megjegyezzük: 1). hogy a legtöbb szerző a soroknak szokta az U és az oszlopoknak az I elemeit megfeleltetni (a fenti k×n-es mátrix helyett annak n×k-as „felfordítottját”, transzponáltját veszi), de az eltérés, amennyiben következetes, nyilván lényegtelen. 2). a szemléletesség kedvéért az 1-est tartalmazó cellákat szokás besatírozni, vagy fekete ponttal kitölteni, a többi, 0-t tartalmazó cellát üresen hagyni. Ez különösen a nagyobb (10-50 sornál és/vagy oszlopnál többet tartalmazó) mátrixok esetén bevett, a jobb áttekinthetőséget szolgáló ábrázolásmódja a(z incidencia)mátrixoknak.

Példák:

---

1. Tetszőleges U halmaz feletti (U, ∅) üres hipergráf incidenciamátrixa egy 0×|U| típusú, azaz nulla soros mátrix lenne. Az ilyen hipergráfoknak így nincs incidenciamátrixa.
2. A fentebb említett absztrakt példa, nevezetesen a ( {u₁, u₂, u₃, u₄}, {e₁, e₂, e₃, e₄, e₅} ; { (u₁, e₁), (u₂, e₁), (u₃, e₂), (u₃, e₄) } ) struktúra incidenciamátrixa: ${\begin{pmatrix}1&1&0&0\\0&0&1&0\\0&0&0&0\\0&0&1&0\\0&0&0&0\end{pmatrix}}$
3. Tekintsük a következő incidenciamátrixot: ${\begin{pmatrix}0&0&0&0\\1&0&0&1\\1&1&1&0\end{pmatrix}}$.
   Erre ránézve azonnal láthatjuk, hogy 3×4-es típusú; azaz U négy elemet tartalmaz (legyenek u_1,2,3,4), mivel hogy a mátrix négy oszlopos; és három élt, mivel a mátrix három soros. Az első sorban csupa nulla áll, tehát az első él egyetlen elemet sem tartalmaz, így ez egy (ez az) üres él: . A második él az u₁ és u₄ elemeket tartalmazza, azaz I₂ = {u₁, u₄}; a harmadik meg az első három elemet, de a negyediket nem, azaz I₃ = {u₁, u₂, u₃}. Vagyis az illeszkedési mátrixból, az U elemeinek mibenlététől eltekintve (matematikai terminológiával: „izomorfia erejéig”) egyértelműen rekonstruálni tudtuk az egyetlen hozzá tartozó illeszkedési struktúrát: ez pedig az ( {u₁, u₂, u₃, u₄}, { ∅, {u₁, u₄}, {u₁, u₂, u₃ } } ).

Megjegyzés: 1). A példák remélhetőleg meggyőzőek a tekintetben, hogy mennyivel kényelmesebb, átláthatóbb lesz az incidenciamátrixokkal dolgozni (pl. leírni őket), mintsem a halmazelmélet nyelvét alkalmazni az incidenciastruktúrák leírására, és számolgatni, minden kapcsos zárójel be van-e zárva. 2). Az illeszkedési struktúráknak az incidenciamátrixon kívül még sokféle hasznos szemléltetési módja, kódolása, ábrázolása van (pl. az adjacencia-mátrix, a Lévi-gráf stb.). Ezekkel egyelőre nem foglalkozunk. 3). A fentiekben véges struktúra incidenciamátrixairól beszéltünk. A fogalom kiterjeszthető lenne véges illeszkedési struktúrákra is, ám ezek illeszkedési mátrixa végtelen sok sort és/vagy oszlopot tartalmazna. A kérdés, hogy mi értelme van ennek. Van-e értelme egy ábrázolhatatlan (végtelen kiterjedésű) ábrázolásmódnak? Nos, bizonyos körülmények között mégis lehet értelme (az euklideszi geometriai gyakorlatainkban is egészen elboldogul(t)unk a véges papírral az általános iskolában, noha az ábrázolandó struktúrák végtelen kiterjedésűek voltak), de helyszűke miatt itt és most megelégszünk eme prófétikus „igenis lehet” kijelentéssel és analógiával.

⍰ Gyakorló feladatok:

1. A bástyaprobléma:
   1. Hány bástyát tehetünk maximum egy 8×8-as sakktáblára úgy, hogy ne üssék egymást? Hányféleképp helyezhetjük el a bástyákat?
2. TicTacToe:
   1. A 3×3-as amőba (külföldön: TicTacToe) játékban két játékos, egyikük a 0, másikuk az 1 szimbólummal felváltva próbál kitölteni egy kezdetben üres 3×3-as (illeszkedési) mátrixot. Az a játékos nyer, akinek sikerül a saját szimbólumával először teljesen megtöltenie egy sort, vagy egy oszlopot, vagy egy 3 cella hosszúságú átlót (ilyenből kettő van: a bal felsőtől a jobb alsó sarokig tartó ún. főátló és a bal alsótól a jobb felső sarokig húzódó ún. mellékátló). Fogalmazzuk meg a geometria (az illeszkedési struktúrák) nyelvén, mit jelent, hogy az A játékos (a 0-s) nyer, illetve mit jelent, hogy a B játékos (az 1-eses) nyer, illetve mit jelent, hogy a játék döntetlenre végződik!
3. Vegyünk fel találomra három egyenset és három pontot a síkon, majd készítsük el a kapott incidenciastruktúra illeszkedési mátrixát!
4. Azt mondjuk, hogy egy illeszkedési struktúrának van konzervatív modellje, más néven kanonikus realizációja az euklideszi síkon, ha fel lehet venni egyenesek és pontok (véges v. végtelen) sorozatát úgy, hogy a k-adik egyenes akkor és csak akkor illeszkedik az m-edik pontra a síkon, ha az illeszkedési struktúra k-adik éle illeszkedik az illeszkedési struktúra m-edik pontjára! Azaz, van két bijektív megfeleltetés az illeszkedési struktúra összes egyenese és az euklideszi sík bizonyos egyenesei, illetve a struktúra pontjai és a sík bizonyos pontjai között, amelyek megőrzik az illeszkedési relációt.
   1. Gondoljunk ki olyan incidenciastruktúrát, amelynek nincs konzervatív modellje!
   2. Keressünk két, minél kevesebb (minimális számú) egyenest és pontot tartalmazó illeszkedési struktúrát, amelyeknek nincs konzervatív modellje.
   3. Mi egy elegendő feltétele annak, hogy egy végtelen illeszkedési struktúrának biztos ne legyen konzervatív modellje?
   4. Fogalmazzunk meg annak szükséges és elegendő feltételeit a 3×3-as incidenciamátrixok osztályára, hogy a mátrix által leírt struktúrának a). legyen konzervatív modellje b) ne legyen konzervatív modellje! c). Adott U, I háromelemű halmazok felett hány (továbbra is 3×3-as) struktúra tartozik az a). ill. b). feltételeknek megfelelő alosztályokba?

Izomorfia

Illeszkedéstartó (affin) leképezés

Definíció:

---

Legyen (U₁, E₁, ι₁) és (U₂, E₂, ι₂) két illeszkedési struktúra, továbbá legyen φ:U₁×E₁→U₂×E₂ egy leképezés az elvileg elképzelhető zászlók között. A φ leképezést illeszkedéstartónak vagy szemiaffin(itás)nak mondjuk, ha teljesül a következő tulajdonság tetszőleges x∈D(φ)-re

x∈ι₁ ⇒ φ(x)∈ι₂ .

Ha található két illeszkedési struktúra közt ilyen affin leképezés, akkor a másodikat az elsőhöz (képest) ko-szemiaffinnak mondjuk, vagy, hosszabb kifejezéssel élve, a második struktúrát az első struktúra szemiaffin képének nevezzük.

Ha egy szemiaffinitás egy illeszkedési struktúrát vele azonos típusú struktúrába képez, akkor affin(itás)nak, a struktúrákat pedig koaffinnak mondjuk; vagy, hosszabb kifejezéssel élve, a második struktúrát az első struktúra affin képének nevezzük.

Példák:

---

Izomorfia

Definíció:

---

Legyen (U₁, E₁, ι₁) és (U₂, E₂, ι₂) két illeszkedési struktúra, továbbá legyen φ:U₁×E₁→U₂×E₂ egy leképezés az elvileg elképzelhető zászlók között. A φ leképezést a két struktúra között(i) izomorfizmusnaknak mondjuk, ha teljesül az alábbi három tulajdonság tetszőleges x=(u,i)∈U₁×E₁ elemekre:

1. φ kölcsönösen egyértelmű, azaz bijektív függvény (bijektivitási követelmény);
2. |φ[U₁]| = |E₁| és |φ^-1[E₂]| = |U₁| (típusmegőrzés követelménye)
3. φ szemiaffinitás (illeszkedéstartás követelménye).

Két illeszkedési struktúrát izomorfnak nevezünk, ha található köztük izomorfizmus. Jele (U₁, E₁, ι₁) ≅ (U₂, E₂, ι₂)

Ellenőrizhető, hogy e három axióma független, azaz egyik sem következik a többi közül néhányból. A leggyanúsabb persze a kettes, de könyűszerrel lehet olyan duális (azaz struktúraelméleti értelemben és intuitíve nem izomorf) incidenciastruktúrákat találni, amelyek közt, bár található bijektív affin leképezés, azonban az nem őrzi meg a számosságtípusokat (pl. 3×2-es incidenciamátrixú struktúrából 2×3-asba képez).

Modell

Ehhez kell a primitív osztály (az egymással izomorf i.s. ekvivalenciaosztálya) fogalma.

Definíció:

---

Egy illeszkedési struktúrát az illeszkedési struktúrák egy primitív osztályának modelljének nevezünk, ha a struktúra beletartozik a primitív osztályba.

Legyen n∈N és P_n az n-dimenziós euklideszi tér pontjainak halmaza. Egy ∏ primitív osztály n-dimenziós geometriai reprezentációjának nevezünk egy olyan illeszkedési struktúrát, melynek 1). eleme az osztálynak; 2). csúcsai és élei is P_n részhalmazai 3). az illeszkedési reláció a részhalmazként tartalmazás (esetleg, az eleme reláció).

A ∏ osztály n-dimenziós realizációjának nevezünk egy olyan n-dimenziós geometriai reprezentációt, amelyre igaz, hogy csúcsai az n-dimenzós sík pontjai, élei pedig az n-dimenziós sík egyenesei, az illeszkedési reláció a tartalmazás.

A ∏ osztály konzervatív modelljének vagy kanonikus realizációjának nevezünk egy olyan 2-dimenziós realizációt, amelynek csúcsai a sík pontjai, élei pedig egyenesek, az illeszkedési reláció az ∈.

Függetlenség

Definíció:

---

Legyen (U, E, ι) egy illeszkedési struktúra, ekkor az α,β∈E éleket metszetfüggetlennek mondjuk, ha

α∧β∉E.

Illeszkedési struktúrák és hipergráfok

Fentebb megjegyeztük, hogy egy tetszőleges U halmaz feletti tetszőleges (U, E) hipergráf, ahol E⊆℘(U), felfogható olyan (U, E, ∈) illeszkedési struktúraként, ahol ∈ a halmazelméleti „eleme” reláció; és ennek következménye, hogy minden hipergráfnak megfeleltethető egy illeszkedési struktúra.

Ugyanott utaltunk arra is, hogy ez bizonyos mértékben és megszorításokkal fordítva is igaz, de erről bővebben lentebb.

Minden illeszkedési struktúra értelmez egy hipergráfot. A „hipergráf” és „incidenciastruktúra” fogalmak mégsem azonosak abban az értelemben, ahogy egy halmaz részhalmazai és ezek karakterisztikus függvényei „szinte ugyanazok”. A megfeleltetés ugyanis nem bijektív.

Jegyzetek

---

---

Lap teteje

---