Se spune că un grafic este plan dacă poate fi desenat într-un plan, astfel încât nicio margine să nu se încrucișeze.

Exemplu: Graficul prezentat în fig este un grafic plan.

imprimare javascript

Regiunea unui grafic: Luați în considerare un grafic plan G=(V,E). O regiune este definită ca fiind o zonă a planului care este mărginită de muchii și nu poate fi subdivizată în continuare. Un grafic plan împarte planurile în una sau mai multe regiuni. Una dintre aceste regiuni va fi infinită.

Regiunea finită: Dacă aria regiunii este finită, atunci acea regiune se numește regiune finită.

Regiunea infinită: Dacă aria regiunii este infinită, acea regiune se numește regiune infinită. Un graf plan are o singură regiune infinită.

Exemplu: Luați în considerare graficul prezentat în Fig. Determinați numărul de regiuni, regiuni finite și o regiune infinită.

Soluţie: Există cinci regiuni în graficul de mai sus, adică r₁,r₂,r₃,r₄,r₅.

Există patru regiuni finite în grafic, adică r₂,r₃,r₄,r₅.

Există o singură regiune finită, adică r₁

Proprietățile graficelor plane:

1. Dacă un graf planar conex G are e muchii și r regiuni, atunci r ≦ Este.
2. Dacă un graf planar conex G are e muchii, v vârfuri și r regiuni, atunci v-e+r=2.
3. Dacă un graf planar conex G are e muchii și v vârfuri, atunci 3v-e≧6.
4. Un grafic complet K_neste un plan dacă și numai dacă n<5.< li>
5. Un grafic bipartit complet K_mneste plană dacă și numai dacă m3.

Exemplu: Demonstrați că graficul complet K₄este plană.

Soluţie: Graficul complet K₄conține 4 vârfuri și 6 muchii.

Știm că pentru un graf planar conectat 3v-e≧6. Prin urmare, pentru K₄, avem 3x4-6=6 care satisface proprietatea (3).

înlocuiți din șir în java

Astfel K₄este un grafic plan. Prin urmare, dovedit.

Grafic non-planar:

Se spune că un grafic este neplan dacă nu poate fi desenat într-un plan, astfel încât nicio margine să nu se încrucișeze.

Exemplu: Graficele prezentate în fig sunt grafice neplanare.

Aceste grafice nu pot fi desenate într-un plan, astfel încât să nu se încrucișeze muchii, deci sunt grafice neplanare.

Proprietăți ale graficelor neplanare:

Un grafic este neplan dacă și numai dacă conține un subgraf homeomorf cu K₅sau K_3.3

multiplexarea

Exemplul 1: Arată că K₅este neplanar.

Soluţie: Graficul complet K₅conține 5 vârfuri și 10 muchii.

Acum, pentru un grafic planar conectat 3v-e≧6.

Prin urmare, pentru K₅, avem 3 x 5-10=5 (care nu satisface proprietatea 3 deoarece trebuie să fie mai mare sau egală cu 6).

Astfel, K₅este un grafic neplanar.

Exemplul 2: Arătați că graficele prezentate în fig. sunt neplanare, găsind un subgraf homeomorf cu K₅sau K_3.3.

Soluţie: Dacă scoatem marginile (V₁,ÎN₄),(ÎN₃,ÎN₄) și (V₅,ÎN₄) graficul G₁, devine homeomorf pentru K₅.Deci este neplanar.

Dacă scoatem marginea V_2,V7) graficul G₂devine homeomorf la K_3.3.Deci este un neplanar.

Colorarea graficului:

Să presupunem că G= (V,E) este un grafic fără muchii multiple. O colorare a nodurilor lui G este o atribuire de culori nodurilor lui G astfel încât vârfurile adiacente să aibă culori diferite. Un grafic G este M-Colorabil dacă există o colorare a lui G care folosește M-Colors.

Colorarea corectă: O colorare este adecvată dacă oricare două vârfuri adiacente u și v au culori diferite, altfel se numește colorare necorespunzătoare.

egalitatea obiectelor java

Exemplu: Luați în considerare următorul grafic și colorați C={r, w, b, y}. Colorați graficul corect folosind toate culorile sau mai puține culori.

Graficul prezentat în fig este un minim 3-colorabil, deci x(G)=3

Soluţie: Fig arată graficul colorat corespunzător cu toate cele patru culori.

Fig prezintă graficul colorat corespunzător cu trei culori.

Numărul cromatic al lui G: Numărul minim de culori necesare pentru a produce o colorare adecvată a unui grafic G se numește numărul cromatic al lui G și este notat cu x(G).

Exemplu: Numărul cromatic al lui K_neste n.

Soluţie: O colorare a lui K_npoate fi construit folosind n culori prin atribuirea de culori diferite fiecărui vârf. Nu pot fi atribuite două vârfuri aceleași culori, deoarece fiecare două vârfuri ale acestui grafic sunt adiacente. De aici numărul cromatic al lui K_n=n.

Aplicații ale colorării graficelor

Unele aplicații ale colorării graficelor includ:

• Înregistrați alocarea
• Colorat Harta
• Verificarea grafică bipartită
• Atribuirea frecvenței radio mobile
• Realizarea unui orar etc.

Prezentați și demonstrați teorema strângerii mâinii.

Teorema strângerii de mână: Suma gradelor tuturor vârfurilor dintr-un grafic G este egală cu dublul numărului de muchii din grafic.

Din punct de vedere matematic se poate afirma ca:

∑_v∈Vdeg(v)=2e

Dovada: Fie G = (V, E) un grafic unde V = {v₁,în₂, . . . . . . . . . .} să fie mulțimea vârfurilor și E = {e₁,Este₂. . . . . . . . . .} fi mulţimea muchiilor. Știm că fiecare muchie se află între două vârfuri, așa că oferă gradul unu fiecărui vârf. Prin urmare, fiecare muchie contribuie cu gradul doi pentru grafic. Deci suma gradelor tuturor vârfurilor este egală cu dublul numărului de muchii din G.

Prin urmare, ∑_v∈Vdeg(v)=2e

gol 0