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.

Java kūrimo sąrašas

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₁,r₂,r₃,r₄,r₅.

Grafike yra keturios baigtinės sritys, ty r₂,r₃,r₄,r₅.

Yra tik viena baigtinė sritis, t.y., r₁

Plokštuminių grafikų savybės:

1. Jei sujungtas plokštuminis grafikas G turi e briaunų ir r sričių, tai r ≦ Tai yra.
2. Jei sujungtas plokštuminis grafikas G turi e briaunas, v viršūnes ir r sritis, tai v-e+r=2.
3. Jei sujungtas plokštuminis grafikas G turi e briaunas ir v viršūnes, tai 3v-e≧6.
4. Pilnas grafikas K_nyra plokštuma tada ir tik tada, kai n<5.< li>
5. Pilnas dvišalis grafikas K_mnyra plokštuminis tada ir tik tada, kai m3.

Pavyzdys: Įrodykite, kad visas grafikas K₄yra plokštuminis.

Sprendimas: Visas grafikas K₄yra 4 viršūnės ir 6 briaunos.

Žinome, kad sujungtam plokštuminiam grafikui 3v-e≧6. Vadinasi, K₄, turime 3x4-6=6, kuris tenkina savybę (3).

javascript miegas

Taigi K₄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₅arba K_3.3

java prioritetų eilė

1 pavyzdys: Parodykite, kad K₅yra neplokštuminis.

Sprendimas: Visas grafikas K₅yra 5 viršūnės ir 10 briaunų.

Dabar prijungtam plokštuminiam grafikui 3v-e≧6.

Vadinasi, dėl K₅, turime 3 x 5-10=5 (tai netenkina 3 savybės, nes turi būti didesnė arba lygi 6).

Taigi, K₅yra neplokštuminis grafikas.

2 pavyzdys: Parodykite, kad paveiksle parodyti grafikai yra neplokštieji, surasdami pografą, homeomorfinį K₅arba K_3.3.

Sprendimas: Jei pašalinsime kraštus (V₁,IN₄),(IN₃,IN₄) ir (V₅,IN₄) grafikas G₁, tampa homeomorfiniu K₅.Todėl jis neplokštuminis.

Jei pašalinsime kraštą V_{2, V}7) grafikas G₂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.

pabraukite tekstą su css

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_nyra n.

Sprendimas: Dažymas K_ngalima 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∈Vdeg(v)=2e

Įrodymas: Tegu G = (V, E) yra grafikas, kuriame V = {v₁,in₂, . . . . . . . . . .} yra viršūnių aibė ir E = {e₁,Tai yra₂. . . . . . . . . .} 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∈Vdeg(v)=2e

romėniški skaitmenys 1100