Cunoaște Intuit, curs, prezentarea unui grafic plan

Rezumat: Un grafic plan. grafice homeomorf. Formula lui Euler. Graficul triangulat. Sarcini.

grafic planar

grafic planar este un grafic. reprezentate pe planul astfel încât nici două dintre marginile sale (sau, mai degrabă, curbele lor reprezentative) nu se intersectează geometrica oriunde, cu excepția incidentului pentru a le ambelor noduri. Graf. izomorf la un grafic plan este numit plan. grafic planar poate fi determinată mai mult ca acest lucru: grafic este planar dacă poate fi pus în avion. Desen un grafic în care oricare două dintre marginile sale nu se suprapun, cu excepția punctelor de intersecție noduri comune, numita reprezentare plană a graficului. În mod evident, reprezentarea plat are doar un grafic plan. Pe de altă parte, în fiecare grafic planar există cu siguranță o reprezentare plană. grafice planare - un simplu cicluri, copaci, pădure. precum contele. conținând un inel din care nodurile „merg“ copaci.

Exemplu. Un exemplu de grafic neplană poate servi ca un grafic complet cu cinci noduri. Orice încercare de a atrage reprezentarea plat transforma într-un eșec.

Deoarece caracteristicile unei reprezentări plate a graficului introduce conceptul de față. Edge într-o reprezentare plană a unui grafic este parte a planului delimitat de un ciclu simplu și care nu sunt conținute în celelalte cicluri.

Figura prezintă o reprezentare plană a unui grafic cu trei fețe: ,,. O parte a planului delimitat de ciclu simplu, o fata nu este, deoarece conține un ciclu. ciclu simplu. delimitând fata, numita fata de delimitare. Două fețe vor fi numite adiacente. în cazul în care limitele lor au cel puțin o muchie comună.

În această parte a graficului delimitat printr-un ciclu simplu, o fata, de la marginea situată în interiorul feței. Ea nu formează o buclă.

Nu este o față plană porțiune eclozat în acest exemplu, deoarece acesta cuprinde un ciclu, și în afară, această porțiune a planului nu este ciclu limitat. O margine este o punte de legătură între cicluri. Astfel de poduri sunt numite partiții.

Deoarece fețele pot fi considerate parte a planului aflat „în afara“ reprezentarea plană a graficului. Este limitată la ciclul simplu „interior“ și nu conține alte cicluri. Această parte a planului se numește fața infinit.

Cifra feței infinit este umbrită. Fiecare apartament are un număr de vedere nu este fata infinit. sau are exact o margine infinit. Ca un caz special, fateta de intrare a infinitului într-o reprezentare plană a copacului și pădure. În reprezentarea plană a copacului și pădurea pentru întregul plan fateta a figurii.

Două grafice sunt homeomorf (sau identice până la nodurile de gradul 2), în cazul în care ambele pot fi obținute de la același grafic „includerea“ în noile sale noduri de margine de gradul 2.

grafice homeomorf înfățișate, și același lucru se poate spune despre orice două grafice ciclice. grafice homeomorf este raportul de echivalență. Este clar că introducerea termenului „homeomorf“ convenabil doar din punct de vedere tehnic - includerea sau eliminarea nodurilor de gradul 2 nu are nimic de-a face cu planeitatea. Adăugarea (includerea) un vârf, să zicem, unele margine. de exemplu, după cum urmează: Fie nodurile și marginea este incidență. Apoi, marginea este scos din grafic, dar a adăugat două muchii noi: incidente și blaturi și topuri și incidente.