Síkbarajzolhatóság - ha egy gráf lerajzolható a síkba úgy, hogy az élei ne messék egymást, akkor a gráf síkbarajzolható
- a síkbarajzolt gráf a síkot tartományokra osztja
Tétel: [Euler-formula]: egy összefüggő síkbeli gráf, amelynek n csúcsa, e éle és t tartománya van (beleértve a külső, nem korlátos tartományt is ), eleget tesz az Euler formulának: n - e + t = 2
Tétel: Ha G egyszerű, síkbarajzolható gráf és pontjainak száma 3, akkor az előbbi jelöléssekkel e <= 3n - 6
Kuratowski-gráfok:
Tétel: A Kuratowski-gráfok nem síkbarajzolhatóak
- egy gráf síkbarajzolhatóságát nem befojásolja, ha egy élet 2 hosszú úttal helyettesítünk, azaz egy élet egy új 2 fokú csúcs felvételével két élre bontunk, vagy ha egy 2 fokú csúcsra illeszkedő éleket egybeolvasztjuk
- a G és H gráfok topológikusan izomorfak, ha a fent említett tranzformációk ismételt alkalmazásával izomorf gráfokba tranzformáljuk őket
Tétel [Kuratowski]: egy gráf akkor és csak akkor síkbarajzolható, ha nem tartalmaz olyan részgráfot, amely topológikusan izomorf K3,3-mal vagy K5-tel
Tétel: [Fáry-Wágner]: ha G egy egyszerű, síkbarajzolható gráf, akkor létezik olyan síkbeli ábrázolása is, hogy minden élet egy egyenes szakasszal rajzolunk le
Szerzők: GospeLL,
[Szócikk szerkesztése]
[Lexikon kezdőlapra lépés]
|
