Pentru a spune că marginea g și fiecare dintre nodurile u și y este incident cu g. Acesta costă numai dacă g se conectează u și y. După ce a clarificat acest lucru, să ia în considerare această metodă. Matricea de incidență bazată pe o structură similară, dar nu pe același principiu ca și cea a matricei de adiacență. Astfel, în cazul în care acesta din urmă are o dimensiune de n × n. unde n - numărul de noduri, matricea de incidență - n x m. aici n - numărul de noduri, m - numărul de muchii. Deci, acum pentru a seta valoarea unei celule, nu trebuie să se asocieze cu partea de sus partea de sus, iar partea de sus a nervurii.
In fiecare matrice de incidență a unui grafic neorientat al celulei este setat la 0 sau 1, iar în cazul unui grafic direcționat. făcut 1, 0 sau -1. Același lucru, dar mai structurată:
1. graf neorientat:
· 1 - marginea superioară a incidentului;
· 0 - nod nu incident de la margine.
2. Grafic regia:
· 1 - Vertex incident de la margine, și este un început;
· 0 - nod nu incident de la margine;
· -1 - marginea incidentului la vârf, și este la sfârșitul ei.
Executăm primă matrice de incidență pentru un grafic neorientat (fig. 3.10), apoi la digraph (fig. 3.11). Coastele notate cu literele A e, primele - cifre. Toate marginile graficului nu este orientat, cu toate acestea matrice incidență umplut cu valori pozitive.
Figura 3.10 - graficul neorientat și matricea de incidență
Pentru digraph matrice are o formă ușor diferită. În fiecare dintre celulele sale a făcut una din cele trei valori. Vă rugăm să rețineți că zerouri în cele două matrice ocupă aceeași poziție, pentru că, în ambele cazuri, structura graficului singur. Cu toate acestea, unele unități pozitive au fost înlocuite pe negativ, de exemplu, într-o celulă graf neorientat (1, b) conține 1 și -1 în digraph. Faptul este că, în primul caz, nervura b este îndreptat, iar al doilea - direcția și, cu partea superioară a intrării este vârf de „1“.
Figura 3.11 - direcționată grafic și matricea de incidență
Fiecare coloană este responsabil pentru orice margine, astfel încât graficul descrisă utilizând matricea de incidență, va avea întotdeauna următoarea caracteristică: fiecare dintre coloanele matricei de incidență cuprinde două unități, fie 1 sau -1, atunci când este orientată margine, restul de ea - zerouri .