Koronagráf (gráfelmélet)
Sablon:Gráf infobox A matematika, azon belül a gráfelmélet területén egy koronagráf 2n csúccsal rendelkező irányítatlan gráf, melynek csúcsai az {u1, u2, ..., un}, illetve a {v1, v2, ..., vn} halmazba tartoznak, élek pedig ui és vj között húzódnak, amennyiben i ≠ j.
A koronagráf felfogható olyan teljes páros gráfként, melyből egy teljes párosítás éleit eltávolították, egy teljes gráf páros dupla fedéseként, a Kn × K2 tenzorszorzatként, a Kn és K2 Descartes-szorzatának komplementereként vagy a Hn,1 páros Kneser-gráfként, melynek csúcsait az n elemű halmaz 1-, illetve (n − 1) elemű részhalmazai alkotnak, két részhalmazt jelképező csúcsok között pedig akkor húzódik él, ha az egyik részhalmaz tartalmazza a másikat.
Példák
A 6 csúcsú koronagráf kört alkot, a 8 csúcsú izomorf a kockagráffal. A Schläfli-féle dupla hatos a térben 12 egyenesből és 30 pontból álló konfiguráció, melynek tizenkét egyenesének metszéspontjai egy tizenkét csúcsból álló koronagráf mintázatát adják ki.
Tulajdonságok
A koronagráf éleinek száma az n(n − 1) téglalapszám. Akromatikus száma n: egy teljes színezés előállítható az egyes {ui, vi} párokat választva egy-egy színosztálynak.Sablon:Sfnp A koronagráfok szimmetrikusak és távolságtranzitívak. Sablon:Harvtxt leírja a koronagráf éleinek egyenlő hosszúságú körökbe particionálását.
A 2n csúcsú koronagráf beágyazható a négydimenziós euklideszi térbe úgy, hogy minden éle egységnyi hosszúságú szakasz legyen. Ezzel a beágyazással azonban egymással nem szomszédos csúcsok is egységnyi távolságra kerülhetnek. Olyan beágyazáshoz, ahol az élek egységnyi távolságra vannak, a nem-élek pedig nem, legalább n − 2 dimenzióra van szükség. Ez a példa is mutatja, hogy nagyon különböző számú dimenzióra lehet szükség egy gráf egységtávolsággráfként és szigorú egységtávolsággráfként való ábrázolásához.Sablon:Sfnp
A koronagráf éleinek lefedéséhez szükséges teljes páros részgráfok minimális száma (páros dimenziója, avagy minimális páros dupla fedésének mérete)
ami a központi binomiális együttható inverz függvénye.Sablon:Sfnp
A 2n csúcsú koronagráf komplementer gráfja a K2 Kn Descartes-szorzattal, illetve a 2 × n-es bástyagráffal egyezik meg.
Alkalmazásai
Az etikett hagyományos szabálya szerint az ebédlőasztalnál a vendégeket úgy ültetik le, hogy a férfiak és nők váltakozva üljenek, de házaspárok ne kerüljenek egymás mellé. Ha egy fogadás résztvevői éppen n házaspárból állnak, akkor a követelményeknek megfelelő elrendezések épp egy koronagráf Hamilton-köreiként írhatók le. Az ilyen elrendezések leszámlálását, vagy ami ezzel csaknem ekvivalens,[1] a koronagráf Hamilton-köreinek megszámolását nevezik a kombinatorikában ültetési problémának (ménage problem); a 6, 8, 10, ... csúcsból álló koronagráfokra az (irányított) Hamilton-körök száma:
- 2, 12, 312, 9600, 416880, 23879520, 1749363840, ... Sablon:OEIS
A koronagráfok jó példát szolgáltatnak arra, hogy a mohó színezési algoritmusok milyen rosszul is viselkedhetnek: ha a koronagráf csúcsait az algoritmus u0, v0, u1, v1 stb. sorrendben kapja meg, akkor a mohó színezés n színt használ el, miközben a színek optimális száma mindössze kettő. Ezt a konstrukciót Sablon:Harvtxt-nak tulajdonítják, ezért néha a koronagráfokat Johnson gráfjainak (Johnson’s graphs) is nevezik, Jn jelöléssel.Sablon:Sfnp Sablon:Harvtxt a koronagráfokat színezési problémák approximációjának nehézségét megmutató konstrukciójának részeként használta fel.
Sablon:Harvtxt a koronagráfokbeli távolságokat olyan metrikus térre hozza példának, ami nehezen beágyazható egy normált térbe.
Ahogy Sablon:Harvtxt megmutatja, a koronagráfok a távolságreguláris cirkuláns gráfok kevés különböző típusának egyikét alkotják.
Sablon:Harvtxt olyan sokszögeket írnak le, melyek láthatósági gráfjaiként koronagráfok szerepelnek; ezzel a példával mutatva be, hogy a láthatósági gráfok teljes páros gráfok uniójaként való ábrázolása nem minden esetben helytakarékos.
Egy 2n csúcsú koronagráf éleinek a bipartíció egyik felétől a másik felé irányításával tankönyvi példáját adja egy n részbenrendezési dimenziójú (szélességű) részbenrendezett halmaznak.
Jegyzetek
Fordítás
Források
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation
- Sablon:Citation
- Sablon:Citation.
- Sablon:Citation.
További információk
- ↑ Az ültetési problémában a kör kezdőpontját is számításba veszik, ezért az ültetési probléma megoldása és a Hamilton-körök száma egy 2n-es szorzótényezőben eltérnek.