grafice ponderate
Weighted (etichetat aka) grafic (sau digraph) - un grafic (digraph), anumite elemente din care (vârfurile nervuri sau muchii.) Comparat numarul. Graficele cel mai frecvent întâlnite cu margini deosebite. Numărul de note au nume diferite: greutatea. lungime. cost cu o schimbare.
Notă. Normal (non ponderați) graph pot fi interpretate ca ponderate, toate care au aceeași greutate de margine 1.
Lungimea suspensiei graficului (conectat) - este suma lungimilor (ponderilor) a acelor margini care alcătuiesc calea. Distanța dintre vârfurile - este, ca și mai înainte, lungimea calea cea mai scurtă. De exemplu, distanța de la un vârf la vertex într-un grafic ponderat d. prezentat în Fig. 11.7. egală cu 6.
Fig. 11.7. Graficul ponderat
N - Periferice topuri v - este setul de noduri. distanța față de fiecare dintre ele (de vertex v) nu este mai mică decât N.
Modalități de reprezentare grafice
Există un număr destul de mare de moduri diferite de a reprezenta grafice. Cu toate acestea, vom prezenta aici doar cele mai utile din punct de vedere al programării.
Matricea adiacență
matricea de adiacență Sm - este o matrice pătrată de dimensiune NxN (N - numărul de noduri din grafic), următoarele reguli completate și cele zerouri:
Dacă există o margine e în grafic. conectarea nodurile u și v. Sm [u, v] = 1. În caz contrar Sm [u, v] = 0.
Rețineți că această definiție este grafice orientate și neorientate adecvate. matricea de adiacență pentru un graf neorientat este simetrică în raport cu principalul său diagonală, și pentru digraph - asimetrice.
Puneți grafic ponderată utilizând matricea de adiacență este de asemenea posibilă. Este necesar doar pentru a face o mică schimbare în definiția:
Dacă există o margine e în grafic. conectarea nodurile u și v. Sm [u, v] = ves (e). în caz contrar Sm [u, v] = 0.
Acest lucru este în concordanță cu observațiile făcute în paragraful anterior: graficul neponderate poate fi interpretat ca un echilibru, ale cărei margini au aceeași greutate 1.
Glitch vor apărea în cazul în care în coaste coloane rezolvate cu greutate 0. Apoi, este necesar pentru a stoca cele două tablouri: unul cu zero-uri si cele care servesc drept indicator al prezenței nervurilor, iar al doilea - cu greutăți ale acestor margini.
Ca un exemplu al matricei adiacenta pentru cele trei grafice. prezentat în Fig. 11.5. Fig. 11.6 și fig. 11.7 (vezi. Fig. 11.8).
Tabelul 11.8. Exemple de matrici adiacență