Tloušťka (teorie grafů) - Thickness (graph theory)

v teorie grafů, tloušťka grafu G je minimální počet rovinné grafy do kterého jsou hrany G lze rozdělit. To znamená, že pokud existuje sbírka k rovinné grafy, všechny se stejnou sadou vrcholů, takže svaz těchto rovinných grafů je G, pak tloušťka G je nanejvýš k.[1][2] Jinými slovy, tloušťka grafu je minimální počet rovinných ploch podgrafy jehož unie se rovná grafu G.[3]

Tak má rovinný graf tloušťku 1. Jsou volány grafy tloušťky 2 biplanární grafy. Koncept tloušťky pochází z dohadu z roku 1962 Frank Harary: Pro jakýkoli graf o 9 bodech, buď sám, nebo jeho doplňkový graf je nerovinný. Problém je rovnocenný s určením, zda kompletní graf K.9 je biplanární (není, a domněnka je pravdivá).[4] Komplexní[3] průzkum o stavu umění tématu od roku 1998 napsal Petra Mutzel, Thomas Odenthal a Mark Scharbrodt.[5]

Konkrétní grafy

Tloušťka kompletní graf na n vrcholy, K.n, je

kromě případů, kdy n = 9, 10 pro které jsou tloušťky tři.[6][7]

Až na několik výjimek byla tloušťka a kompletní bipartitní graf K.a, b je obecně:[8][9]

Související problémy

Každý les je rovinný a každý rovinný graf lze rozdělit na nejvýše tři lesy. Proto tloušťka libovolného grafu G je maximálně rovna arboricita stejného grafu (minimální počet lesů, do kterých lze rozdělit) a alespoň rovný arboricitě dělené třemi.[2][10] Tloušťka G je také v rámci stálých faktorů jiného standardu graf neměnný, zvrhlost, definováno jako maximum, přes podgrafy G, minimálního stupně v podgrafu. Pokud n-vertexový graf má tloušťku t pak to nutně má nanejvýš t(3n − 6) hrany, ze kterých vyplývá, že její degenerace je nanejvýš 6t − 1. V opačném směru, pokud má graf degeneraci D pak má nanejvýš arboricitu a tloušťku D.

Tloušťka úzce souvisí s problémem současné vkládání.[11] Pokud dva nebo více rovinných grafů sdílejí stejnou sadu vrcholů, je možné vložit všechny tyto grafy do roviny s hranami nakreslenými jako křivky, takže každý vrchol má ve všech různých výkresech stejnou pozici. Je však možné, že nebude možné zkonstruovat takovou kresbu, zatímco okraje zůstanou rovné úsečky.

Jiný invariant grafu je přímočará tloušťka nebo geometrická tloušťka grafu G, spočítá nejmenší počet rovinných grafů, do kterých G lze rozložit s omezením, že všechny tyto grafy lze kreslit současně s rovnými hranami. The tloušťka knihy přidává další omezení, aby byly nakresleny všechny vrcholy konvexní pozice, tvořící a kruhové rozložení grafu. Na rozdíl od situace pro arboricitu a degeneraci však žádné dva z těchto tří parametrů tloušťky nejsou vždy v konstantním faktoru.[12]

Výpočetní složitost

to je NP-tvrdé vypočítat tloušťku daného grafu a NP-kompletní otestovat, zda je tloušťka nejvýše dvě.[13] Spojení s arboricitou však umožňuje aproximovat tloušťku uvnitř přibližný poměr ze 3 palců polynomiální čas.

Reference

  1. ^ Tutte, W. T. (1963), „Tloušťka grafu“, Indag. Matematika., 25: 567–577, PAN  0157372.
  2. ^ A b Mutzel, Petra; Odenthal, Thomas; Scharbrodt, Mark (1998), „Tloušťka grafů: průzkum“, Grafy a kombinatorika, 14 (1): 59–73, doi:10.1007 / PL00007219, PAN  1617664.
  3. ^ A b Christian A. Duncan, O tloušťce grafu, geometrické tloušťce a větách oddělovače „CCCG 2009, Vancouver, BC, 17. – 19. Srpna 2009
  4. ^ Mäkinen, Erkki; Poranen, Timo (2012). „Komentovaná bibliografie o tloušťce, vnější tloušťce a arboricitě grafu“. Missouri J. Math. Sci. 24 (1): 76–87.
  5. ^ Petra Mutzel, Thomas Odenthal a Mark Scharbrodt, Tloušťka grafů: Průzkum
  6. ^ Mutzel, Odenthal & Scharbrodt (1998), Věta 3.2.
  7. ^ Alekseev, V. B .; Gončakov, V. S. (1976), „Tloušťka libovolného úplného grafu“, Rohož. Sb. (N.S.), 101 (143): 212–230, PAN  0460162.
  8. ^ Mutzel, Odenthal & Scharbrodt (1998), Věta 3.4.
  9. ^ Beineke, Lowell W.; Harary, Franku; Moon, John W. (1964), „Na tloušťce celého bipartitního grafu“, Proc. Cambridge Philos. Soc., 60: 1–5, doi:10.1017 / s0305004100037385, PAN  0158388.
  10. ^ Dean, Alice M .; Hutchinson, Joan P.; Scheinerman, Edward R. (1991), „O tloušťce a arboricitě grafu“, Journal of Combinatorial Theory, Řada B, 52 (1): 147–151, doi:10.1016 / 0095-8956 (91) 90100-X, PAN  1109429.
  11. ^ Brass, Peter; Cenek, Eowyn; Duncan, Cristian A .; Efrat, Alon; Erten, Cesim; Ismailescu, Dan P .; Kobourov, Stephen G .; Lubiw, Anna; Mitchell, Joseph S. B. (2007), „O simultánním vkládání rovinných grafů“, Výpočetní geometrie, 36 (2): 117–130, doi:10.1016 / j.comgeo.2006.05.006, PAN  2278011.
  12. ^ Eppstein, David (2004), „Oddělení tloušťky od geometrické tloušťky“, Směrem k teorii geometrických grafů, Contemp. Matematika., 342, Amer. Matematika. Soc., Providence, RI, str. 75–86, arXiv:matematika / 0204252, doi:10.1090 / conm / 342/06132, PAN  2065254.
  13. ^ Mansfield, Anthony (1983), „Určení tloušťky grafů je NP-tvrdé“, Mathematical Proceedings of the Cambridge Philosophical Society, 93 (1): 9–23, doi:10.1017 / S030500410006028X, PAN  0684270.