| dbo:abstract
|
- 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. Tehát a G gráf vastagsága a síkbarajzolható részgráfok minimális száma, melyek uniója kiadja G-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 K9 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 , Thomas Odenthal és Mark Scharbrodt szerezték. (hu)
- 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. Tehát a G gráf vastagsága a síkbarajzolható részgráfok minimális száma, melyek uniója kiadja G-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 K9 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 , Thomas Odenthal és Mark Scharbrodt szerezték. (hu)
|
