Przykładowe zadania egzaminacyjne z teorii grafów
Lp. Zadanie
6 7 8 9 10
1. Wyjaśnij w oparciu o tw. Halla, dlaczego w grafie podanym na rysunku nie
ma skojarzenia pełnego względem zbioru V1 = {1, 2, 3, 4, 5}.
1 2 3 4 5
2. W podanej sieci (przy jej łukach podano przepustowości) znane są
x
następujące przepływy: f (v, s) = 1, f (s, y) = 3, f (v, y) = 1, f (z, x) = 0,
6
f (z, t) = 1, f (x, t) = 3. 3
3 1
Wyznacz przepływy w pozostałych łukach tak, aby został w sieci
2 2
s v t
zdefiniowany przepływ z s do t.
Wyznacz wartość przepływu przez całą sieć i wartość przepływu przez
1 2
3 3
przekrój zadany zbiorem węzłów {s, v, y}.
W oparciu o tw. Forda i Fulkersona rozstrzygnij, czy uzyskany przepływ jest y
maksymalny w tej sieci.
3. W pewnym kraju Unii Europejskiej jest 9 dużych miast. Pomiędzy każdą parą miast zbudowana jest wygodna autostrada.
Rolnicy tego kraju, niezadowoleni z wysokości dopłat bezpośrednich, postanowili zablokować te autostrady wysypując na
nie efekty swojej pracy. Jednak płodów rolnych starczyło im tylko na zablokowanie po jednym kierunku ruchu z każdej
autostrady. Rozstrzygnij z uzasadnieniem, czy premier tego kraju będzie mógł odwiedzić samochodem, nie łamiąc
przepisów ruchu drogowego, wszystkie duże miasta, zaczynając podróż z dowolnego i odwiedzając każde tylko raz. Czy
może być pewny, że wróci do miasta, z którego wyruszy?
1 4 7
4. W grafie pokazanym na rysunku zaznaczono skojarzenie (krawędzie
pogrubione). Za pomocą kolejnych dróg powiększających względem
10
skojarzenia wyznacz w tym grafie skojarzenie maksymalne.
2 5 8
Czy wyznaczone skojarzenie jest doskonałe? Odpowiedzi uzasadnij.
Wskaż w grafie jakiekolwiek minimalne pokrycie krawędziowe.
11
Podaj ogólny związek liczby elementów w wyznaczonym skojarzeniu
3 6 9
i pokryciu.
5. Podaj, które z grafów pokazanych na rysunkach
G5
są ze sobą izomorficzne, a które nie są.
G2
G6
G1 G3 G4
6.
Rozważ graf o liczbie wierzchołków n e" 3 i jego dopełnienie. Wyprowadz
i podaj warunek dla stopni wierzchołków w
grafie, który zapewni, że w dopełnieniu tego grafu będzie spełniony warunek dostateczny istnienia cyklu Hamiltona z
tw. Ore.
7. Rozstrzygnij z uzasadnieniem prawdziwość następujących stwierdzeń:
1. Jeżeli w grafie G istnieje cykl Eulera, to w grafie krawędziowym L(G) także istnieje cykl Eulera.
2. Jeżeli w grafie krawędziowym L(G) istnieje cykl Eulera, to w grafie G także istnieje cykl Eulera.
8. Rozstrzygnij z uzasadnieniem, czy graf, którego zbiorem wierzchołków jest zbiór kodów Graya rzędu 3, a krawędzie
łączą dwa kody różniące się dokładnie na jednej pozycji, jest grafem dwudzielnym.
W podanym grafie wyznacz: a g
d
9.
a) maksymalną liczbę dróg krawędziowo rozłącznych pomiędzy parą
wierzchołków v i w,
v b e h w
b) minimalny zbiór krawędzi rozspajający te wierzchołki.
Zilustruj krawędziową wersję tw. Mengera na powyższych zbiorach.
Rozstrzygnij z uzasadnieniem, czy ten graf jest 4-spójny krawędziowo?
c j
f
10. Czy dla grafu o 9 wierzchołkach, w którym suma stopni wierzchołków wynosi 58 jego dopełnienie może być grafem
spójnym? Odpowiedz
dokładnie uzasadnij bez konstruowania i rysowania grafu.