Matricea de incidenta

Matricea de incidență este una dintre  formele de reprezentare grafică , în care sunt indicate legăturile dintre elementele incidente ale graficului (marginea (arc) și vârful). Coloanele matricei corespund muchiilor, rândurile corespund vârfurilor. O valoare diferită de zero într-o celulă de matrice indică relația dintre un vârf și o muchie ( incidența acestora ).

În cazul unui grafic dirijat, fiecare arc <x,y> este plasat în coloana corespunzătoare: „1” în rândul vârfului x și „-1” în rândul vârfului y; dacă nu există nicio legătură între vârf și margine, atunci se pune „0” în celula corespunzătoare.

Exemplu

Grafic	Matricea de incidenta

Rândurile corespund vârfurilor de la 1 la 6, iar coloanele corespund muchiilor e1–e7. De exemplu, cele din a doua coloană din rândurile 2 și 3 înseamnă că muchia e2 conectează vârfurile 2 și 3.

Caracteristicile acestei reprezentări

1. Folosit pentru orice grafice, chiar dacă există o buclă.
2. Fiecare coloană trebuie să conțină cel mult doi 1 (dacă această margine este o buclă, atunci 1 este plasat opus vârfului la care este incidentă bucla). În cazul unui grafic direcționat, coloana trebuie să conțină 1 și -1.
3. Poate fi folosit pentru a reprezenta hipergrafe (caz în care coloana poate conține mai mult de doi 1)

Vezi și

• Matricea adiacentei

Note

Literatură

1. Harari F. Teoria grafurilor.  — M.: Mir. - 1973. - 300 p.