Graficul planar

Un graf plan  este un graf care poate fi desenat pe un plan fără margini încrucișate , altele decât la vârfuri. Orice imagine specifică a unui graf plan într-un plan fără muchii încrucișate nu la vârfuri se numește graf plan . Cu alte cuvinte, un graf plan este izomorf cu un graf planar reprezentat pe un plan astfel încât vârfurile sale sunt puncte ale planului, iar muchiile sunt curbe pe plan, care, dacă se intersectează, atunci numai de-a lungul vârfurile. Zonele în care un grafic partiţionează un plan se numesc feţele acestuia . Partea nemărginită a planului este, de asemenea, o față, numită față exterioară . Orice grafic plan poate fi îndreptat, adică redesenat pe plan, astfel încât toate muchiile sale să fie segmente de linie.

Proprietăți

Formula lui Euler

Pentru un graf planar conectat, următoarea relație este valabilă între numărul de vârfuri , muchii și fețe (inclusiv fața exterioară):

A fost găsit de Euler în 1736 [1] în timp ce studia proprietățile poliedrelor convexe . Această relație este valabilă și pentru alte suprafețe până la un factor numit caracteristica Euler . Acesta este invariantul de suprafață , pentru un plan sau sferă este egal cu doi și, de exemplu, pentru suprafața unui tor  este zero.

Formula are multe consecințe utile. În primul rând, toate stivuirile plane ale unui grafic au același număr de fețe. În al doilea rând, dacă fiecare față este delimitată de cel puțin trei muchii (cu condiția ca graficul să aibă mai mult de două muchii) și fiecare muchie separă două fețe , atunci

Prin urmare,

adică pentru un număr mai mare de muchii, un astfel de grafic este evident neplanar. Reversul nu este adevărat: se poate lua ca contraexemplu graficul Petersen . Rezultă că într-un graf plan este întotdeauna posibil să se găsească un vârf de grad de cel mult 5.

Formula generală se generalizează cu ușurință și în cazul unui grafic deconectat:

unde  este numărul de componente conectate din grafic.

Două exemple de grafice neplanare

Grafic complet cu cinci vârfuri

Lema. Un grafic complet cu cinci vârfuri (K 5 ) nu poate fi aplatizat.

Dovada. Nu merge pentru el .

„Case și fântâni”

Problema celor trei puţuri . Sunt trei case și trei fântâni. Este posibil să așezi poteci între case și fântâni în așa fel încât o potecă să ducă de la fiecare casă la fiecare fântână și să nu se intersecteze două căi. Nu se pot construi poduri.

Lema. Un graf bipartit complet cu trei vârfuri în fiecare dintre părți (K 3,3 ) nu poate fi așezat pe un plan.

Dovada. Conform formulei lui Euler, graficul are 5 fețe.

Pe de altă parte: orice față (inclusiv cea exterioară) conține un număr par de muchii, ceea ce înseamnă cel puțin 4. Deoarece fiecare muchie este inclusă în exact două fețe, obținem relația , F  este numărul de fețe, E  este numărul de muchii. Inlocuim F = 5 si E = 9 in aceasta inegalitate si vedem ca nu este satisfacuta.

Teorema Pontryagin-Kuratovsky

Afirmația este evidentă: dacă un graf G conține un subgraf homeomorf cu K 5 sau K 3,3 , atunci acesta nu poate fi descompus pe plan. Se dovedește că și contrariul este adevărat.

Un grafic este plan dacă și numai dacă nu conține subgrafe homeomorfe pentru un grafic complet de cinci vârfuri (K 5 ) sau pentru un grafic „case și puțuri” (K 3,3 ).

Teorema poate fi enunțată și în următoarea variantă (numită uneori „ teorema lui Wagner ”).

Graficul este plan dacă și numai dacă nu conține subgrafe care se contractează la K 5 sau K 3,3 .

Verificați computerul pentru planaritate

Primul algoritm care a găsit subgraful Kuratowski în timp liniar a fost dezvoltat în 1974 de Hopcroft și Tarjan [2] .

Caracteristici ale graficelor neplanare

Grafice plane în probleme

Carte de colorat . Este necesar să colorați o hartă plată cu un anumit număr de culori, astfel încât oricare două țări care au o secțiune comună de frontieră să aibă culori diferite. Se dovedește că, în absența enclavelor , patru culori sunt întotdeauna suficiente, dar această afirmație este extrem de greu de demonstrat, vezi problema Patru culori .

Rectificarea graficului ( teorema lui Fari ). Orice grafic plan poate fi redesenat astfel încât să rămână plan, iar marginile să devină segmente de linie.

Generalizări

Un grafic se potrivește pe o suprafață dacă poate fi desenat pe ea fără a încrucișa marginile. Graficul stivuit se numește geometric , vârfurile sale sunt punctele suprafeței, iar muchiile sunt liniile de pe acesta. Zonele în care un grafic parțiază o suprafață se numesc fețe . Un graf plan este un graf așezat pe un plan.

Numărul de intersecție al graficului G  este cel mai mic număr de intersecții ale muchiilor desenului plat al graficului G . Astfel, un grafic este plan dacă și numai dacă numărul său de intersecție este zero.

Un graf toroidal  este un graf care poate fi așezat pe un tor.

Vezi și

Note

  1. ↑ Harari F. Teoria graficelor URSS p. 126
  2. ↑ Hopcroft, John & Tarjan, Robert E. (1974), Efficient planarity testing , Journal of the Association for Computing Machinery vol. 21 (4): 549–568 , DOI 10.1145/321850.321852  .

Link -uri