Vastagság (gráfelmélet)

A Wikipédiából, a szabad enciklopédiából

A matematika, azon belül a gráfelmélet területén egy G gráf vastagsága (thickness) a síkbarajzolható gráfok minimális száma, amibe G élei particionálhatók. Tehát, ha létezik ugyanazon a csúcshalmazon k síkbarajzolható gráf, melyek uniója G, akkor G vastagsága legfeljebb k.[1][2] Tehát a G gráf vastagsága a síkbarajzolható részgráfok minimális száma, melyek uniója kiadja G-t.[3] Egy síkgráf vastagsága tehát 1. A 2 vastagságú gráfokat biplanáris gráfoknak (biplanar graphs) is nevezik. A vastagság fogalmát Frank Harary egy 1962-es sejtésében vezette be: eszerint bármely 9 csúcsú gráfra igaz, hogy vagy ő, vagy komplementere nem síkba rajzolható. A probléma ekvivalens azzal a felvetéssel, hogy a K9 teljes gráf biplanáris-e (nem az, és a sejtés igaz).[4] A gráfvastagság terén az 1998-as állapotokat részletesen szemléző[3] cikket Petra Mutzel, Thomas Odenthal és Mark Scharbrodt szerezték.[5]

Specifikus gráfok[szerkesztés]

A Kn teljes gráf vastagsága

kivéve az n = 9, 10 esetet, akkor három.[6][7]

Néhány kivétellel a Ka,b teljes páros gráf vastagsága:

[8][9]

A hiperkockagráf vastagsága:

Kapcsolódó problémák[szerkesztés]

Minden erdő síkgráf, és minden síkgráf legfeljebb három erdőre particionálható. Így tehát bármely G gráf vastagsága legfeljebb ugyanazon gráf arboricitásával (az erdők számával, melybe particionálható), legalább az arboricitás harmadával egyenlő.[2][10] G vastagsága konstans faktorra van egy másik gyakran használt gráfinvariánssal, a degeneráltsággal is, ami G összes részgráfjában a fokszám minimális értékeinek a maximuma. Ha egy n csúcsú gráf vastagsága t, akkor legfeljebb t(3n − 6) éle lehet, tehát degeneráltsága is legfeljebb 6t − 1. A másik irányban, ha egy gráf degeneráltsága D, akkor arboricitása és vastagsága is legfeljebb D.

A vastagság közeli kapcsolatban van a szimultán beágyazás problémájával.[11] Ha két vagy több síkbarajzolható gráf csúcshalmazai megegyeznek, akkor lehetséges ezen gráfok egyidejű síkbaágyazása oly módon, hogy az élek görbe vonalúak (a csúcsok pedig megegyeznek). Ez nem feltétlenül lehetséges az élek egyenes szakaszokkal történő lerajzolásakor.

Egy másik gráfinvariáns, a G gráf egyenes vonalú vastagsága, rektilineáris vastagsága vagy mértani vastagsága (rectilinear thickness, geometric thickness) meghatározza a síkbarajzolható gráfok legkisebb számát, melyekbe G oly módon felosztható, hogy a gráfok szimultán módon, egyenes vonalakkal lerajzolhatók legyenek. A könyvvastagság további megszorítással él, miszerint az összes csúcsnak konvex helyzetben kell lennie, körkörös elrendezést alkotva. Az arboricitástól és a degeneráltságtól eltérően ezek az invariánsok egyike sincsen konstans faktorra a másiktól.[12]

Számítási bonyolultság[szerkesztés]

Adott gráf vastagságának meghatározása NP-nehéz, annak meghatározása, hogy a vastagság legfeljebb kettő, NP-teljes.[13] Az arboricitással való kapcsolat miatt azonban a gráf vastagsága 3 közelítési aránnyal polinom időben meghatározható.

Fordítás[szerkesztés]

  • Ez a szócikk részben vagy egészben a Thickness (graph theory) 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.

Kapcsolódó szócikkek[szerkesztés]

Jegyzetek[szerkesztés]

  1. ↑ Tutte, W. T. (1963), "The thickness of a graph", Indag. Math. 25: 567–577.
  2. ↑ a b Mutzel, Petra; Odenthal, Thomas & Scharbrodt, Mark (1998), "The thickness of graphs: a survey", Graphs and Combinatorics 14 (1): 59–73, DOI 10.1007/PL00007219.
  3. ↑ a b Christian A. Duncan, On Graph Thickness, Geometric Thickness, and Separator Theorems, CCCG 2009, Vancouver, BC, August 17–19, 2009
  4. ↑ (2012) „An Annotated Bibliography on the Thickness, Outerthickness, and Arboricity of a Graph”. Missouri J. Math. Sci. 24 (1), 76–87. o.  
  5. ↑ Petra Mutzel, Thomas Odenthal and Mark Scharbrodt, The Thickness of Graphs: A Survey
  6. ↑ (Mutzel, Odenthal & Scharbrodt 1998), Theorem 3.2.
  7. ↑ Alekseev, V. B. & Gončakov, V. S. (1976), "The thickness of an arbitrary complete graph", Mat. Sb. (N.S.) 101 (143): 212–230.
  8. ↑ (Mutzel, Odenthal & Scharbrodt 1998), Theorem 3.4.
  9. ↑ Beineke, Lowell W.; Harary, Frank & Moon, John W. (1964), "On the thickness of the complete bipartite graph", Proc. Cambridge Philos. Soc. 60: 1–5, DOI 10.1017/s0305004100037385.
  10. ↑ Dean, Alice M.; Hutchinson, Joan P. & Scheinerman, Edward R. (1991), "On the thickness and arboricity of a graph", Journal of Combinatorial Theory, Series B 52 (1): 147–151, DOI 10.1016/0095-8956(91)90100-X.
  11. ↑ Brass, Peter; Cenek, Eowyn & Duncan, Cristian A. et al. (2007), "On simultaneous planar graph embeddings", Computational Geometry 36 (2): 117–130, DOI 10.1016/j.comgeo.2006.05.006.
  12. ↑ Eppstein, David (2004), "Separating thickness from geometric thickness", Towards a theory of geometric graphs, vol. 342, Contemp. Math., Amer. Math. Soc., Providence, RI, pp. 75–86, DOI 10.1090/conm/342/06132.
  13. ↑ Mansfield, Anthony (1983), "Determining the thickness of graphs is NP-hard", Mathematical Proceedings of the Cambridge Philosophical Society 93 (1): 9–23, DOI 10.1017/S030500410006028X.
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Vastagság_(gráfelmélet)&oldid=19502176”