ZEBRANE ZADANIA DOMOWE Z TEORII GRAFÓW
Zadanie 1
1 2 3 4 5 6
1 0 1 0 0 1 0
îÅ‚ Å‚Å‚
Dana jest macierz sÄ…siedztwa pewnego grafu nieskierowanego o postaci: 2 ïÅ‚1 0 0 1 0 1śł
ïÅ‚ śł
ïÅ‚ śł
3 0 0 0 0 1 1
ïÅ‚ śł
4 1 0 0 0 1śł
ïÅ‚0
ïÅ‚1
5 0 1 0 0 0śł
ïÅ‚ śł
6 1 1 1 0 0ûÅ‚
ïÅ‚ śł
ðÅ‚0
Na podstawie tej macierzy:
a. oblicz stopnie wierzchołków grafu,
b. oblicz liczbę krawędzi,
c. narysuj graf.
Zadanie 2
Dla grafu z Zadania 1 narysuj graf będący jego dopełnieniem.
Zadanie 3
Na rysunku grafu z Zadania 1 oznacz w wybrany przez siebie sposób krawędzie grafu i wyznacz macierz
incydencji oraz narysuj graf krawędziowy dla tego grafu.
Zadanie 4
Dla grafu z Zadania 1 narysuj:
a. dwa przykładowe podgrafy o zbiorze wierzchołków V1={1, 2, 3, 6}, które nie są podgrafami
indukowanymi przez zbiór V1,
b. podgraf indukowany przez zbiór V1.
Zadanie 5
1 2 3 4 5 6
1 0 1 0 0 1 0
îÅ‚ Å‚Å‚
ïÅ‚1
2 0 0 1 0 1śł
Dana jest macierz sÄ…siedztwa pewnego grafu skierowanego o postaci:
ïÅ‚ śł
ïÅ‚ śł
3 0 0 0 0 1 0
ïÅ‚ śł
4 1 0 0 1 0śł
ïÅ‚0
ïÅ‚1
5 0 1 1 0 1śł
ïÅ‚ śł
6 1 0 0 1 0ûÅ‚
ïÅ‚ śł
ðÅ‚0
Na podstawie tej macierzy:
a. oblicz stopnie wyjściowe i wejściowe wierzchołków grafu,
b. oblicz liczbę łuków,
c. narysuj graf.
Zadanie 6
Narysuj graf pochodny dla grafu z zadania 5.
Zadanie 7
Graf nieskierowany G1 ma ciąg stopni wierzchołków postaci (6, 5, 4, 5, 5, 6, 3), natomiast graf G2 postaci
(6, 5, 4, 5, 5, 4, 5). Czy grafy te mogą być izomorficzne? Odpowiedz
uzasadnij opierajÄ…c siÄ™ na definicji
izomorfizmu grafów.
Zadanie 8
Zbadaj izomorficzność podanych par grafów.
1 2
1 2
7
5 6 7 6
5
4 3
4 3
a.
1 / 11
1 2
2
3 7
1
8
9 6 8
7 4 5 9
6 5
4 3
b.
Zadanie 9
Zbadaj, które pary grafów są izomorficzne wśród czterech podanych:
1 2 1 2
3 3
6 6
4 4
5 5
1
1 2
6
5
4
5
6
3 2
4 3
Zadanie 10
Skonstruuj graf (nieskierowany) o 4 wierzchołkach, który jest izomorficzny ze swoim dopełnieniem.
Udowodnij izomorfizm tej pary grafów. Narysuj i opisz macierzami incydencji oba grafy. Znajdz
zwiÄ…zek
pomiędzy wyznaczonymi macierzami incydencji.
Zadanie 11
Skonstruuj graf (nieskierowany) o 5 wierzchołkach, który jest izomorficzny ze swoim dopełnieniem.
Udowodnij izomorfizm tej pary grafów. Narysuj i opisz macierzami incydencji oba grafy. Znajdz
zwiÄ…zek
pomiędzy wyznaczonymi macierzami incydencji.
Zadanie 12
Skonstruuj graf (nieskierowany) o 4 wierzchołkach, który jest izomorficzny ze swoim grafem
krawędziowym. Udowodnij izomorfizm tej pary grafów. Narysuj i opisz macierzami sąsiedztwa oba grafy.
Znajdz
związek pomiędzy wyznaczonymi macierzami sąsiedztwa.
Zadanie 13
Skonstruuj graf (nieskierowany) o 5 wierzchołkach, który jest izomorficzny ze swoim grafem
krawędziowym. Udowodnij izomorfizm tej pary grafów. Narysuj i opisz macierzami sąsiedztwa oba grafy.
Znajdz
związek pomiędzy wyznaczonymi macierzami sąsiedztwa.
Zadanie 14
Skonstruuj graf skierowany o 4 wierzchołkach, który jest izomorficzny ze swoim dopełnieniem. Udowodnij
izomorfizm tej pary grafów. Narysuj i opisz macierzami incydencji oba grafy. Znajdz
związek pomiędzy
wyznaczonymi macierzami incydencji.
Zadanie 15
Dla grafu skierowanego
({1, 2, 3, 4, 5}, {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 2), (3, 5), (4, 1), (4, 3), (5, 3), (5, 4)})
utwórz graf pochodny. Dla obu grafów wyznacz macierze incydencji i sąsiedztwa oraz stopnie
wierzchołków. W obu grafach wyznacz stopnie wierzchołków względem zbioru {1, 3, 4}.
2 / 11
Zadanie 16
Narysuj graf relacji binarnej P na zbiorze V = {2, 3, 4, 5, 6, 7} zdefiniowanej następująco: i P j dla i, j " V
Ô! NWD(i, j) = 1 (NWD oznacza najwiÄ™kszy wspólny dzielnik). Graf pochodny dla tego grafu opisz
macierzami incydencji i sąsiedztwa. Wyznacz stopnie wierzchołków w grafie relacji i jego grafie
pochodnym. Wyznacz także stopnie wierzchołków względem zbioru liczb pierwszych zawartych w V.
Zadanie 17
îÅ‚0 0 1 0 0 0Å‚Å‚
ïÅ‚0 0 0 1 0 1śł
ïÅ‚ śł
ïÅ‚0 1 0 1 0 0śł
ïÅ‚ śł
ïÅ‚0 0 0 0 0 1śł
ïÅ‚1 0 0 1 0 0śł
ïÅ‚ śł
ïÅ‚0 0 0 0 1 0śł
ðÅ‚ ûÅ‚
Zbadaj spójność i silną spójność grafu o macierzy sąsiedztwa .
Zadanie 18
Dany jest graf nieskierowany, którego stopnie wierzchołków tworzą ciąg (5, 6, 5, 6, 5, 6, 5, 6).
Oblicz liczbę krawędzi tego grafu i sprawdz
jego spójność.
Zadanie 19
Dany jest graf nieskierowany, którego stopnie wierzchołków tworzą ciąg (3, 2, 3, 7, 3, 3, 2, 5).
Zbadaj spójność tego grafu.
Zadanie 20
Dany jest graf nieskierowany o 10 wierzchołkach i minimalnym stopniu wierzchołka równym 5. Udowodnij,
że taki graf jest spójny. Udowodnij w ogólnym przypadku, że graf o n wierzchołkach i minimalnym stopniu
wierzchołka nie mniejszym od n/2 jest spójny.
Zadanie 21
Dany jest graf skierowany bez pętli o 13 wierzchołkach, dla których zarówno stopnie wyjściowe jak i
wejściowe wynoszą co najmniej 6. Udowodnij, że graf jest silnie spójny.
Zadanie 22
Dla których z wymienionych liczb krawędzi: 30, 36, 42, 48, istnieje graf spójny o 10 wierzchołkach?
Zadanie 23
Czy istnieje graf spójny o co najmniej dwóch wierzchołkach, w którym stopnie wierzchołków tworzą ciąg
kolejnych liczb naturalnych? Odpowiedz
uzasadnij.
Zadanie 24
Narysuj graf o 9 wierzchołkach i 4 składowych spójnych, który ma:
a) 5 krawędzi,
b) 15 krawędzi.
Zadanie 25
2 2 2
1 1
1 3
3 3
7 4 7
8
4 4
7
5
6 6
5 6 5
W podanych grafach: , , ,
metodami przeglądu grafu wszerz i przeglądu w głąb wyznacz ciągi wierzchołków, które zaczynają się od
wierzchołka: a) 1, b) 4, c) 7.
3 / 11
Zadanie 26
Sprawdz
, czy podane grafy sÄ… planarne:
1
2
1
8 2
7 3 7 3
6
8
6 5
4
4
5
1 2
1 2
3
8
3
9 8
7
4
4
7
6 5
6 5
1
1
2 3 2 3
4 4
5 6 5 6
7 8 7 8
Zadanie 27
Posługując się tw. Kuratowskiego wykaż, czy graf o podanym 2 5 8
rysunku jest, czy nie jest planarny.
1 3 6 9 11
4 7 10
Zadanie 28
Czy wśród grafów o 5 wierzchołkach i 9 krawędziach są grafy nieplanarne?
Odpowiedz
uzasadnij w oparciu o tw. Kuratowskiego.
Zadanie 29
Graf ma n wierzchołków i m krawędzi.
W którym z podanych przypadków wykluczona jest planarność grafu?
a) n = 4 i m = 6,
b) n = 5 i m = 8,
c) n = 6 i m = 13,
d) n = 7 i m = 14,
e) n = 8 i m = 19.
Odpowiedz
uzasadnij w oparciu o warunek konieczny wynikajÄ…cy z wzoru Eulera.
4 / 11
Zadanie 30
5
Rozstrzygnij z uzasadnieniem,
czy podane grafy sÄ… dwudzielne:
3 4
1
2 4 6
1
2
3
7
7 6 5
Zadanie 31
Sprawdz
, czy podane grafy sÄ… dwudzielne:
1
1
2
7 2
7
3
6 3
6
4
5
5 4
Zadanie 32
Sprawdz
na podstawie podanej macierzy sÄ…siedztwa grafu, nie rysujÄ…c go, czy istnieje w nim droga lub cykl
Eulera. W przypadku odpowiedzi pozytywnej, narysuj graf i wyznacz za pomocÄ… algorytmu Fleury ego
drogÄ™ lub cykl Eulera.
0 1 1 0 1 0 1
îÅ‚ Å‚Å‚
ïÅ‚1 0 1 1 1 1 1śł
ïÅ‚ śł
ïÅ‚ śł
1 1 0 1 0 1 0
ïÅ‚ śł
ïÅ‚0 1 1 0 0 1 1śł
ïÅ‚1 1 0 0 0 0 0śł
ïÅ‚ śł
ïÅ‚0 1 1 1 0 0 1śł
ïÅ‚1 1 0 1 0 1 0śł
ðÅ‚ ûÅ‚
Zadanie 33
StosujÄ…c algorytm Fleury ego wyznacz drogÄ™ Eulera w grafie.
g
f h
a b c d e
6 7 8
1 2 3 4 5
Zadanie 34
Rozstrzygnij z uzasadnieniem, czy grafy o podanych rysunkach sÄ… Eulerowskie:
Jeśli są, to w każdym z nich wyznacz drogę (cykl) Eulera za pomocą algorytmu Fleury ego.
5 / 11
Zadanie 35
Czy po dodaniu do pierwszego z grafów podanych w zadaniu 34:
a) 1, b) 2, c) 3 krawędzi można uzyskać graf, w którym będzie istniała droga Eulera?
Odpowiedz
zilustruj na rysunku.
Zadanie 36
Czy graf pochodny dla dowolnego Eulerowskiego grafu skierowanego jest zawsze Eulerowski? Odpowiedz

uzasadnij!
Zadanie 37
Czy graf krawędziowy dla grafu Eulerowskiego jest zawsze Eulerowski? Odpowiedz
uzasadnij!
Zadanie 38
W grafach z zadania 34 zamień każdą krawędz
na łuk tak, aby powstały z nich Eulerowskie grafy
skierowane.
Zadanie 39
W poniższych grafach sprawdz
, czy są spełnione warunki dostateczne istnienia cyklu Hamiltona:
a) z tw. Diraca b) z tw. Ore c) tw. Chvátala. Znajdz
w nich, jeśli istnieje, cykl Hamiltona.
1 2 1 2
7 3 7 3
6 4 6 4
5 5
Zadanie 40
W podanych grafach sprawdz
niezależnie, które z omawianych warunków dostatecznych istnienia cyklu
Hamiltona dla grafów nieskierowanych (tw. Ore, Diraca, Chvátala, o liczbie krawÄ™dzi i inne) sÄ… speÅ‚nione, a
które nie:
2 2 2
1 1 1
3 3 3
7 7 7
4 4 4
6 6 6
5 5 5
2 2
2
1 1
1 3
3 3
7 7 4
8
4 4
7
5
6 6
5 5 6
Zadanie 41
Osiem komputerów połączono w sieć. Liczby komputerów, z którymi każdy z nich ma bezpośrednie
dwukierunkowe połączenie wynoszą: 3, 5, 3, 4, 3, 5, 5, 6. Jeden z komputerów wysyła sygnał do wszystkich,
z którymi ma bezpośrednie łącze. Każdy z komputerów, otrzymawszy sygnał, przesyła go do kolejnych w
następnym kroku czasowym. Czy jest możliwe, aby sygnał dotarł do wszystkich komputerów i wrócił do
komputera początkowego w ośmiu krokach czasowych?
Zadanie 42
Dany jest graf o następujących stopniach wierzchołków: 3, 3, 4, 3, 5, 3, 2, 3. Wykaż, że dopełnienie tego
grafu posiada cykl Hamiltona.
6 / 11
Zadanie 43
Wykaż, że graf krawędziowy grafu o następujących stopniach wierzchołków: 2, 4, 4, 4, 2, 4, 4, jest grafem
hamiltonowskim.
Zadanie 44
Sprawdz
, czy w poniższych grafach są spełnione:
a. warunek dostateczny z tw. Nasha-Williamsa dla istnienia cyklu Hamiltona,
b. silna spójność grafu,
c. warunek dostateczny z tw. Meyniela dla istnienia cyklu Hamiltona.
Wyznacz, jeśli istnieją, cykle Hamiltona.
1 2
1 2
6 3
6 3
5 4
5 4
Zadanie 45
W podanych grafach skierowanych sprawdz
, czy spełnione są warunki dostateczne istnienia cyklu Hamiltona
z tw. Meyniela i Nasha-Williamsa:
1
1 2 3 2 3 1 2 3
4 5 6 4 5 6 4 5 6
Zadanie 46
W podanych grafach sprawdz
, czy spełnione są warunki dostateczne istnienia cyklu Hamiltona z tw. Redei,
Thomassena i Camiona:
2 2
1 3 1 3
5 4 5 4
Zadanie 47
W podanych grafach wyznacz kolejności wierzchołków oraz drzewa przeglądu grafu dla przeglądów wszerz
i w głąb, które zaczynają się od wierzchołków: dla grafu a. od 3 i 7, dla grafu b. od 1 i 7.
a. b.
1
1
8 2
8 2
7 3
7 3
6 4
6 4
5
5
7 / 11
Zadanie 48
W podanych grafach wyznacz kolejności
2 2
2
wierzchołków oraz drzewa przeglądu grafu dla
1 1
1 3
3 3
przeglądów wszerz i w głąb, które zaczynają
się od wierzchołków:
7 4 7
8
a) 1,
4 4
7
5
6 6
b) 4,
5 6 5
c) 7.
Zadanie 49
Wyznacz kody Prüfera
2 2 2
dla następujących drzew
1 3 1 3 1 3
rozpinajÄ…cych w grafie K8:
4 4 4
8 8 8
Odp.:
7 7 7
5 5 5
a) (6, 3, 2, 5, 5, 8);
6 6 6
a) , b) , c) .
b) (2, 3, 8, 6, 4, 3);
c) (2, 1, 4, 8, 6, 4).
Zadanie 50
Wyznacz kod Prüfera dla drzewa:
1 3 10 11
2
9
4 7 8 12
5 6
Zadanie 51
W grafie K9 wyznacz i narysuj drzewa a) (1, 2, 3, 4, 5, 6, 7),
rozpinajÄ…ce o nastÄ™pujÄ…cych kodach Prüfera:
b) (2, 2, 3, 2, 1, 8, 9),
c) (7, 4, 4, 4, 4, 4, 3),
d) (9, 7, 5, 3, 1, 2, 4),
e) (5, 6, 4, 7, 3, 8, 2).
Zadanie 52
Dane sÄ… kody Prüfera dla drzew rozpinajÄ…cych: (3, 3, 4, 5, 6, 9, 6, 5, 7, 7) i (2, 3, 4, 3, 6, 7, 7, 8, 10, 8, 12).
Wyznacz i narysuj te drzewa na podstawie kodów.
Zadanie 53
Wyznacz liczbę wszystkich zer w macierzy incydencji grafu nieskierowanego, który jest drzewem
rozpinajÄ…cym o kodzie Prüfera (10, 3, 4, 4, 7, 9, 2, 2, 5, 1). Odp.: 110.
Zadanie 54
2
W grafie podanym na rysunku zaznaczono jego drzewo rozpinajÄ…ce.
1
Wyznacz wszystkie cykle fundamentalne względem tego drzewa i przedstaw
3
jako różnicę symetryczną takich cykli następujące cykle proste w grafie:
7
a) {{1, 2}, {2, 3}, {3, 6}, {1, 6}},
b) {{1, 4}, {4, 5}, {5, 6}, {1, 6}},
4
6
c) {{1, 4}, {3, 4}, {3, 6}, {1, 6}}.
5
8 / 11
Zadanie 55
1
7 2
3
6
5 4
Dla grafu na rysunku:
a. znajdz
wszystkie cykle fundamentalne względem drzewa rozpinającego o zbiorze krawędzi
T={ {1,5},{2,4},{3,4},{4,7},{5,7},{6,7}} oraz przedstaw cykle proste:
{{1,6},{6,7},{4,7},{3,4},{1,3}} i {{1,6},{2,6},{2,5},{3,5},{1,3}}, jako różnice symetryczne
odpowiednich cykli fundamentalnych,
b. znajdz
wszystkie cykle fundamentalne względem drzewa rozpinającego o zbiorze
T={{1,6},{2,5},{2,6},{3,5},{4,7},{5,7}} oraz przedstaw cykle proste:
{{1,3},{3,4},{4,7},{5,7},{1,5}} i {{2,6},{2,4},{3,4},{1,3},{1,6}}, jako różnice symetryczne
odpowiednich cykli fundamentalnych.
Zadanie 56
2 5
Wyznacz w podanym grafie maksymalną liczbę dróg krawędziowo
rozłącznych, które łączą wierzchołki 1 i 8. Podaj przykładowy zbiór
takich dróg, który ma maksymalną moc. Co na podstawie mocy tego
1 3 6 8
zbioru można powiedzieć o minimalnej liczbie krawędzi w zbiorze
rozspajającym 1 i 8? Wskaż zbiór rozspajający 1 i 8 o wskazanej mocy.
4 7
Zadanie 57
Czy podany graf jest 3-spójny?
Ile wynosi jego spójność wierzchołkowa?
Odpowiedzi uzasadnij.
Zadanie 58
2 7 9
1
11
3 4 8 10
5 6
Dany jest graf spójny, niekierowany:
a. wskaż zbiór rozspajający graf o mocy 4,
b. wskaż zbiór rozspajający graf o mocy 3,
c. wskaż zbiór rozdzielający graf o mocy 3,
d. wskaż zbiór rozdzielający graf o mocy 2,
e. wskaż zbiory rozspajające pary wierzchołków: 1 i 6, 1 i 11,
f. zastosuj twierdzenie Mengera w wersji krawędziowej do wyznaczenia minimalnej mocy zbiorów
rozpajających dla powyższych par.
g. zastosuj twierdzenie Mengera w wersji wierzchołkowej do wyznaczenia minimalnej mocy zbioru
rozdzielającego wierzchołki 1 i 11,
h. wykaż 3-spójność krawędziową grafu,
i. wykaż 2-spójność (wierzchołkową) grafu,
j. sprawdz
, czy graf jest 3-spójny (wierzchołkowo),
k. wyznacz spójność krawędziową grafu,
l. wyznacz spójność wierzchołkową grafu.
9 / 11
Zadanie 59
a g
d
v
b e h w
c j
f
W podanym grafie wyznacz:
a) maksymalną liczbę dróg krawędziowo rozłącznych pomiędzy parą wierzchołków v i w,
b) maksymalną liczbę dróg krawędziowo rozłącznych pomiędzy parą wierzchołków d i j,
c) maksymalną liczbę dróg wierzchołkowo rozłącznych pomiędzy parą wierzchołków v i w,
d) maksymalną liczbę dróg wierzchołkowo rozłącznych pomiędzy parą wierzchołków d i c,
e) minimalny zbiór krawędzi rozspajający wierzchołki v i w,
f) minimalny zbiór krawędzi rozspajający wierzchołki d i j,
g) minimalny zbiór wierzchołków rozdzielający wierzchołki v i w,
h) minimalny zbiór wierzchołków rozdzielający wierzchołki d i c,
i) spójność krawędziową,
j) spójność wierzchołkową.
Zilustruj obie wersje tw. Mengera na powyższych zbiorach. Odpowiedz z uzasadnieniem na pytania:
a) czy ten graf jest 3-spójny?
b) czy ten graf jest 3-spójny krawędziowo?
c) czy ten graf jest 2-spójny?
Zadanie 60*
W podanym grafie wyznacz:
S 1 2 3
T
a) wszystkie S-T drogi,
b) co najmniej trzy różne S-T separatory
(różne od zbiorów S i T),
c) S-T separator o minimalnej mocy różny od zbiorów
4 5 6
S i T,
d) co najmniej dwa różne S-T konektory,
e) S-T konektor o maksymalnej mocy.
7
Zilustruj uogólnione tw. Mengera na powyższych zbiorach. 8 9
Zadanie 61*
W podanym grafie wyznacz:
S 1 2 3
T
a) wszystkie S-T drogi,
b) co najmniej trzy różne S-T separatory
(różne od zbiorów S i T),
c) S-T separator o minimalnej mocy,
4 5 6
d) co najmniej trzy różne S-T konektory,
e) S-T konektor o maksymalnej mocy.
Zilustruj uogólnione tw. Mengera na powyższych zbiorach.
7 8 9
10 / 11
Zadanie 62
W podanej sieci o przepustowościach łuków równych 4 i 5
przepływach: f (a) = 4, f (b) = 3, f (d) = 2, f (e) = 1, f (f ) = 1,
e
k
f (g) = 1, f (i) = 1, wyznacz: i
1
c
a) wartości brakujących przepływów przez łuki tak, aby
a
b
2 4 6
powstał przepływ przez sieć z 2 do 6,
g
d
h
b) wartość wyznaczonego przepływu przez sieć,
3
j
f l
c) wartości przepływów przez przekroje zadane zbiorami {2,
3, 4}, {2, 5, 7} i {1, 2, 3, 7},
7
d) tylko na podstawie wartości wyznaczonych w punktach b) i
c) wyznacz wartości przepływów przez przekroje zadane
zbiorami {1, 3, 4, 6}, {1, 5, 6, 7} i {4, 5, 6}.
Odp.: b) 8; c) 11, 10, 10; d) 2, 3, 2.
Zadanie 63
W podanej sieci o przepustowościach łuków równych 4 i przepływach: f (a) = 3 4
g
1, f (c) = 2, f (d) = 1, f (f ) = 2, f (h) = 1, f (k) = 1, f (l) = 3, wyznacz: d
b
a) wartości brakujących przepływów przez łuki tak, aby powstał
1
2
j
a
przepływ przez sieć z 6 do 4,
h
i
f
b) wartość wyznaczonego przepływu przez sieć,
e
c
7
c) wartości przepływów przez przekroje zadane zbiorami
l
{1, 2, 6}, {1, 3, 5, 6} i {3, 5, 6, 7},
k
6 5
d) tylko na podstawie wartości wyznaczonych w punktach b) i c)
wyznacz wartości przepływów przez przekroje zadane zbiorami {3,
4, 5, 7}, {1, 2, 4} i {2, 4, 7}.
Odp.: b) 7; c) 9, 10, 10; d) 2, 3, 3.
Zadanie 64
1 (1)
W podanej sieci (przy łukach podano wartości przepływów i w
u x
2 (3)
nawiasach ich przepustowości) wyznacz: 1 (3)
2 (3)
1 (2)
2 (2)
a) wartość maksymalnego przepływu z s do t za pomocą ścieżek
1 (3)
powiększających przepływ, 1 (2)
2 (2)
y
s v t
b) minimalny przekrój pomiędzy s i t oraz jego przepustowość.
1 (1)
1 (2)
Zilustruj tw. Forda i Fulkersona w podanej sieci.
1 (3)
2 (3) 1 (2)
w z
Odp.: a) 6. 1 (2)
Zadanie 65
1 (2)
W podanej sieci (przy łukach podano wartości przepływów i w
u x
3 (4)
nawiasach ich przepustowości) wyznacz: 2 (3)
2 (3)
0 (1)
1 (2)
a) wartość maksymalnego przepływu z s do t za pomocą ścieżek
1 (3)
powiększających przepływ, 2 (2) 1 (2)
y
s v t
b) minimalny przekrój pomiędzy s i t oraz jego przepustowość.
0 (1)
1 (1)
1 (2)
Zilustruj tw. Forda i Fulkersona w podanej sieci.
3 (4) 1 (2)
w z
2 (3)
Odp.: a) 8.
* nadobowiÄ…zkowe
11 / 11