Algorytmy grafowe.pdf

Algorytmy grafowe

Grafy

G = (V,E) – graf

Gdzie:

V – zbiór wierzchołków

E – zbiór krawędzi

Grafy:

Skierowane

Nieskierowane

Spójność grafu

Graf G jest spójny , jeśli każde dwa wierzchołki można połączyć

ścieżką.

a) Graf spójny

b) Graf niespójny

Dwuspójność grafu

Graf G jest dwuspójny , jeśli między każdymi dwoma wierzchołkami

istnieją dwie różne ścieżki. Jeśli graf zawiera tylko 2 węzły, to jest

dwuspójny .

Punkt artykulacji (wierzchołek rozdzielający) – jego usunięcie

„rozspujnia” graf (dzieli na dwuspójne składowe ).

Silna spójność grafu

Graf skierowany G jest silnie spójny , jeśli dla każdych dwóch

wierzchołków v i w grafu G istnieją ścieżki skierowane z v do w oraz z

w do v .

Jeśli G nie jest silnie spójny, to można podzielić go na co najmniej dwie

silnie spójne składowe .