Gráfhatvány

Egy gráf négyzete

A matematika, azon belül a gráfelmélet területén egy irányítatlan G gráf k-adik hatványa, G^k egy olyan gráf, melynek csúcskészlete megegyezik az eredeti gráféval, és két csúcsa akkor van éllel összekötve, ha G-beli távolságuk legfeljebb k. A gráfok hatványaira a számok hatványozásához hasonlóan hivatkozunk: G² a négyzete, G³ a köbe G-nek.

A gráfhatványoknak nincs közük a gráfszorzásokhoz, melyek (a hatványoktól eltérően) jellemzően sokkal több csúccsal rendelkeznek, mint az eredeti gráfok.

Tulajdonságai

Ha egy gráf átmérője d, akkor d-edik hatványa teljes gráf. Ha egy gráfcsalád korlátos klikkszélességű, akkor d-edik hatványai is azok, bármely rögzített d értékre.

Színezés

Egy gráf négyzetének színezése segítségével a vezeték nélküli kommunikációs hálózatok felhasználóinak ki lehet úgy osztani frekvenciákat, hogy semelyik két felhasználó ne interferáljon egymással vagy közös szomszédaikkal, továbbá magas szögfelbontású gráflerajzolások keresésére.

Egy Δ maximális fokszámú síkbarajzolható gráf k-adik hatványának kromatikus száma és degeneráltsága is $O({\mathrm{\Delta }}^{\lfloor k/2\rfloor })$, ahol a degeneráltság korlátjából az is látszik, hogy ennyi színnel lehet a gráfot mohó színezési algoritmussal kiszínezni. A síkbarajzolható gráfok négyzetének speciális esetét tekintve, Wegner 1977-es sejtése szerint bármely síkbarajzolható gráf négyzetének kromatikus száma legfeljebb $\max (d+5,\frac{3d}{2}+1)$, az viszont biztos, hogy a kromatikus szám legfeljebb $\frac{5d}{3}+O(1)$. Általánosabban, bármely d degeneráltságú és Δ maximális fokszámú gráf négyzetének degeneráltsága O(dΔ), így a síkgráfokon kívül sok más ritka gráfcsalád kromatikus száma is Δ-val arányos.

Bár a Δ maximális fokszámú, síkba nem rajzolható gráfok négyzetének kromatikus száma legrosszabb esetben Δ²-tel arányos lehet, a magas (6-nál nagyobb) derékbőségű gráfok esetében ez a felső korlát kisebb, O(Δ²/log Δ).

Annak a pontos meghatározása, hogy egy gráf négyzetének színezéséhez minimálisan hány színre van szükség, NP-nehéz, még a síkbarajzolható esetben is.

Hamilton-körök

Minden összefüggő gráf köbe szükségképpen tartalmaz Hamilton-kört. Ez nem feltétlenül igaz az összefüggő gráfok négyzetére, sőt, utóbbiakról NP-teljes feladat eldönteni, hogy hamiltoni-e. Mindenesetre a Fleischner-tétel alapján a 2-szeresen csúcsösszefüggő gráfok négyzete mindig tartalmaz Hamilton-kört.

Számítási bonyolultság

Az n csúccsal és m éllel rendelkező gráf k-adik hatványa O(mn) időben kiszámítható, minden egyes csúcsból kiinduló szélességi kereséssel meghatározva az összes többi csúcstól való távolságot. Ha azonban A a gráf szomszédsági mátrixa, úgy módosítva, hogy a főátlón helyezkedjenek el a nem nulla elemei, akkor az A^k megadja a gráf k-adik hatványának szomszédsági mátrixát, amiből az is következik, hogy a k-adik hatvány kiszámítható a mátrixszorzáshoz szükséges idő logaritmikus faktorában.

Fák k-adik hatványai a bemeneti gráf méretét tekintve lineáris időben felismerhetők.

Annak eldöntése, hogy adott gráf egy másik gráf négyzete-e, NP-teljes. Továbbá annak eldöntése is NP-teljes, hogy egy gráf egy másik gráf k-adik hatványa-e bármely k ≥ 2-re, vagy hogy egy páros gráf k-adik hatványa-e bármely k > 2-re.

Feszített részgráfok

Sablon:Math, a kockagráf páros fele

Egy Sablon:Mvar páros gráf félnégyzete vagy páros fele a Sablon:Math azon részgráfja, amit Sablon:Mvar bipartíciójának egyik fele feszít ki. A térképgráfok a síkbarajzolható gráfok páros felei, a felezett kockagráfok pedig a hiperkockagráfok páros felei.

Egy fa levélhatványai a fa hatványainak a fa levelei által kifeszített részgráfjai. Egy Sablon:Mvar-levélhatvány olyan levélhatvány, melynek kitevője éppen Sablon:Mvar.

Fordítás

• Sablon:Fordítás