102627

Formalna definicja drogi (język modelowania ST), podaj przykład

Drogą - w grafie G , z węzła a do węzła b nazywać będziemy ciąg :

< a, k,..., i, j,..., 1, b > taki, że : a, k, i, j ,1, b e W oraz:

<(a,k),(k,(..., i),(i, j),(j,..),..,(.. ,1),(1 ,b)> eWxW

Węzeł a będziemy nazywać WĘZŁEM POCZĄTKU DROGI, natomiast węzeł b

WĘZŁEM KOŃCA DROGI.

Drogą nazywamy ciąg łuków bądź wierzchołków.

Drogą minimalną w sensie struktury w zbiorze P^A nazywamy drogę pe P*^b z węzła a do węzła b o minimalnej liczbie węzłów lub łuków. Dla P^A* 0 istnieje zawsze co najmniej jedna droga minimalna.

Drogą cykliczną w grafie G=<W,L> nazywamy drogę p€ P^A, gdy a=b (a, b eW).