Zadania

znalezione zostaną wszystkie możliwe ścieżki długości do S. i tak dalej: w n-tej iteracji mamy wykryte wszystkie przejścia długości 2" i mniejsze. Czyli ostatecznie: każda ścieżka w grafie G₀ długości 2” lub mniejszej znajdzie swoje odzwierciedlenie w postaci pojedynczej krawędzi we wszystkich grafach G_{; T} gdzie i>n, G; oznacza grał uzyskany \v i-tej iteracji za pomocą przedstawionego algorytmu.

Oznacza to. że aby wykryć, że dwa wierzchołki oddalone od siebie o n są połączone drogą, muszę wykonać i iog_:nl iteracji, jeśli np. n=5 to 2 iteracje nie starczą, stąd zaokrąglenie w górę.

Przedstawiając problem w funkcji liczby wierzchołków: najgorszym grafem dla podanego algorytmu jest ścieżka k-wierzchołkowa i pytanie, czy wierzchołki krańcowe są połączone. Wówczas trzeba wykonać I"log- (k-1)] iteracji.

(k wierzchołkowa ścieżka ma długość k-l). Po tej liczbie iteracji dla każdego grafu k-wierzcholkowego odpowiedź będzie prawidłowa.

55. Dana jest siatka prostokątna o rozmiarze k*k. De różnych dróg prowadzi z lewego dolnego rogu siatki [punktu A* 0.0)1 do prawego górnego rogu [punk fu B(k,k)] ? Z 'węzła do węzła siatki można poruszać się tylko w górę lub w

prawo.

Na początku należy zauważyć kilka podstawowych rzeczy-:

a)    n3 każda drogę prowadząca z punktu A do punktu B składa się dokładnie 2k ruchów podstawowych (oznaczmy je umownie u dla ruchu w górę i r dla ruchów' w prawo).

b)    na każdą drogę składa się dokładnie k ruchów g i k ruchów p.

W naszym przykładzie k=5. Oznacza to, że przejście z punktu A do punktu B zajmuje 10 ruchów podstaw'owych. Dla drogi przedstawionej na rysunku jest to ciąg: (u,r,r,r,u,r,u;r,u,u).

Jeśli ponumerujemy ruchy od l do 2k to możemy zdefiniować zbiór ruchów M={ l,2,3,4,.„,2k}.

Zbiór ten zawsze możemy podzielić na dwa równoliczne podzbiory TJ i R, gdzie U jest zbiorem tych ruchów, w których idziemy w górę, a R zawiera ruchy, tv których idziemy w prawo. Przy tym zbiory te są rozłączne, a ich suma daje M.

W naszym przykładzie U={ 1,5,7,9,10}, R={2,3,4,6,8}. Liczba możliwych dróg z punktu A do Sjest równa liczbie możliwych do utworzenia w taki sposób zbiorów. Oczywiście zbiory te to nic innego, jak kombinacje k-elementowe w zbierze 2k-eIementowym M (bez powtórzeń - nie można dwa razy wykonać ruchu o tym samym numerze). Czyli:

Lp.DrógA3

Zadanie to można uogólnić na siatkę nie koniecznie kwadratową. Wtedy po prostu zbiory R i Ti nie są równo liczne, ale ich proporcje pozostają takie same dla wszystkich dróg. Przykładowo, jeśli mamy punkt}' A(rl.y3) i B(x2,y2) (przy założeniach tKt? i yl<y2), to musimy iść d^-(x2-r3) razy w prawo i dy=(y2-yl) razy w górę. Całkowita liczba ruchów to dm~(d5+dy). a liczba możliwych dróg wynosi:

Lp.Dróg^ =

d\ /dm\ dy /dm\    / (drc-Kty)! \

^dm    ' dy ' V d.x!*dy! )

__ ~_

56. Problem najcięższego podgrafu rozmiaru k jest zdefiniowany następująco: Dany jest graf obciążony G. Znajdź taki jego podgraf G' rozmiaru k (tj. mak wierzchołków), by sumaryczna waga wszystkich krawędzi indukowanych przez wierzchołki grafu G’ w grafie G była maksymalna pośród wszystkich innych podgrafów rozmiaru k.

Udowodnij, że probiera najcięższego podgrafu jest trudny.

Udowodnimy, że problem znalezienia kliki rozmiaru k w grafie jest w relacji alfa z naszym problemem najcięższego podgrafu stopnia k (w skrócie PNP).

A więc:

KLIKA a PNP Dowód:

Mamy graf G i problem znalezienia kliki w nim. Obciążamy więc wszystkie krawędzie jedynkami i wysnuwamy

twierdzenie:    ¹----

W grafie istnieje klika rozmiaru k w waga sumaryczna nojcięższego podgrafu stopnia k w tym grane wynosi k“(k-l)/2 Inaczej mówiąc, mając algorytm rozwiązywania PNP bez problemu rozwiążemy każdy problem kliki.

Dowód w prawo: jeśli w grafie istnieje klika rozmiaru k to jest to podgraf pełny, a więc ma k*(k-I)/2 krawędzi. Stąd jego sumaryczna waga. 1 jest to maksymalny laki podgraf, bo nic ma innego, który by miał więcej krawędzi (to nie ma krawędzi wielokrotnych). Dowód w- lewo: Jeśli maksymalny podgraf ma sumaryczną wagę k*(k-I) to znaczy, że ma nie krawędzi i dalej idąc oznacza to, że jest grałem pełnym rozmiaru k {nie ma krawędzi wielokrotnych). A każdy graf pełny rozmiaru k jest kliką rozmiaru k.