A matematika, azon belül a gráfelmélet területén egy irányítatlanGgráfk-adik hatványa, Gk 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: G2 a négyzete, G3 a köbeG-nek.[1]
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őjed, akkor d-edik hatványa teljes gráf.[2] 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.[3]
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,[4] továbbá magas szögfelbontásúgráflerajzolások keresésére.[5]
Egy Δ maximális fokszámú síkbarajzolható gráfk-adik hatványának kromatikus száma és degeneráltsága is , 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.[4] 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 , az viszont biztos, hogy a kromatikus szám legfeljebb .[6][7] Á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 Δ2-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(Δ2/log Δ).[8]
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.[9]
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 Ak megadja a gráf k-adik hatványának szomszédsági mátrixát,[13] 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ákk-adik hatványai a bemeneti gráf méretét tekintve lineáris időben felismerhetők.[14]
Annak eldöntése, hogy adott gráf egy másik gráf négyzete-e, NP-teljes.[15]
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áfk-adik hatványa-e bármely k > 2-re.[16]
Egy falevélhatványai a fa hatványainak a fa levelei által kifeszített részgráfjai. Egy k-levélhatvány olyan levélhatvány, melynek kitevője éppen k.[19]
Fordítás
Ez a szócikk részben vagy egészben a Graph power című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
↑Todinca, Ioan (2003), "Coloring powers of graphs of bounded clique-width", Graph-theoretic concepts in computer science, vol. 2880, Lecture Notes in Comput. Sci., Springer, Berlin, pp. 370–382, DOI 10.1007/978-3-540-39890-5_32.
↑ abAgnarsson, Geir & Halldórsson, Magnús M. (2000), "Coloring powers of planar graphs", Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00), San Francisco, California, USA, pp. 654–662.
↑(Agnarsson & Halldórsson 2000) list publications proving NP-hardness for general graphs by McCormick (1983) and Lin and Skiena (1995), and for planar graphs by Ramanathan and Lloyd (1992, 1993).
↑Le, Van Bang & Nguyen, Ngoc Tuy (2010), "Hardness results and efficient algorithms for graph powers", Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009, Revised Papers, vol. 5911, Lecture Notes in Computer Science, Berlin: Springer, pp. 238–249, ISBN 978-3-642-11408-3, DOI 10.1007/978-3-642-11409-0_21.