Matematyka dyskretna , studia zaoczne inżynierskie
zestaw 7
Drogą Eulera w grafie G=)#V ,E *# nazywamy dowolną drogę przechodzącą przez każdą krawędz
grafu
dokładnie raz, tzn. v , ...., v , taką, że każda krawędz
e"E występuje w ciągu v , ...., v dokładnie raz
1 m+1 1 m+1
e={v , v } dla pewnego i. Jeśli v =v to drogę tą nazywamy cyklem Eulera.
i i+1 1 m+1
Graf zawierajÄ…cy cykl Eulera nazywamy grafem eulerowskim. Graf zawierajÄ…cy drogÄ™ Eulera nazywamy
grafem półeulerowskim.
Twierdzenie Eulera
Niech G będzie grafem spójnym.
i) G jest grafem eulerowskim wttw. gdy każdy wierzchołek w G jest parzysty.
ii) G jest grafem półelerowskim wttw. gdy ma dwa wierchołki stopnia nieparzystego (jest to początek i
koniec drogi Eulera)
Droga Hamiltona to droga przechodząca przez wszystkie wierzchołki, każdy odwiedzając jedynie jeden
raz.
Cykl Hamiltona to zamknięta droga przechodząca przez wszystkie wierzchołki grafu dokładnie raz.
Graf hamiltonowski to graf posiadajÄ…cy cykl Hamiltona.
W odróżnieniu od grafów eulerowskich, grafy hamiltonowskie nie posiadają prostej i szybkiej w użyciu
charakteryzacji. Nie znana jest żadna metoda, pozwalająca szybko (tzn. w czasie wielomianowym)
stwierdzić czy dany graf jest hamiltonowski. Są natomiast znane pewne warunki wystarczające na to, by
graf był hamiltonowski:
Twierdzenie Ore
G=)#V , E *#
Jeśli w grafie prostym o co najmniej trzech wierzchołkach dowolne dwa niesąsiednie
G
wierzchołki v i w spełniają , to graf jest hamiltonowski.
Twierdzenie Diraca
G=)#V , E *#
Graf prosty w którym każdy wierzchołek ma stopień co najmniej |V|/2 jest hamiltonowski.
Graf Dwudzielny- graf G=)#V ,E *# w którym zbiór wierzchołków V da się podzielić na dwa rozłączne
podzbiory V oraz V tak, by żadne dwa wierzchołki w obrębie tego samego podzbioru V nie były
1 2 i
połączone.
Warunek konieczny i dostateczny kojarzenia małżeństw.
Twierdzenie Halla (wersja małżeńska)
W grupie n dziewcząt każda może wybrać męża spośród chłopców, których zna wttw. w każdym podzbiorze
m dziewczÄ…t mán, dziewczyny te znajÄ… co najmniej m chÅ‚opców.
1. Sprawdz
czy podane grafy majÄ… drogÄ™ Eulera, cykl Eulera, drogÄ™ Hamiltona, cykl Hamiltona.
5
6
4
a
b
h i
9
3
8
g
e
c
e
1
7
2
d
f
2. a) Przedstaw ogólną ideę algorytmu znajdywania cyklu Eulera.
b) Za pomocą powyższego algorytmu znajdz
cykl Eulera dla podanego grafu rozpoczynajÄ…c od
wierzchołka v=1.
Wejście: graf G spójny, bez wierzchołków stopnia nieparzystego, reprezentowany za pomocą listy
incydencji, ZA[v], v"V
Wyjście: Cykl Eulera reprezentowany przez ciąg wierzchołków na stosie CE, STOS jest stosem
pomocniczym
top(s)  oznacza szczyt stosu
1 begin
2. STOS:=" ; CE:=";
3.v:= dowolny wierzchołek grafu;
4.STOSKá v {poÅ‚ożenie wierzchoÅ‚ka v na szczyt stosu}
5. while STOS<>" do
6. begin
7. v:= top(STOS);{v = szczytowy element stosu}
8. if ZA[v]<>" then
9. begin
10. u:= pierwszy wierzchołek listy ZA[v]
11. STOSKá u;
12. ZA[v]:=ZA[v]\{u}; ZA[u]:=ZA[u]\{v}; {usuń krawędz
{u,v} z listy incydencji}
13. v:=u;
14. end;
15 else {jeśli ZA[v]="}
16 begin
17.......v Ká STOS; {zdjÄ™cie wierzchoÅ‚ka v ze STOS}
18 CEKá v; {wÅ‚ożenie wierzchoÅ‚ka v na szczyt stosu CE}
19. end;
20. end;
21.end;
K
3. Narysuj grafy pełne dla nd"6 .
n
K
a) Dla jakich n graf jest eulerowski?
n
K
b) Dla jakich n graf jest hamiltonowski?
n
Qn
4. Symbolem oznaczymy graf zwany kostką n-wymiarową. Jego zbiorem wierzchołków jest zbiór
wszystkich ciągów postaci śąa a2,... , an źą, ai"{0,1} . Krawędzie łączą te i tylko te ciagi, które różnią się
1,
dokładnie jednym wyrazem.
a) Ile wierzchołków i krawędzi ma ten graf?
Qn
b) Dla jakich n graf jest eulerowski?
Qn
c) Dla jakich n graf jest hamiltonowski?
W
5. Narysuj grafy będące kołem dla nd"6. Które grafy (koła) są eulerowskie, które zaś
n
hamiltonowskie?
6. Przedstaw cztery pięciowierzchołkowe grafy -- kolejno graf który:
" nie jest hamiltonowski i nie jest eulerowski
" nie jest hamiltonowski, ale jest eulerowski
" jest hamiltonowski i nie jest eulerowski
" jest hamiltonowski i eulerowski.
7. Przypuśćmy, że 4 dziewczyny znają 5 chłopców. Poszczególne znajomości zostały opisane w tabeli.
a) Narysuj odpowiedni graf znajomości,
b) sprawdz
czy jest spełniony warunek kojarzenia małżeństw. Jeśli jest spełniony podaj przykład
takiego skojarzenia maksymalnego(każda dziewczyna, żeby miała męża)
dziewczyna Chłopcy, których zna dziewczyna
d c , c
1 2 4
d c , c , c
2 1 3 5
d c , c
3 2 4
d c
4 4