ofi gs kolos2 s1

Ufu 2004/3003

nę | ■ tratew J »w<t

^,v,wł,'“^f'    \ZLvn.____________________

Nr udania	1	2	3	4	3	^6 r	•	* i^0*—
Punktacja	3	2	2	2	1	3 3	«	Jul Co!
	3			zl	A		\k.

*    ^r*^{ftc s}P^ra"^tlź spełnienie warunku dostatecznego ChvittU na istnienie

cyklu Hamiltona.

Zadanie 2

W podanym grafie sprawdź spełnienie warunku dostatecznego Meyniela aa istnienie cyklu Hamiltona.

Zadanie 3

Czyjełli w podanym grafie skierowanym, wybierzemy losowo i usuniemy jeden z dwóch łuków z każdej pary łączącej dwa wierzchołki, to otrzymamy podgraf zawierający drogę Hamiltona?

Czy taki podgraf będzie w każdym przypadku zawierał cykl Hamiltona? Odpowiedź uzasadnij przytaczając odpowiednie twierdzenia

Zadanie 4

W grafie pokazanym na rysunku wyznacz drzewo przeglądu grafu wszerz zaczynając od wierzchołka 3. Podaj kod Prtlfcra wyznaczonego drzewa rozpinąjąccgo w grafie K*.

Zadanie 5

W grafie K* wyznacz drzewo rozpinające o kodzie Prtlfcra (9,7,9. 3.1.2,4). Zadanie 6

W grafie podanym na rysunku zaznaczono jego drzewo rozpinające.

Wyznacz zbiór wszystkich cykli fundamentalnych względem tego drzewa.

Przedstaw jako różnicę symetryczną cykli fundamentalnych cykl prosty wyznaczony ciągiem wierzchołków (2,3.6.7,4. 5, 2).

Sprawdź wynik za pomocą rachunku zbiorów.

Zadanie 7

W podanym grafie wyznacz:

a)    maksymalną liczbę dróg krawędziowe rozłącznych pomiędzy parą wierzchołków v i w.

b)    minimalny zbiór krawędzi rozspajający wierzchołki v i w.

Zilustruj krawędziową wersję tw. Mengcra na powyższych zbiorach.

Odpowiedz z uzasadnieniem na pytanie, czy ten graf jest 4-spójny krawędziowe? Zadanie 8

W podanej sieci (przy lukach podano wartości przepływów i w nawiasach ich przepustowości) wyznacz:

ai wartość maksymalnego przepływu z s do I za pomocą ścieżek powiększających przepływ.

bj minimalny przekrój*pomiędzy s i t oraz jego przepustowość.

Zfemngtw Forda i Fulkcrsona w podanej sieci.

Zakres punktów	1 11-12	13- 14	15- 16	17-18	19-20
Ocena	3,0	3-5	4-0		*■»