Eulerian este un ciclu într-un grafic care conține toate margini ale graficului.
Un grafic Euler este un grafic conectat în care există un ciclu Euler. Graful Euler poate fi desenat fără a lua creionul din hârtie și a repeta liniile (Figura 14).
Fig. 14. Graficul Euler
Teorema 6. Un grafic G este Euler dacă și numai dacă G este un grafic conectat având toate vârfurile egale.
Un lanț Hamiltonian este un lanț simplu care conține toate vârfurile graficului.
Un ciclu Hamiltonian este un lanț Hamiltonian, al cărui început și sfârșit coincid.
Un grafic este numit Hamiltonian dacă conține un ciclu Hamiltonian (Figura 15).
Fig. 15. Graficul grafului Hamiltonian
Un grafic G se numește p-cromatic, unde p este un număr natural dacă nodurile sale pot fi colorate cu culori p diferite, astfel încât nici două vârfuri adiacente nu sunt colorate în mod egal.
Cel mai mic număr p pentru care graficul este p-cromatic este numit numărul cromatic al graficului și este notat. Dacă = 2, atunci graficul este numit bichromatic. O condiție necesară și suficientă în graficul ciclurilor de lungime ciudată.
De exemplu, graficul din Fig. 16 este bicromatic, vârfurile sale fiind "colorate" cu două "culori", notate cu 0 și 1.
Fig. 16. Graficul grafic bichromatic.
Grafică plană și plană
Se spune că un grafic G este planar dacă există un grafic G 'izomorf pentru el, în imaginea căruia în planul margini se intersectează numai la vârfuri. Cu alte cuvinte, pentru un grafic plan, nici două muchii nu au puncte comune decât nodurile comune. De exemplu, graficul din Fig. 5 este planar, iar în Fig. 7 nu este.
Teorema lui Euler. Un grafic planar conectat cu vârfuri n și margini m divide avionul în domenii k (inclusiv cel exterior) și
Se spune că un grafic este bipartit dacă mulțimea vârfurilor sale X poate fi împărțită în două subseturi disjuncte astfel încât fiecare margine a graficului să se alăture vârfurilor a două subseturi diferite.
Articole similare
Trimiteți-le prietenilor: