Plokštuminis grafikas:
Grafas vadinamas plokštumu, jei jis gali būti nubrėžtas plokštumoje taip, kad jokia briauna nesikerta.
Pavyzdys: Paveiksle parodytas grafikas yra plokštuminis grafikas.
Diagramos sritis: Apsvarstykite plokštuminį grafiką G=(V,E). Sritis apibrėžiama kaip plokštumos sritis, kuri yra ribojama briaunų ir negali būti toliau skaidoma. Plokštuminis grafikas padalija planus į vieną ar daugiau regionų. Vienas iš šių regionų bus begalinis.
Ribotas regionas: Jei srities plotas yra baigtinis, tai ta sritis vadinama baigtine.
Begalinis regionas: Jei srities plotas yra begalinis, ta sritis vadinama begaline. Plokštuminis grafikas turi tik vieną begalinę sritį.
Pavyzdys: Apsvarstykite grafiką, parodytą pav. Nustatykite sričių, baigtinių sričių ir begalinės srities skaičių.
Sprendimas: Aukščiau pateiktame grafike yra penki regionai, ty r 1 ,r 2 ,r 3 ,r 4 ,r 5 .
Grafike yra keturios baigtinės sritys, ty r 2 ,r 3 ,r 4 ,r 5 .
Yra tik viena baigtinė sritis, t.y., r 1
Plokštuminių grafikų savybės:
- Jei sujungtas plokštuminis grafikas G turi e briaunų ir r sričių, tai r ≦
Tai yra. - Jei sujungtas plokštuminis grafikas G turi e briaunas, v viršūnes ir r sritis, tai v-e+r=2.
- Jei sujungtas plokštuminis grafikas G turi e briaunas ir v viršūnes, tai 3v-e≧6.
- Pilnas grafikas K n yra plokštuma tada ir tik tada, kai n <5. < li>
- Pilnas dvišalis grafikas K mn yra plokštuminis tada ir tik tada, kai m3.
Pavyzdys: Įrodykite, kad visas grafikas K 4 yra plokštuminis.
Sprendimas: Visas grafikas K 4 yra 4 viršūnės ir 6 briaunos.
Žinome, kad sujungtam plokštuminiam grafikui 3v-e≧6. Vadinasi, K 4 , turime 3x4-6=6, kuris tenkina savybę (3).
Taigi K 4 yra plokštuminis grafikas. Taigi įrodyta.
Neplokštuminė diagrama:
Grafas laikomas neplokštumu, jei jo negalima nubraižyti plokštumoje taip, kad jokia briauna nesikerta.
Pavyzdys: Paveiksle pateikti grafikai yra neplokštieji grafikai.
Šių grafikų negalima nubraižyti plokštumoje taip, kad nesikirstų briaunos, todėl jie yra neplokštieji grafikai.
Neplokštuminių grafikų savybės:
Grafas yra neplokštuminis tada ir tik tada, kai jame yra K homeomorfinis pografas 5 arba K 3.3
1 pavyzdys: Parodykite, kad K 5 yra neplokštuminis.
Sprendimas: Visas grafikas K 5 yra 5 viršūnės ir 10 briaunų.
Dabar prijungtam plokštuminiam grafikui 3v-e≧6.
Vadinasi, dėl K 5 , turime 3 x 5-10=5 (tai netenkina 3 savybės, nes turi būti didesnė arba lygi 6).
Taigi, K 5 yra neplokštuminis grafikas.
2 pavyzdys: Parodykite, kad paveiksle parodyti grafikai yra neplokštieji, surasdami pografą, homeomorfinį K 5 arba K 3.3 .
Sprendimas: Jei pašalinsime kraštus (V 1 ,IN 4 ),(IN 3 ,IN 4 ) ir (V 5 ,IN 4 ) grafikas G 1 , tampa homeomorfiniu K 5 .Todėl jis neplokštuminis.
Jei pašalinsime kraštą V 2, V 7) grafikas G 2 tampa homeomorfiniu K 3.3 .Vadinasi tai neplokštuminis.
Grafiko dažymas:
Tarkime, kad G= (V,E) yra grafikas be kelių briaunų. G viršūnių spalvinimas yra spalvų priskyrimas G viršūnėms taip, kad gretimos viršūnės būtų skirtingų spalvų. Grafas G yra M spalvos, jei yra G dažymas, kuriame naudojamos M spalvos.
Tinkamas dažymas: Dažymas yra tinkamas, jei bet kurios dvi gretimos viršūnės u ir v turi skirtingas spalvas, kitaip tai vadinama netinkama spalva.
Pavyzdys: Apsvarstykite toliau pateiktą grafiką ir spalvą C={r, w, b, y}. Tinkamai nuspalvinkite grafiką naudodami visas spalvas arba mažiau spalvų.
Paveiksle parodytas grafikas yra mažiausiai 3 spalvų, taigi x(G)=3
Sprendimas: Fig. parodytas grafikas, tinkamai nuspalvintas visomis keturiomis spalvomis.
Paveiksle parodytas grafikas, tinkamai nuspalvintas trimis spalvomis.
Chromatinis G skaičius: Minimalus spalvų skaičius, reikalingas tinkamai grafo G spalvai gauti, vadinamas chromatiniu G skaičiumi ir žymimas x(G).
Pavyzdys: Chromatinis skaičius K n yra n.
Sprendimas: Dažymas K n galima sukonstruoti naudojant n spalvų, kiekvienai viršūnei priskiriant skirtingas spalvas. Dviejų viršūnių negalima priskirti tų pačių spalvų, nes kiekviena dvi šio grafiko viršūnės yra gretimos. Taigi chromatinis skaičius K n =n.
Grafikų spalvinimo taikymas
Kai kurios grafiko spalvinimo programos apima:
- Registro paskirstymas
- Žemėlapio dažymas
- Dvišalės grafikos tikrinimas
- Mobiliojo radijo dažnių paskyrimas
- Sudaryti tvarkaraštį ir pan.
Nurodykite ir įrodykite rankų paspaudimo teoremą.
Rankos paspaudimo teorema: Visų G grafo viršūnių laipsnių suma lygi dvigubam kraštinių skaičiui grafe.
Matematiškai tai galima pasakyti taip:
∑ v∈V deg(v)=2e
Įrodymas: Tegu G = (V, E) yra grafikas, kuriame V = {v 1 ,in 2 , . . . . . . . . . .} yra viršūnių aibė ir E = {e 1 ,Tai yra 2 . . . . . . . . . .} yra briaunų rinkinys. Mes žinome, kad kiekviena briauna yra tarp dviejų viršūnių, todėl kiekvienai viršūnei suteikiamas pirmasis laipsnis. Taigi kiekviena briauna suteikia grafiko antrą laipsnį. Taigi visų viršūnių laipsnių suma yra lygi dvigubam G briaunų skaičiui.
Vadinasi, ∑ v∈V deg(v)=2e
