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