síkbeli gráf
Planar graph - gráf. amely lehet ábrázolni a gépen keresztezése nélkül élek. Más szóval, a grafikon sík, ha izomorf sík gráf. azaz, a grafikon látható a síkban úgy, hogy a felső - egy pont a síkban, és az élek - nem metsző görbék rajta. Azok a területek, ahol a grafikon osztja a gépet, az úgynevezett lapján. Korlátlan része a gép - is szembe kell nézniük az úgynevezett külső felületén.
A legegyszerűbb tulajdonságai síkgráfok
Euler-képlet
Egy csatlakoztatott síkbeli gráf a következő összefüggés a csúcsok száma | V (G) | . élek | E (G) | és arcok | F (G) | (Beleértve külső felület):
Euler 1736-ban azt találták [1] a tanulmány tulajdonságainak konvex poliéderek. Ez az összefüggés igaz más felületeken akár egy együtthatóval, az úgynevezett Euler jellemző. Ez állandó felületű, sík vagy gömb van kettő, de például egy tórusz felülete - nulla.
A képlet sok hasznos hatása. Először is, az összes lakás stack egy grafikon azonos arcok száma. Másodszor, ha az egyes arc határolja legalább három bordát (feltéve, hogy az oszlopban több mint két széle), és minden borda választja el a két arcot. az
azaz, nagyobb számú élek egy grafikon ismert síkba eső. Az ellenkezője nem igaz: mint egy ellenpélda is eltarthat a Petersen gráf. Ebből következik, hogy egy sík gráf mindig talál egy csúcsából foka legfeljebb 5.
Az általános képlet is könnyen általánosítható az esetben egy szétkapcsolt grafikon:
ahol | C (G) | - száma csatlakoztatott komponensek a gráfban.
Két példa nem-síkgráfok
Teljes gráf öt csúcsot
Az első algoritmus megállapítja Kuratowski részgráfot lineáris időben kifejlesztett 1974-ben, Hopcroft Tarjanne [2].
Jelei nem síkgráfok
- elégséges feltétele - ha a gráf tartalmaz teljes páros gráf K3,3 vagy K5 teljes részgráf. ez nem planáris;
- szükséges feltétele - ha nem síkbeli gráf, annak tartalmaznia kell több, mint négy csúcsa mértékben több, mint 3 vagy nagyobb, mint 5 csúcsú mértéke nagyobb, mint 2.
Síkgráfok problémákat
Színezés kártyákat. Azt akarom festeni egy sima térkép egy adott színek száma úgy, hogy minden két ország közös határ, hogy a különböző színeket. Úgy tűnik, hogy a távollétében enklávék. Mindig elég négy szín, de ez az állítás rendkívül nehéz bizonyítani, lásd. a négy szín tétel.
Helyesbítés grafikon (Fary tétel). Bármely síkbeli gráf lehet rajzolni úgy, hogy lapos marad, és az élek válnak egyenes szakaszok.
Earl kerül a felületre, ha meg tudja felhívni rá keresztezése nélkül élek. Laid grafikonon az úgynevezett geometriai. A csúcs - egy pont a felszínen, és a széleket - a vonal rajta. Azok a területek, ahol a grafikon tör a felszínre, az úgynevezett arcok. Planar graph - gráf fektetve egy repülőgép.