Síla grafu - Graph power

Čtverec grafu

v teorie grafů, obor matematiky, kth síla Gk z neorientovaný graf G je další graf, který má stejnou sadu vrcholy, ale ve kterém dva vrcholy sousedí, když jsou vzdálenost v G je nanejvýšk. Na mocnosti grafů se odkazuje pomocí terminologie podobné té z umocňování čísel: G2 se nazývá náměstí z G, G3 se nazývá krychle z G, atd.[1]

Síly grafu by měly být odlišeny od produkty grafu, který má (na rozdíl od mocnin) obecně mnohem více vrcholů než původní graf.

Vlastnosti

Pokud má graf průměr d, pak jeho d-tá síla je kompletní graf.[2] Pokud je rodina grafů ohraničená šířka kliky, tak to udělejte d-tá síla pro všechny pevné d.[3]

Zbarvení

Barvení grafu na čtverci grafu lze použít k přiřazení frekvencí účastníkům bezdrátových komunikačních sítí tak, aby si žádný ze dvou účastníků vzájemně nerušil žádného ze svých společných sousedů,[4] a najít grafové výkresy s vysokou úhlové rozlišení.[5]

Oba chromatické číslo a zvrhlost z kta síla a rovinný graf maximálního stupně Δ jsou , kde vazba degenerace ukazuje, že a chamtivé zbarvení Algoritmus lze použít k vybarvení grafu tímto mnoha barvami.[4] Pro speciální případ čtverce rovinného grafu předpokládal Wegner v roce 1977, že chromatické číslo čtverce rovinného grafu je nanejvýš a je známo, že chromatické číslo je nanejvýš .[6][7] Obecněji pro jakýkoli graf s degenerací d a maximální stupeň Δ, degenerace čtverce grafu je Ó(dΔ), tolik druhů řídký graf jiné než planární grafy mají také čtverce, jejichž chromatický počet je úměrný Δ.

Ačkoli chromatické číslo čtverce neplanárního grafu s maximálním stupněm Δ může být úměrné Δ2 v nejhorším případě je pro grafy vysoké menší obvod, ohraničený O (Δ2/ log Δ) v tomto případě.[8]

Určení minimálního počtu barev potřebných k vybarvení čtverce grafu je NP-tvrdé, dokonce i v rovinném případě.[9]

Hamiltonicita

Kostka každého připojeného grafu nutně obsahuje a Hamiltonovský cyklus.[10] Není nezbytně nutné, aby čtverec spojeného grafu byl hamiltonián a je tomu tak NP-kompletní k určení, zda je čtverec Hamiltonian.[11] Nicméně tím, že Fleischnerova věta, čtverec a 2-vrchol spojený graf je vždy Hamiltonian.[12]

Výpočetní složitost

The ksíla grafu s n vrcholy a m hrany lze vypočítat v čase O (mn) provedením a šířka první vyhledávání počínaje od každého vrcholu k určení vzdáleností ke všem ostatním vrcholům, nebo o něco rychlejší pomocí sofistikovanějších algoritmů.[13] Alternativně, pokud A je matice sousedství pro graf upravený tak, aby měl na své hlavní úhlopříčce nenulové položky, pak nenulové položky z Ak uveďte matici sousedství kth síla grafu,[14] ze kterého vyplývá, že konstruování kth síly mohou být provedeny v množství času, které je v logaritmickém faktoru času pro násobení matic.

The kth síly stromů lze rozpoznat časově lineárně ve velikosti vstupního grafu.[15]

Vzhledem k grafu je rozhodování, zda jde o druhou mocninu jiného grafu NP-kompletní.[16]Navíc je NP-kompletní určit, zda je graf a ksíla jiného grafu pro dané číslo k ≥ 2, nebo zda se jedná o a kta síla a bipartitní graf, pro k > 2.[17]

Vyvolané podgrafy

K.4 jako poloviční čtverec a krychlový graf

The napůl čtverec a bipartitní graf G je podgrafem G2 vyvolané jednou stranou bipartice G. Mapové grafy jsou poloviční čtverce rovinné grafy,[18] a poloviční krychlové grafy jsou poloviční čtverce hyperkrychlové grafy.[19]

Listové síly jsou podgrafy sil stromů vyvolané listy stromu. A k-leaf power je listová síla, jejíž exponent je k.[20]

Reference

  1. ^ Bondy, Adrian; Murty, USA (2008), Teorie grafů, Postgraduální texty z matematiky, 244, Springer, str. 82, ISBN  9781846289699.
  2. ^ Weisstein, Eric W. „Výkon grafu“. MathWorld.
  3. ^ Todinca, Ioan (2003), „Barvicí síly grafů ohraničené šířky kliky“, Grafově-teoretické pojmy v informatice, Poznámky k přednášce ve Výpočtu. Sci., 2880, Springer, Berlín, str. 370–382, doi:10.1007/978-3-540-39890-5_32, PAN  2080095.
  4. ^ A b Agnarsson, Geir; Halldórsson, Magnús M. (2000), „Barvicí síly rovinných grafů“, Sborník z jedenáctého výročního sympozia ACM-SIAM o diskrétních algoritmech (SODA '00), San Francisco, Kalifornie, USA, str. 654–662.
  5. ^ Formann, M .; Hagerup, T .; Haralambides, J .; Kaufmann, M .; Leighton, F. T.; Symvonis, A .; Welzl, E.; Woeginger, G. (1993), „Kreslení grafů v rovině s vysokým rozlišením“, SIAM Journal on Computing, 22 (5): 1035–1052, doi:10.1137/0222063, PAN  1237161.
  6. ^ Kramer, Florica; Kramer, Horst (2008), „An survey on the distance-colored of graphs“, Diskrétní matematika, 308 (2–3): 422–426, doi:10.1016 / j.disc.2006.11.059, PAN  2378044.
  7. ^ Molloy, Michael; Salavatipour, Mohammad R. (2005), „Vazba na chromatické číslo čtverce rovinného grafu“, Journal of Combinatorial Theory, Řada B, 94 (2): 189–213, doi:10.1016 / j.jctb.2004.12.005, hdl:1807/9473, PAN  2145512.
  8. ^ Alon, Noga; Mohar, Bojan (2002), „Chromatický počet sil grafu“, Kombinatorika, pravděpodobnost a výpočet, 11 (1): 1–10, doi:10.1017 / S0963548301004965, PAN  1888178.
  9. ^ Agnarsson & Halldórsson (2000) vyjmenujte publikace prokazující tvrdost NP pro obecné grafy McCormick (1983) a Lin a Skiena (1995) a pro rovinné grafy Ramanathan a Lloyd (1992, 1993).
  10. ^ Bondy & Murty (2008), str. 105.
  11. ^ Podzemní, Polly (1978), „Na grafech s Hamiltonovými čtverci“, Diskrétní matematika, 21 (3): 323, doi:10.1016 / 0012-365X (78) 90164-4, PAN  0522906.
  12. ^ Diestel, Reinhard (2012), "10. Hamiltonovské cykly", Teorie grafů (PDF) (opraveno 4. elektronické vydání).
  13. ^ Chan, Timothy M. (2012), „All-pair shortest paths for unweighted unirected graphs in čas", Transakce ACM na algoritmech, 8 (4): A34: 1 – A34: 17, doi:10.1145/2344422.2344424, PAN  2981912
  14. ^ Hammack, Richard; Imrich, Wilfried; Klavžar, Sandi (2011), Příručka grafů produktů, Diskrétní matematika a její aplikace (2. vyd.), CRC Press, s. 1. 94, ISBN  9781439813058.
  15. ^ Chang, Maw-Shang; Ko, Ming-Tat; Lu, Hsueh-I (2015), „Algoritmy lineárního času pro problémy s kořeny stromů“, Algorithmica, 71 (2): 471–495, doi:10.1007 / s00453-013-9815-r.
  16. ^ Motwani, R .; Sudan, M. (1994), „Výpočet kořenů grafů je těžký“, Diskrétní aplikovaná matematika, 54: 81–88, doi:10.1016 / 0166-218x (94) 00023-9.
  17. ^ Le, Van Bang; Nguyen, Ngoc Tuy (2010), „Výsledky tvrdosti a efektivní algoritmy pro výkon grafů“, Graficko-teoretické koncepty v informatice: 35. mezinárodní workshop, WG 2009, Montpellier, Francie, 24. – 26. Června 2009, revidované práce, Přednášky v informatice, 5911, Berlín: Springer, s. 238–249, doi:10.1007/978-3-642-11409-0_21, ISBN  978-3-642-11408-3, PAN  2587715.
  18. ^ Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H. (2002), "Mapové grafy", Deník ACM, 49 (2): 127–138, arXiv:cs / 9910013, doi:10.1145/506147.506148, PAN  2147819.
  19. ^ Shpectorov, S. V. (1993), "On scale scale embeddings of graphs into hypercubes", European Journal of Combinatorics, 14 (2): 117–130, doi:10.1006 / eujc.1993.1016, PAN  1206617.
  20. ^ 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.