În anumite aplicații necesită poziționat grafic pe o suprafață de două dimensiuni (un plan, o sferă, un poliedru, un tor etc.), astfel încât marginile graficului nu au trecut unul pe altul.
Definiția. Un grafic este numit un grafic planar care poate fi reprezentat pe un plan, astfel încât marginile sale să nu se intersecteze. Imaginea geometrică a unui grafic plan, în care marginile sale nu se intersectează, se numește un grafic plat.
Exemplul 1. Luați în considerare exemplele de grafice plane și imaginile lor plane:
Figura 2.12. Exemple de grafice plane și imaginile plane ale acestora
Fiecare grafic planar poate fi așezat, de asemenea, fără margini traversate pe o sferă sau pe alte tipuri de suprafețe. Criteriul pentru planaritatea graficelor este
TEOREM 2.11. Pontryagin-Kuratowski.
Un grafic este planar dacă și numai dacă nu conține subgrafe homeomorfe la graficele K5 și K3,3.
Exemplul 2. Determinați planaritatea graficului K4,4.
Soluția. Din moment ce graficul K4,4 conține K3,3 ca subgraf. apoi de teorema lui Pontryagin-Kuratowski nu este plană.
Definiția. O parte a planului delimitată de un ciclu simplu al unui grafic plan și care nu conține alte noduri și muchii în interiorul acestuia este numită fața lui. Un ciclu care leagă o față este numit limita unei fețe. Feretele din interiorul grafului plat sunt numite interne. Borderul exterior este extern.
Fiecare margine a unui grafic plat aparține exact celor două fețe. Îndepărtarea lui duce la faptul că cele două fețe se îmbină într-una.
Pentru graficele plane (pseudografii), avem
TEOREM 2.12. Formula lui Euler. Dacă n este numărul de vârfuri, m este numărul de margini, r este numărul de fețe ale unui grafic planar conectat G. Atunci
Notă. Formula Euler poate fi aplicată doar grafurilor plate, în care fețele pot fi distinse.
Exemplul 3 Verificarea fezabilității formulei dlyaploskogo Euler graph G = (V, X), V = (1, 2, 3, 4, 5, 6), X = ((1, 2), (1, 3), (1 , 4), (2, 3), (3, 4), (4, 5), (4, 6), (5, 6)) la ris.2.13.
Soluția. Caracteristicile graficului sunt după cum urmează: n = 6, m = 8, r = 4 (3 fețe interioare și o față exterioară). Substituind în formula Euler, obținem: 4 + 6 - 8 = 2.
Exemplu 4. Dovediți că graficul K5 nu este planar.
Soluția. Principalele caracteristici ale graficului după cum urmează: n = 5, m = 5 C 2 = (4 x 5) / (2 x 1) = 10. Presupunând planeitate în examinare a graficului, trebuie să existe imaginea plană. Deoarece formula Euler găsi numărul de muchii din planul imaginii: r = 2 - n + m = 2 5 + 10 = 7. Deoarece fiecare fațetă a graficului complet trebuie să conțină cel puțin trei coaste, numărul total de muchii din fețele (inclusiv repetă la numărare) nu ar trebui să fie mai mică de 21. Deoarece o margine a unui grafic planar poate cuprinde exact două fețe, atunci numărul total de muchii nu trebuie să fie mai mică de 11. cu toate acestea, m = 10.Otsyuda rezultă că plat Graficul de stivuire K5 există. Prin urmare, nu este planar, care trebuia să fie dovedit.
1. Dovediți neplanaritatea graficului K3.3 utilizând formula lui Euler.
2. Dovediți că graficul K6 nu este planar în două moduri
1) folosind teorema lui Pontryagin-Kuratowski,
2) folosind formula Euler.
3. Verificați validitatea formulei lui Euler pentru copaci.
4. Care este numărul minim de margini pe care trebuie să le eliminați dintr-un grafic plat pentru al transforma într-un copac? Răspunsul este justificat.
5. Este posibil să se construiască un grafic nonplanar cu 4 noduri?
6. Construiți un grafic nonplanar cu 6 noduri care nu conține K3,3.
7. Verificați planaritatea graficului K2,4.
8. Verificați dacă cubul B este planar.
9. Verificați planaritatea cubului B 4.
10. Verificați dacă graficul este planar în figura 2.14.
Figura 2.14. Numărați la sarcina 10
SARCINI DE CONTROL PE TEMA
Articole similare
Trimiteți-le prietenilor: