Zadanie 1.
(a) (obowiązkowe)
Zdefiniowana poniżej funkcja c (i, j) okreS
la przepustowoS
ci łuków w sieci S.
Skonstruuj w S przepływ maksymalny metodą S
cieżek powiększających. Udowodnij, że jest to przepływ maksymalny.
1 gdy (i s) (1 j 6),
( j t) (7 i 11);
c(i,j) =
gdy (1 i 6) (7 j 11)
(b) W grafie dwudzielnym G = (V1 V2, E) wyznacz skojarzenie maksymalnej mocy.
Czy w tym grafie istnieje skojarzenie maksymalne, które nie jest skojarzeniem maksymalnej mocy?
(c) Czy w G istnieje skojarzenie pełne względem V1?
Czy G ma skojarzenie pełne względem V2?
(d) Wyznacz w G maksymalną liczbę krawędzi niezależnych; wskaż zbiór krawędzi niezależnych o maksymalnej mocy.
(e) Wyznacz w G minimalną liczbę wierzchołków pokrywających wszystkie krawędzie; wskaż zbiór wierzchołków
pokrywających o minimalnej licznoS
ci.
(f) Wyznacz w G maksymalną liczbę wierzchołków niezależnych; wskaż odpowiedni zbiór wierzchołków.
(e) Wyznacz w G minimalną liczbę krawędzi pokrywających wszystkie wierzchołki i wskaż odpowiedni zbiór krawędzi.
V1
V2
V1
V1 V2
V2
1
7
S: G:
1 G:
G:
1
1
7
7
7
2
8
2
2
2
3 8
8
8
s 3
9 t 3
3
4
9
9
9
10 4
4
4
5
10
10
10
5
5
5
11
6
11
11
11
6
6
6
V1 V1
V2 V1 V2
V2 V1
V2
G: G:
G:
1 1 G:
1
1
7 7
7
7
2 2
2
2
8 8
8
8
3 3
3
3
9 9
9
9
4 4
4
4
10 10
10
10
5 5
5
5
11 11
11
11
6 6
6
6