Conectivitatea graficului - studopediya
graf neorientat este numit conectat. dacă fiecare pereche de vârfuri distincte pot fi conectate prin cel puțin un lanț.
Un grafic direcționat este numit puternic conectat. dacă pentru oricare două vârfuri xi și xj există cel puțin o cale de conectare xi la xj.
Un grafic direcționat se numește one-way conectat. în cazul în care cel puțin unul este accesibil de celălalt, pentru oricare două noduri.
Componentele conectate ale unui graf neorientat este numit subgrafic sa conectat, un subgraf nu este deținut de orice alt subgraf conectat a graficului (subgraful mai conectat).
Componentă a unui grafic direcționat puternic conectat este numit subgrafic său puternic conectat nu este deținut de orice alt subgrafic conectat puternic subgraf a graficului (subgraful cel mai puternic conectate).
, Conectivitate Monocomponent a unui graf neorientat este subgrafic unilaterală conectat nu este deținut de nici un alt subgrafic conectat unilateral subgrafic graficului (maxim subgrafic conectat unilateral).
Fie G = (X, A) un grafic nedirijat-TION cu o multitudine de vârfuri X = x1. xn>. Un pătrat matrice S = (sij) de ordinul n, în care
G se numește matricea graficului.
Pentru o matrice pătrată grafic direcționat T = (tij) de ordinul n. de la Koto-o multime
nazyvaetsyamatritsey fețe de conectare (accesibilități).
Un pătrat matrice S = (sij) de ordinul n. în care
Se numește matricea de conectivitate puternică.
Într-un grafic neorientat prezentat în Fig. 3.8 Cele două componente conectate. Prima componentă include conectivitate vertex x1. x2, x4, x5, iar al doilea este format dintr-un singur nod x3.
conectivitatea matricei graficului are forma:
Vedem că 1, 2, 4 și 5 rânduri ale matricei S sunt identice.
Într-un grafic direcționat prezentat în Fig. 3.9 Cele două componente ale conectivității puternice. Prima componentă include conectivitate vertex x1. x2, x3, x5, iar al doilea este format dintr-un singur nod x4. Într-adevăr, pentru fiecare pereche de noduri din x1 set. x2, x3, x5> există cel puțin o cale de a conecta aceste noduri. De exemplu, calea (x1. X2, x5, x3, x1) conectează toate aceste vârfuri. Din partea de sus a x4 nu există nici un fel nici un vârf al graficului.
Matricea de conectivitate puternică a graficului este dată de:
Vedem că 1, 2, 3 si 5 rânduri ale matricei S sunt identice.