Ugrás a tartalomhoz

Gráfhatvány

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából
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, 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öbe G-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

[szerkesztés]

Ha egy gráf átmérője d, 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

[szerkeszté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áf k-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]

Hamilton-körök

[szerkesztés]

Minden összefüggő gráf köbe szükségképpen tartalmaz Hamilton-kört.[10] 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.[11] Mindenesetre a Fleischner-tétel alapján a 2-szeresen csúcsösszefüggő gráfok négyzete mindig tartalmaz Hamilton-kört.[12]

Számítási bonyolultság

[szerkesztés]

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ák k-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áf k-adik hatványa-e bármely k > 2-re.[16]

Feszített részgráfok

[szerkesztés]
K4, a kockagráf páros fele

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

Egy fa levé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

[szerkeszté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.

Jegyzetek

[szerkesztés]
  1. ↑ Bondy, Adrian & Murty, U. S. R. (2008), Graph Theory, vol. 244, Graduate Texts in Mathematics, Springer, p. 82, ISBN 9781846289699, <https://books.google.com/books?id=HuDFMwZOwcsC&pg=PA82>.
  2. ↑ Weisstein, Eric W.: Graph Power (angol nyelven). Wolfram MathWorld
  3. ↑ 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.
  4. ↑ a b Agnarsson, 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.
  5. ↑ Formann, M.; Hagerup, T. & Haralambides, J. et al. (1993), "Drawing graphs in the plane with high resolution", SIAM Journal on Computing 22 (5): 1035–1052, DOI 10.1137/0222063.
  6. ↑ Kramer, Florica & Kramer, Horst (2008), "A survey on the distance-colouring of graphs", Discrete Mathematics 308 (2-3): 422–426, DOI 10.1016/j.disc.2006.11.059.
  7. ↑ Molloy, Michael & Salavatipour, Mohammad R. (2005), "A bound on the chromatic number of the square of a planar graph", Journal of Combinatorial Theory, Series B 94 (2): 189–213, DOI 10.1016/j.jctb.2004.12.005.
  8. ↑ Alon, Noga & Mohar, Bojan (2002), "The chromatic number of graph powers", Combinatorics, Probability and Computing 11 (1): 1–10, DOI 10.1017/S0963548301004965.
  9. ↑ (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).
  10. ↑ (Bondy & Murty 2008), p. 105.
  11. ↑ Underground, Polly (1978), "On graphs with Hamiltonian squares", Discrete Mathematics 21 (3): 323, DOI 10.1016/0012-365X(78)90164-4.
  12. ↑ Diestel, Reinhard (2012), "10. Hamiltonian cycles", Graph Theory (corrected 4th electronic ed.), <http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch10.pdf>.
  13. ↑ Hammack, Richard; Imrich, Wilfried & Klavžar, Sandi (2011), Handbook of Product Graphs (2nd ed.), Discrete Mathematics and Its Applications, CRC Press, p. 94, ISBN 9781439813058, <https://books.google.com/books?id=WiB6UO1nqHAC&pg=PA94>.
  14. ↑ Chang, Maw-Shang; Ko, Ming-Tat & Lu, Hsueh-I (2015), "Linear-Time Algorithms for Tree Root Problems", Algorithmica 71 (2): 471-495, DOI 10.1007/s00453-013-9815-y.
  15. ↑ Motwani, R. & Sudan, M. (1994), "Computing roots of graphs is hard", Discrete Applied Mathematics 54: 81–88, DOI 10.1016/0166-218x(94)00023-9.
  16. ↑ 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.
  17. ↑ Chen, Zhi-Zhong; Grigni, Michelangelo & Papadimitriou, Christos H. (2002), "Map graphs", Journal of the ACM 49 (2): 127–138, DOI 10.1145/506147.506148.
  18. ↑ Shpectorov, S. V. (1993), "On scale embeddings of graphs into hypercubes", European Journal of Combinatorics 14 (2): 117–130, DOI 10.1006/eujc.1993.1016.
  19. ↑ Nishimura, N.; Ragde, P. & Thilikos, D.M. (2002), "On graph powers for leaf-labeled trees", Journal of Algorithms 42: 69–108, DOI 10.1006/jagm.2001.1195.
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Gráfhatvány&oldid=25798482”