Subgrafuri și grafuri planare

Un graf parțial păstrează toate vârfurile și elimină unele muchii. Un subgraf se obține alegând vârfuri și păstrând toate muchiile grafului inițial dintre ele; când elimini un vârf, dispar și muchiile sale incidente. Un graf este planar dacă poate fi desenat fără încrucișări ale muchiilor în alte puncte decât vârfurile comune. Un desen încurcat nu dovedește neplanaritatea: poți muta vârfurile și redesena muchiile.

Exemplu pas cu pas: din triunghiul cu muchiile $AB,BC,CA$, păstrezi toate vârfurile și elimini $CA$; obții un graf parțial, lanțul $A-B-C$. Dacă elimini vârful $C$, dispar muchiile $BC$ și $CA$, iar subgraful pe $\{A,B\}$ păstrează muchia $AB$.

Pentru un graf planar conex desenat fără încrucișări, relația lui Euler este $V-M+F=2$, unde $F$ numără și fața exterioară. Un graf complet $K_n$ are muchie între oricare două vârfuri distincte, deci $M=n(n-1)/2$.

Exemplu lucrat pentru $K_4$: (1) Pui trei vârfuri pe conturul unui triunghi și al patrulea în interior. (2) Unești vârful interior cu toate cele trei vârfuri ale conturului: ai $V=4$, $M=6$. (3) Numări trei fețe interioare și fața exterioară, deci $F=4$. (4) Verifici $4-6+4=2$; desenul dovedește că $K_4$ este planar.

Pentru un graf planar simplu cu $V\ge 3$, $M\le 3V-6$. $K_5$ are $V=5$ și $M=10$, dar $3V-6=9$; cum $10>9$, $K_5$ nu poate fi planar. Un subgraf pe vârfurile alese păstrează toate muchiile care aveau ambele capete în această mulțime; dacă vrei să elimini doar o muchie, construiești un graf parțial.

Un graf planar desenat în plan împarte planul în fețe: regiunile mărginite de muchii, plus regiunea exterioară nemărginită. Relația lui Euler leagă numărul de vârfuri, de muchii și de fețe și este aceeași cu cea de la poliedrele convexe, deoarece un poliedru convex poate fi „aplatizat” într-un graf planar. Din ea se deduce și o limită pentru numărul muchiilor: dacă fiecare față are cel puțin $3$ muchii pe contur, atunci $M\le 3V-6$ pentru $V\ge 3$, deoarece suma lungimilor fețelor este $2M$ și fiecare față contribuie cu cel puțin $3$. Graful complet bipartit $K_{3,3}$ are $6$ vârfuri împărțite în două grupe de câte $3$, iar fiecare vârf al unei grupe este legat de toate vârfurile celeilalte; el reprezintă „problema celor trei case și trei fântâni”. Fiind bipartit, nu are cicluri de lungime $3$, deci fiecare față are cel puțin $4$ muchii, iar pentru un graf planar conex cu aceste fețe $M\le 2V-4$. Pentru $K_{3,3}$, $2V-4=8<9=M$, așadar nu este planar. Un criteriu complet este teorema lui Kuratowski: un graf este planar dacă nu conține subgraf obținut din $K_5$ sau din $K_{3,3}$ prin împărțirea muchiilor.

Exemplu rezolvat. Un graf planar conex are $8$ vârfuri și $12$ muchii. Câte fețe are desenul său planar?

1. Relația lui Euler este $V-M+F=2$.
2. $8-12+F=2$, deci $F=6$.
3. Un exemplu de astfel de graf este scheletul cubului.

Exemplu rezolvat. Din graful complet $K_4$ cu vârfurile $A,B,C,D$, determină subgraful pe $\{A,B,C\}$ și un graf parțial cu $3$ muchii.

1. Subgraful pe $\{A,B,C\}$ păstrează muchiile $AB,AC,BC$ și este un triunghi.
2. Un graf parțial al lui $K_4$ cu $3$ muchii și toate cele $4$ vârfuri este, de exemplu, $\{AB,BC,CD\}$, un lanț.
3. Acest graf parțial este chiar un arbore, deoarece este conex cu $4-1=3$ muchii.

Greșeli frecvente

• Greșit: graful $K_{3,3}$ este planar fiindcă are doar $6$ vârfuri.
  Corect: are $9$ muchii și nu poate fi desenat fără încrucișări; planaritatea nu depinde doar de numărul vârfurilor.
• Greșit: două linii care se încrucișează într-un desen arată automat un graf neplanar.
  Corect: cauți și o reprezentare fără încrucișări.
• Greșit: fața exterioară nu intră în relația lui Euler.
  Corect: ea se numără în $F$.
• Greșit: la formarea unui subgraf păstrezi un vârf, dar elimini arbitrar o muchie dintre două vârfuri păstrate.
  Corect: subgraful păstrează toate muchiile dintre vârfurile alese; pentru eliminarea izolată a unei muchii folosești graf parțial.

Înainte și după