Zadania

if A[from\Y,too\V] then Jest Droga eke INieMaDrogi; end;

Jaka jest minimalna wartość x, by algorytm, dla grafu k-wierzcholkowego zawsze zwracał poprawną odpowiedź Operacja A*A+A jest operacją na wartościach logicznych, fj. A*A jest algebraicznym mnożeniem macierzy z operacją iloczynu logicznego na elementach, a A-?-A jest operacją sumowania logicznego eiemenrów.

Rozwiązanie najlepiej przedstawić na bazie przykładowego rysunku. Oto graf G i reprezentująca go macierz przejść A:

Teraz przeprowadzimy operację A* A

	i:	2	3	4	5
1	r i	F	F	F	F
2	T	F	T	F	f
3	F	F	F	T	r
4	T	F	F	F	T
5	p	I	F	F	F

X

	1 I^2	3	4 | 5
1		F	F1F
2	T|F	T	F	F
3	Fi F	F	T	F
4	Ti F	FIFlT
5	F|T	F|F|F

	l (213|4 j 3
1	F 1 F | F i F 1 F
2	r | F | F | T i ?
3	TlFlFlFlT
4	F i T j F i F ! F
5	Tl F|Ti FIF

	1	- 1 3 | 4 | 5
;	F	FjFfFlF
n	T	F | T | F j F
3	F	F j F 1 T f f
4	T	F|FI FIT
5	F	T( F1F j F

Wszelkie oznaczenia grafów i macierzy będą indeksowane numerami iteracji. Czyli na początku mamy graf Go i kodującą go macierz Aq. Co się dzieje podczas mnożenia ? Rozpatrzmy, co otrzymujemy po mnożeniu w i-tym wierszu i j-tej kolumnie (zakładam, że w wierszach mamy docelowe, a w kolumnach początkowe wierzchołki krawędzi). Są to dwa wektory - w pierwszym znajduje się informacja o wszystkich wejściach do i-tego wierzchołka, w drugim wszystkie wyjścia z wierzchołka j-tego. Z definicji mnożenia macierzy i zdefiniowanych operacji logicznych wynika algorytm postępowania. Bierzemy pierwszy element z wiersza (czyli oznajmiający⁷, czy istnieje krawędź Wl->Wi) i pierwszy element z kolumny (krawędź Wj->W1) i mnożymy je logicznie. Jeśli obie krawędzie istnieją, oznacza to istnienie przejścia Wj->Wi->WI, a jest to równoważne otrzymanemu wynikowi mnożenie T*T=T. Operację powtarzamy biorąc kolejne pary elementów z wektorów, co odpowiada badaniu przejść z Wj do Wi przez wszystkie kolejne wierzchołki W.x. Wyniki sumujemy logicznie. Łatwo zauważyć, że na dobrą sprawę mnożenie wektorów można zakończyć już po wykryciu pierwszego przejścia, ale standardowa definicja mnożenia macierzy każe inaczej. Tak więc ostatecznie w wyniku mnożenia i-tego wiersza przez j-tą kulumnę w macierzy⁷ wynikowej na pozycji (ij) mamy informację, czy można przejść z wierzchołka i-tego do j-tego pośrednio przez jakiś inny wierzchołek: Natomiast po uogólnieniu - operacja mnożenia Ao*A*> daje w wyniku macierz A_!t w której

jako wynik mamy wszystkie przejścia pośrednie (z jednym wierzchołkiem pośrednim) bazujące na

	ll	1 2 j	13	4	3
I	F	FI	IF	F	F
2	F	FI	i F	T	F
3	T	Fj	: F	7	T
4	p	Ti	F	F	r
5	T|	i F |	T	F	F

	1	2|3l4|5
1	F	F| F	F|F
2	T	f(t	f If
3	F	F i F	T|F
4	T	f) F	f|t
5	F	T|F	F t F

	1	i 2 | 3 i 4 | 5
1	F|	|FIr|Fj F
+1	T	f!t! Tj F
3	T	FI f|T i T i
4	T	Tl FlFj I
5	T	Tl T[T i r

przejściach w macierzy Ao. W tym wypadku, po pierwszym mnożeniu, w macierzy wynikowej znalazły się wszystkie ścieżki (przejścia) długości 2.

Uzyskaliśmy więc nowy graf G₍, w którym każda krawędź postaci w^rt->w₂ oznacza, że w grafie Go istnieje ścieżka w,->w_s->w₂, gdzie w⁷x oznacza jakiś wierzchołek pośredni. Następną operacją jest dodawanie. Co ono daje ? Po prostu do nowo uzyskanego grafu Gt dodajemy krawędzie grafu Go (niejako stracone w trakcie mnożenia macierzy). W ten sposób graf Gj zawiera zarówno przejścia pośrednie jak też i bezpośrednie.

Teraz przechodzimy do następnej iteracji. Kolejne mnożenie Ai*Ai daje nam w⁷ wyniku macierz A₂ znów⁷ zawierającą wszystkie przejścia pośrednie, bazujące jednak na przejściach z grafu Gi, a nie Go- Uzyskany graf G₂ będzie zawierał wszystkie możliwe przejścia długości 2 w stosunku do grafu G_t. Aby zrozumieć, jakie ma to znaczenie, najlepiej przejścia rozpisać: jeśli w grafie G₂ mamy krawćź VV_a->W_b oznacza to, że w grafie Gj istnieje ścieżka długości 2:

W_a->\V_c->W_b. gdzie W_e jest jakimś wierzchołkiem pośrednim w tym grafie.

Istnienie krawędzi W_a->W_e oraz W_c->\V_b w grafie G_t oznacza natomiast, że w⁷ grafie Gc(pierwotnym) istnieją połączenia pośrednie, bądź też bezpośrednie miedzy wierzchołkami a i c oraz c i b, czyli są to ścieżki długości 1 mb 2. Załóżmy przykładowo, że połączenia te są pośrednie, czyli mają długość 2. Oznacza to, że istnienie krawędzi w grafie G2 odzwierciedla istnienie ścieżki o długości |\Va->Wb! - fWa->Wc! + |Wc->\Vc{ =2+2=4- w‘grafie G₀' Można więc powiedzieć, że każda ścieżka długości 4 w grafie G₀ znajdzie odzwierciedlenie w postaci krawędzi w grafie G_:. Pamiętamy też. żc graf Gi zawiera także wszystkie połączenia bezpośrednie (długości 1), stąd zbiór możliwych długości ścieżek jest szerszy:

lWa-> \Vbf = I\Va->Wd + lWc->\Vbi e {2+2;2 +1; 1 +2; 1 +1}={4;3;2 }.

Tak więc wszystkie ścieżki w- grafie G₀ o długościach z podanego zbioru znajdą odzw ierciedlenie w postaci pojedynczych krawędzi w grafie G_:. Operacja sumowania A₂+-Ai dodaje do grafu G; połączenia bezpośrednie (zawarte w Gj), które znów nam umknęły w trakcie mnożenia. Nasza macierz jest gotowa do kolejnej iteracji. Analogicznie jak poprzednio, teraz