Planär graf

Exempel
PlanärIcke planär

Fjärilsgraf

Den kompletta grafen K5

Den kompletta grafen
K4

Den bipartita grafen K3,3

Inom grafteori är en planär graf en graf som kan bäddas in i planet, det vill säga ritas på planet på ett sådant sätt att kanterna inte skär varandra, utan bara möts i noderna.[1] En sådan avbildning kallas en plan graf eller planär inbäddning av grafen. En plan graf kan definieras som en planär graf med en avbildning av varje nod till en punkt i planet, och från varje kant till en plan kurva i planet, så att varje kurvas ändpunkter är de punkter som avbildas av kantens ändnoder och så att alla kurvor är disjunkta utom i ändpunkterna.

Varje graf som kan avbildas på ett plan kan avbildas på en sfär och vice versa.

En generalisering av planära grafer är grafer som kan ritas på en yta av ett givet genus. Med denna terminologi har planära grafer grafgenus 0, eftersom planet (och sfären) har genus 0.

Kuratowskis och Wagners satser

Den polske matematikern Kazimierz Kuratowski bidrog med en karakterisering av planära grafer byggd på två förbjudna grafer, vilket nu är känt som Kuratowskis sats:

En ändlig graf är planär om och endast om den inte innehåller en delgraf som är en subdivision av K5 (den kompletta grafen över fem noder) eller K3,3 (den kompletta bipartita grafen över sex noder, så att tre av dem är förbundna med de andra tre).

En subdivision av en graf bildas om man sätter in noder i kanter (till exempel ändrar kanten •——• till •—•—•) noll eller flera gånger.

I stället för att betrakta subdivisioner behandlar Wagners sats minora av grafer:

En ändlig graf är planär om och endast om den inte har K5 eller K3,3 som en minor.

En minor bildas ur en graf genom kantkontraktion (att ta bort en kant genom att "smälta samman" dess två ändnoder).

Ett exempel på en graf som inte har K5 eller K3,3 som delgraf. Den har däremot en subgraf som är en subdivision av K3,3 (noden B har "satts in" i kanten CF), eller en minor till K3,3 ("sammanför" B och C till en nod), och är därför inte planär.
En animation som visar att Petersengrafen innehåller en delgraf som är en minor, vilken är isomorf med K3,3 (dessutom har Petersengrafen en även en minor som är isomorf med K5 - smält samman 0 med 5, 1, med 6,..., 4 med 9).

Andra kriterier för planaritet

I praktiken är det svårt att använda Kuratowskis kriterium för att snabbt avgöra om en graf är planär. Det finns dock snabba algoritmer för att lösa problemet: för en graf med n noder är det möjligt att avgöra i linjär tid O(n) huruvida en graf kan vara planär eller ej.

För en enkel sammanhängande planär graf med v noder och e kanter gäller följande enkla förhållanden:

Sats 1. Om v ≥ 3 så är e ≤ 3v − 6;
Sats 2. Om v ≥ 3 och det inte finns några cykler av längd 3, så är e ≤ 2v − 4.

I den här meningen är planära grafer glesa grafer eftersom de bara har O(v) kanter och blir asymptotiskt mindre än det maximala O(v2). Grafen K3,3 har exempelvis sex noder och nio kanter och inga cykler av längd tre. Därför kan den enligt sats 2 inte vara planär. Märk att dessa satser ger nödvändiga, men inte tillräckliga, förutsättningar för planaritet och därför bara kan användas för att visa att en graf inte är planär. Om varken sats 1 eller 2 ger ett svar, får man använda andra metoder.

Eulers formel

Eulers formel säger att om en oändlig sammanhängande planär graf ritas i planet utan att några kanter skär varandra och v är antalet noder, e antalet kanter och f antalet "sidor" (områden begränsade av kanter, inklusive den oändligt stora ytan som omger grafen) så gäller

ve + f = 2.

Som ett exempel kan vi ta fjärilsgrafen ovan: v = 5, e = 6 och f = 3. Detta gäller allmänt för alla planära grafer med f sidor, varje förändring av grafen som skapar en ny sida kommer inte att förändra v − e + f. Eftersom egenskapen gäller för alla grafer med f = 2, ger induktion att det gäller för alla andra fall. Eulers formel kan också visas enligt: Om grafen inte är ett träd, så avlägsna en kant som fullbordar en cykel. Detta sänker både e och f med ett och lämnar ve + f konstant. Upprepa tills den kvarvarande grafen är ett träd. Träd har v =  e + 1 och f = 1, vilket ger v − e + f = 2. Det vill säga Eulerkarakteristiken är 2.

I en ändlig, sammanhängande, enkel och planär graf avgränsas varje sida (utom möjligtvis den yttre) av minst tre kanter och varje kant vidrör högst två sidor. Genom att använda Eulers formel kan man visa att dessa är glesa i meningen att e ≤ 3v − 6 om v ≥ 3.

Ett Schlegeldiagram av en regelbunden dodekaeder som avbildar en konvex polyeder som en planär graf.

Eulers formel gäller också för konvexa polyedrar. Detta är ingen tillfällighet, eftersom varje konvex polyeder kan avbildas på en sammanhängande enkel planär graf medelst ett Schlegeldiagram - en avbildning ("projektion") av polyedern på ett plan med centrum valt nära centrum av en av polyederns sidor. Alla planära grafer motsvaras inte av en polyeder på detta sätt, exempelvis inte träd. Eulers formel gäller för alla polyedrar vars ytor är enkla polygoner som skapar en yta som är topologiskt ekvivalent med en sfär oavsett dess konvexitet.

Medelgrad

Av ve + f = 2 och (en yta har minst tre kanter och varje kant har maximalt två ytor) följer att medelgraden är strikt mindre än sex. I annat fall kan en given graf inte vara planär.

Referenser

  1. ^ Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication.). New York: Dover Pub. sid. 64. ISBN 978-0-486-67870-2. http://store.doverpublications.com/0486678709.html. Läst 8 augusti 2012. ”Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them.” 

Media som används på denna webbplats

Butterfly graph.svg
Författare/Upphovsman: Koko90, Licens: CC BY-SA 3.0
The Butterfly graph. Layout from ISGCI (Information System on Graph Class Inclusions), List of small graphs (http://www.graphclasses.org/smallgraphs.html).
Biclique K 3 3.svg
Författare/Upphovsman: Koko90, Licens: CC BY-SA 3.0
The complete bipartite graph K3,3.
Kuratowski.gif
Författare/Upphovsman: Pablo Angulo using Sage software, Licens: CC BY 3.0
Animation showing how the Petersen graph contains a minor isomorphic to K3,3. An Illustration of Wagner's theorem. Created with Sage
Dodecahedron schlegel.svg
Författare/Upphovsman: Jooja, Licens: CC BY-SA 3.0
Created with Inkscape
Planar no subgraph k33.JPG
Författare/Upphovsman: Ingen maskinläsbar skapare angavs. Arunachalam.t~commonswiki antaget (baserat på upphovsrättsanspråk)., Licens: CC BY-SA 2.5
This is an example for a Non Planar graph that doesn't have K3,3 or K5 as its subgraph. But this graph has a subgraph homeomorphic to K3,3.
K4 planar.svg
Författare/Upphovsman:
Original:
MlaWU
Vektor:
, Licens: GFDL
planare Zeichnung des K4