Fig. 1. Un grafic al cărui grade sunt marcate pe noduri.
Gradul unui vârf (numit și valență) în teoria graficelor este numărul de margini ale graficului G. incident spre vârful x. Atunci când se calculează gradul de buclă de margine este luată în considerare de două ori. [1] Gradul unui vârf este notat ca d (x) (în sursele occidentale - deg (v)). Gradele maxime și minime ale vârfurilor graficului G sunt notate cu Δ (G) și δ (G). În Fig. 1 gradul maxim este de 5, minimul este 0. Gradele tuturor nodurilor sunt aceleași într-un grafic obișnuit, deci în acest caz se poate vorbi despre gradul unui grafic.
Lemma pe Handshakes
Prin suma puterilor pentru graficul G = (V.E),
adică, suma gradelor vârfurilor oricărui grafic este de două ori mai mare decât numărul marginilor sale. În plus, rezultă din formula că, în orice grafic, numărul de noduri de grad impare este egal. Această afirmație (și formula în sine) este cunoscută sub numele de lemna la strângerea de mâini. Numele provine dintr-o problemă matematică bine cunoscută: este necesar să se demonstreze că, în orice grup, numărul de oameni care au dat mâna cu un număr ciudat de alții este egal.
Secvența de grade de vârfuri
Fig. 2. Două grafice nonisomorfe cu aceeași secvență de grade (3, 2, 2, 2, 2, 1, 1, 1).
Secvența de grade ale vârfurilor unui grafic nedirecționat este o secvență nesemnificativă. [2] Pentru graficul prezentat în Fig. 1, are forma (5, 3, 3, 2, 2, 1, 0). Secvența de grade de vârfuri este invariantă a graficului. prin urmare, este aceeași pentru grafice izomorfe. Cu toate acestea, secvența de grade de vârf nu este o caracteristică unică a unui grafic: în unele cazuri, grafice non-izomorfe au aceeași secvență.
Problema grade secvențe este de a găsi unele sau toate numărătorilor cu secvența non predeterminată în creștere care constă din numere naturale (zero grade, astfel, pot fi ignorate, deoarece valoarea lor este modificată prin adăugarea sau eliminarea vârfuri izolate). O secvență care este o secvență de puteri a unui grafic este numită o secvență grafică. Formula suma puterilor rezultă că orice secvență cu suma impar (ca, de exemplu, 3, 3, 1) nu poate fi grade graficul de secvență. Conversiunea este de asemenea adevărată: dacă o secvență are o valoare uniformă, este o secvență de grade ale multigrafului. Construirea un astfel de grafic se realizează într-un mod simplu: este necesar să se combine vârful puteri impare în perechi. Adăugați bucle la nodurile rămase nefolosite.
Este mai dificil să implementăm un grafic simplu cu o anumită secvență. Teorema Erdos - Gallai susține că o creștere a secvenței di (dacă i = 1, ..., n) poate fi o secvență de grafic simplu numai dacă valoarea sa chiar și inegalitate
De exemplu, secvența (3, 3, 3, 1) nu poate fi o secvență a unui grafic simplu; satisface inegalitatea Erdös-Gallai numai pentru k egal cu 1, 2 sau 4, dar nu pentru k egal cu 3.
Conform criteriului Havel-Hakimi [3]. în cazul în care o secvență (d1 d2 ..., dn ..) non-în creștere este o secvență de grade simplu grafic, (d2 - 1, d3 - 1, ..., DD1 +1 - .. 1, DD1 2 DD1 +3 ..., dn) o secvență puteri ale unui grafic simplu. Acest fapt ne permite să construim un algoritm polinomial pentru identificarea unui grafic simplu, cu o secvență predeterminată implementată.
Comparați secvența inițială a numerelor cu vârful graficului fără margini cu puterile necesare. Această transformare definește o secvență de cel puțin un vârf al graficului, toate muchiile incidente la ea și o multitudine de noduri cu noi completări necesare grade. Prin aranjarea nodurile rămase pe adăugări non-grade crescătoare obține o secvență care nu mai mare de grade de grafice simple. Repetând transformarea și ordonând nu mai mult de n-1 ori, obținem întregul grafic.
Problema găsirii sau estimării numărului de grafice printr-o anumită secvență aparține zonei de enumerare a grafurilor.
Fig. 3. Vârfurile finale sunt 4, 5, 6, 7, 10, 11 și 12.
- Se spune că un vârf de gradul 0 este izolat.
- Un vârf al gradului 1 se numește vârful final, un vârf pendant sau o frunză de vârf. Marginea care provine de la un astfel de vârf se numește terminal (endend). În Fig. 3 este o margine agățată. Terminologia similară este folosită în studiul arborilor în general și al structurilor de date.
- Un vârf de gradul n-1 al unui grafic al ordinului n este considerat a fi dominant (vertex dominantă engleză).
- Dacă toate vârfurile graficului au același grad k. graficul este numit k-grafic normal sau regulat al gradului k. În acest caz, graficul însuși are gradul k.
- Calea Euler există într-un grafic neorientat, conectat dacă și numai dacă graficul are 0 sau 2 vârfuri de grad impare. Dacă graficul conține 0 noduri de grad impare, calea Euler este un ciclu.
- Un digraph este psevdolesom [termen necunoscut] numai în cazul în care fiecare nod outdegree nu este mai mare decât 1. Graficul funcției - psevdolesa caz special în care outdegree de toate nodurile sunt egale cu 1.
- Conform teoremei Brooks, numărul cromatic al oricărui grafic, cu excepția unei clicuri sau a unui ciclu ciudat, nu depășește gradul maxim al vârfurilor sale (Δ). Conform teoremei lui Wiesing, indicele cromatic al oricărui grafic nu depășește Δ + 1.
- Un grafic k-degenerat este un grafic în care fiecare subgraf are un vârf de grad cel mult k.
Trimiteți-le prietenilor: