Fie G un graf marcat cu n noduri si margini n. Definim matricea de adiacență A (G) după cum urmează:
Matricea de adjuvant este pătrată, cu dimensiunea n 'n.
Se poate observa că matricea de adiacență este simetrică, iar numărul de unități din fiecare rând este egal cu gradul de vertexul care corespunde acestei linii. Din matricea de adjudecție, este ușor să se construiască o reprezentare grafică a graficului.
Exemplul 4.6. Construiți un grafic din matricea de adjunct
Este posibil să se determine matricea de incidență I (G). având n rânduri și coloane m, ale căror elemente sunt specificate după cum urmează:
Exemplul 4.7. Luați în considerare graficul din Exemplul 4.6, care indică marginile.
În fiecare rând al matricei de incidență, numai două elemente sunt diferite de 0 (sau unul dacă marginea este o buclă). Prin urmare, această metodă de descriere nu este economică. Relația de incidență poate fi, de asemenea, specificată de lista margini a graficului. Fiecare linie din această listă corespunde unei margini, conține numerele de vârfuri care îi sunt afectate.
Exemplul 4.8. Luați în considerare graficul din Exemplul 4.7. Lista de margini arată astfel:
Din lista de margini ale graficelor, este ușor să se construiască o matrice de incidență, deoarece fiecare margine a acestei liste corespunde coloanei matricei și numărul de noduri din fiecare element al listei reprezintă numerele elementelor din rândul matricei de incidență care sunt egale cu 1.
Un grafic poate fi reprezentat în diferite moduri. Uneori nu este ușor pentru a vedea dacă aceleași grafice reprezentate în diferite desene sau diferite matrici. Graficele care diferă numai prin numerotarea nodurilor sunt considerate a fi izomorfe. Renumarea este specificată de un șir de noi numere de vârfuri aflate în ordinea inițială. Noua matrice adiacență obținută ca rezultat al deplasării fiecărui element ij în rând și coloană, adică, rezultând permutare () de rânduri și coloane ale matricei originale. Puteți efectua toate permutările posibile ale rândurilor și coloanelor pentru a verifica non-izomorfismul grafurilor, dar acest lucru va necesita n. permutații, care este destul de laborioasă.
Articole similare
Trimiteți-le prietenilor: