incidență matrice - un tabel care conține un set de rânduri și coloane. Fiecare linie corespunde unui nod, și fiecare coloană - ramură grafic. Dacă numărul de ramură este direcționat din nodul în coloana rând și j-a i-am scrie unul. În cazul în care ramura i-lea este direcționat către un nod în rândul i-lea și j-a coloană scriere -1. Toate celelalte elemente ale matricei sunt egale cu incidență zero.
matrice de incidență oferă o descriere completă a unui grafic direcționat. Cu matricea de incidență este convenabil pentru a scrie ecuația primei legi a lui Kirchhoff în formă de matrice:
unde M - matricea de incidență,
IB - Curenții de ramură matrice,
J - matrice curentii date în nodurile.
matrici topologice permit să oficializeze intrarea ecuațiilor legilor lui Kirchhoff. care este foarte importantă din punct de vedere al calculelor de calculator.
matrice de incidență este o dimensiune n x m matrice dreptunghiulară, unde n - numărul de noduri și m - numărul duggrafa. Notată incidență matrice B = ij>, i = 1, 2, ..., n, j = 1, 2, ..., m.
Fiecare element al matricei este definită după cum urmează:
bij = 1 dacă x i este inițial vertex arc AJ,
bij = -1, dacă xi este un finit aj arc vertex,
bij = 0 dacă xi nu este nodul terminal al arcului sau dacă aj este buclă aj.
Fig. 1.5. și b este un grafic și matricea sa de adiacență, pe care o puteți găsi vârfuri caracteristice. Deoarece suma elementelor i -lea rând al matricei dă outdegree vârfuri xi. iar suma elementelor coloanelor i-lea dă vârfuri indegree xi. Matricea smezhnostimozhno găsi afișare directă și inversă. Să considerăm șirul i -lea al matricei. Dacă aij = 1 elementul grafic atunci xj elementul inclus în cartografierea F (xi). De exemplu, în al 2-lea rând al matricei A (fig. 1.5, b) unități sunt în a 2 si 5 coloane deci T (x2) = <х2. х5>.
Fig. 1.5. Digraph și reprezentarea sa matrice: a - digraph; b - matricea de adiacenta; în - matricea de incidență
Pentru graficul din fig. 1.5, iar matricea de incidență este prezentată în Fig. 1.5 in. Pe măsură ce fiecare arc este incident de la două înălțimi diferite, cu excepția cazului în care arcul formează o buclă, fiecare coloană conține fie un element egal cu unu și unu - egal - la 1 sau toate elementele coloanei sunt egale cu 0.
Pentru un graf neorientat, matricea de incidență se determină în mod similar, cu excepția faptului că toate elementele egale cu 1, substituite cu 1.