Vastagság (gráfelmélet)

A matematika, azon belül a gráfelmélet területén egy Sablon:Mvar gráf vastagsága (thickness) a síkbarajzolható gráfok minimális száma, amibe Sablon:Mvar élei particionálhatók. Tehát, ha létezik ugyanazon a csúcshalmazon Sablon:Mvar síkbarajzolható gráf, melyek uniója Sablon:Mvar, akkor Sablon:Mvar vastagsága legfeljebb Sablon:Mvar. Tehát a Sablon:Mvar gráf vastagsága a síkbarajzolható részgráfok minimális száma, melyek uniója kiadja Sablon:Mvar-t. 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 Sablon:Math teljes gráf biplanáris-e (nem az, és a sejtés igaz). A gráfvastagság terén az 1998-as állapotokat részletesen szemléző cikket Petra Mutzel, Thomas Odenthal és Mark Scharbrodt szerezték.

Specifikus gráfok

A Sablon:Mvar teljes gráf vastagsága

$\lfloor \frac{n+7}{6}\rfloor ,$

kivéve az Sablon:Math esetet, akkor három.

Néhány kivétellel a Sablon:Mvar teljes páros gráf vastagsága:

$\lceil \frac{ab}{2(a+b-2)}\rceil .$

A hiperkockagráf vastagsága:

$t(Q_n)=\lceil \frac{n+1}{4}\rceil .$

Kapcsolódó problémák

Minden erdő síkgráf, és minden síkgráf legfeljebb három erdőre particionálható. Így tehát bármely Sablon:Mvar 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ő. Sablon:Mvar vastagsága konstans faktorra van egy másik gyakran használt gráfinvariánssal, a degeneráltsággal is, ami Sablon:Mvar összes részgráfjában a fokszám minimális értékeinek a maximuma. Ha egy Sablon:Mvar csúcsú gráf vastagsága t, akkor legfeljebb Sablon:Math éle lehet, tehát degeneráltsága is legfeljebb Sablon:Math. A másik irányban, ha egy gráf degeneráltsága Sablon:Mvar, akkor arboricitása és vastagsága is legfeljebb Sablon:Mvar.

A vastagság közeli kapcsolatban van a szimultán beágyazás problémájával. 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 Sablon:Mvar 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 Sablon:Mvar 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.

Számítási bonyolultság

Adott gráf vastagságának meghatározása NP-nehéz, annak meghatározása, hogy a vastagság legfeljebb kettő, NP-teljes. 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

• Sablon:Fordítás

Kapcsolódó szócikkek

• 1-síkbarajzolható gráf