Matematyka dyskretna , studia zaoczne inżynierskie

zestaw 7

Drogą Eulera w grafie

G=〈V , E 〉

nazywamy dowolną drogę przechodzącą przez każdą krawędź grafu

dokładnie raz, tzn. v

1

, ...., v

m+1

, taką, że każda krawędź e∈E występuje w ciągu v

1

, ...., v

m+1

dokładnie raz

e={v

i

, v

i+1

} dla pewnego i. Jeśli v

1

=v

m+1

to drogę tą nazywamy cyklem Eulera.

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

Jeśli w grafie prostym

G

=〈

V , E

〉

o co najmniej trzech wierzchołkach dowolne dwa niesąsiednie

wierzchołki v i w spełniają

, to graf

G

jest hamiltonowski.

Twierdzenie Diraca

Graf prosty

G

=〈

V , E

〉

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

1

oraz V

2

tak, by żadne dwa wierzchołki w obrębie tego samego podzbioru V

i

nie były

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.

Sprawdź czy podane grafy mają drogę Eulera, cykl Eulera, drogę Hamiltona, cykl Hamiltona.

2.

a) Przedstaw ogólną ideę algorytmu znajdywania cyklu Eulera.
b) Za pomocą powyższego algorytmu znajdź cykl Eulera dla podanego grafu rozpoczynając od
wierzchołka v=1.

f

4

1

3

5

6

9

2

7

8

d

e

a

c

b

g

e

h

i

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.STOS 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. STOS u;



12. ZA[v]:=ZA[v]\{u}; ZA[u]:=ZA[u]\{v}; {usuń krawędź {u,v} z listy incydencji}
13. v:=u;
14. end;
15 else {jeśli ZA[v]=∅}
16 begin
17.......v



STOS; {zdjęcie wierzchołka v ze STOS}

18 CE v; {włożenie wierzchołka v na szczyt stosu CE}



19. end;
20. end;
21.end;

3.

Narysuj grafy pełne

K

n

dla

n≤6

.

a) Dla jakich n graf

K

n

jest eulerowski?

b) Dla jakich n graf

K

n

jest hamiltonowski?

4.

Symbolem

Q

n

oznaczymy graf zwany kostką n-wymiarową. Jego zbiorem wierzchołków jest zbiór

wszystkich ciągów postaci



a

1,

a

2,

... , a

n



, a

i

∈{

0,1}

. Krawędzie łączą te i tylko te ciagi, które różnią się

dokładnie jednym wyrazem.
a) Ile wierzchołków i krawędzi ma ten graf?
b) Dla jakich n graf

Q

n

jest eulerowski?

c) Dla jakich n graf

Q

n

jest hamiltonowski?

5.

Narysuj grafy będące kołem dla

n≤6.

Które grafy (koła)

W

n

są eulerowskie, które zaś

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) sprawdź 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

1

c

2

, c

4

d

2

c

1

, c

3

, c

5

d

3

c

2

, c

4

d

4

c

4