Grafy Eulera  

(przechodzenie przez krawędzie)

Grafem Eulera nazywamy graf składający się z drogi Eulera. 

Drogą  Eulera  nazywamy  drogę  zamknięta  przechodzącą  dokładnie 
jeden raz przez każdą krawędź z grafu G.

Graf  jest  grafem  Eulera  wtedy  i  tylko  wtedy  gdy    wszystkie 
wierzchołki  G  są stopnia parzystego

.

A

D

C

B

Graf  spójny  mający  dokładnie  dwa  wierzchołki  stopnia   
nieparzystego, ma drogę Eulera

.

1

10. Elementy teorii grafów (Algorytmy na grafach)

Drzewa rozpinające. Grafy Eulera i Hamiltona. Grafy AND/OR. Wykorzystanie w
 algorytmach wyznaczania  sieci instalacji elektrycznej, najkrótszych połączeń, 
planowaniu działań (np. montażu). 

Obwód Hamiltona    

(przechodzenie przez wierzchołki)

Obwodem Hamiltona w grafie spójnym jest droga zamknięta. Która 

przechodzi przez każdy wierzchołek grafu G dokładnie jeden raz.

Obwód  Hamiltona  w  grafie  o    n  wierzchołkach  składa  się  z    n   
krawędzi.

Problem komiwojażera. 

Całkowita  liczba  różnych  obwodów  Hamiltona  w  grafie  pełnym 
o  
 n  wierzchołkach: (n-1)/2!
 

2

Problem kolorowania

Shell

       Esso

Gulf

       BP

Shell

   lub

Gulf

Graf jest k - kolorowalny jeżeli każdemu wierzchołkowi można przypisać 

jeden z k kolorów, w taki sposób że żadne dwa wierzchołki sąsiednie nie 

mają tego samego koloru.

3

Graf rozmieszczenia stacji benzynowych

Problem wyznaczania najkrótszej trasy: znaleźć taka ścieżkę, prowadzącą 
od węzła  i  do węzła  j, by suma wartości przebywanych połączeń była jak 
najmniejsza. Wyznacz najkrótsza ścieżkę łączącą węzły  A  i  J.

PRZESZUKIWANIE GRAFÓW (metoda podziału i ograniczeń)

4

A

B

G

C

D

I

J

F

E

12

15

8

11

6

5

5

7

5

3

12

10

7

9

6

4

9

10

11

12

12

13

10

12

8

10

8

6

8

5

4

6

4

10

12

10

8

D(12)

C(10)

B(15)

I(25) F(24)

F(20) E(19)

B(16)

C(20) E(22)

G(26)

A(0)

D(12)

C(10)

B(15)

I(25) F(24)

F(20) E(19)

B(16)

C(20) E(22)

G(26)

A(0)

D(12)

C(10)

B(15)

I(25) F(24)

F(20) E(19)

B(16)

C(20) E(22)

G(26)

F(25)

G(24)

B(24)

H(23)

A(0)

D(12)

C(10)

B(15)

I(25) F(24)

F(20) E(19)

B(16)

C(20) E(22)

G(26)

F(25)

G(24)

B(24)

H(23)

A(0)

Drzew kolejnych etapów przeszukiwania

5

D(12)

C(10)

I(25)

F(20)

E(19)

G(24)

H(23)

A(0)

D(12)

C(10)

I(25)

F(20)

E(19)

G(24)

H(23)

A(0)

E(24)

H(25)

I(26)

D(30)

D(12)

C(10)

I(25)

F(20)

E(19)

G(24)

H(23)

A(0)

E(24)

H(25)

I(26)

D(30)

J(36)

J(31)

I(27)

F(31)

B(32)

D(12)

C(10)

I(25)

E(19)

G(24)

H(23)

A(0)

J(35)

H(28)

F(33)

J(36)

J(31)

I(27)

F(31)

B(32)

Drzewa kolejnych etapów przeszukiwania

Korzystając z przedstawionej wyżej metody wyznacz:

Długość  najkrótszej  drogi  łączącej  dwa  wierzchołki  w  danym  grafie 

skierowanym? 

Jeśli  graf  skierowany  ma  wagi,  to  jaka  jest  waga  minimalna  lub 

maksymalna takiej drogi?

 3                                                  7                        9

         v

1

                                  

    2                                   5                                    4

    9

                                                                 1                                  8

        

v

3

                 4                   v

5

             v

7

6

ALGORYTMY NA GRAFACH

Algorytm Fleury’go 

(wyznaczanie drogi Eulera)

Niech ES – ciąg krawędzi drogi lub cyklu Eulera,  VS – ciąg wierzchołków 

tej drogi lub cyklu. Niech V(G) – zbiór wierzchołków, a E(G) – zbiór 

krawędzi grafu G

1. Wybierz dowolny wierzchołek  v  nieparzystego stopnia, jeśli taki 

istnieje. W przeciwnym przypadku wybierz dowolny wierzchołek v. Niech 

 VS = v  i  niech  ES = .

2. Jeśli z wierzchołka  v  nie wychodzi już żadna krawędź, zatrzymaj się.

3.  Jeśli pozostała dokładnie jedna krawędź wychodząca z wierzchołka  v  , 

powiedzmy krawędź  e  z wierzchołka  v  do  w, to usuń  e  z E(G) oraz  

v  z  V(G)  i przejdź do kroku 5.

4. Jeśli została więcej niż jedna krawędź wychodząca z wierzchołka  v  , 

wybierz krawędź, powiedzmy  e  z  v  do  w , po usunięciu której graf 

pozostanie spójny, następnie usuń  e  z  E(G).

5. Dołącz  w  na końcu ciągu  VS, dołącz  e  na końcu ciągu  ES, zastąp  v  

wierzchołkiem  w  i przejdź do kroku 2.

7

Algorytm Fleury’go 

(wyznaczanie drogi Eulera)

8

Algorytm Kruskala  

(minimalne drzewo spinające)

Dane: skończony graf spójny  G  z  wagami, którego krawędzie są 

 uporządkowane według 

wzrastających wag.

Wyniki: zbiór  E  krawędzi minimalnego drzewa spinającego grafu 

 G

Niech E:= .

Dla j = 1 do |E(G)| 

Jeśli graf  E  {e

j

}  jest acykliczny, to dołącz e

j

 do E.

Przykład

2

5

3  
    
 

3

5

5

5

3

4

1

5

2

e

8

e

9

e

7

e

8

e

4

e

5

e

6

e

2

e

1                        

             

e

10

e

3

e

11

9

Wagi krawędzi W(e

i

) mają tworzyć ciąg niemalejący, tzn. W(e

i

) < 

W(e

j

)  dla  i < j , zatem:

e

1

2

5

3  
    
 

3

5

5

5

3

4

1

5

2

e

8

e

9

e

7

e

8

e

4

e

5

e

6

e

2

e

1                        

             

e

10

e

3

e

11

e

1  

 e

2

  e

3   

e

4

  e

5  

 e

6

  e

7  

e

8

  e

9 

 e

10

 e

11

1     2   2   3   3    4   5   5   5   5    5 

e

7

e

3

e

5

e

6

e

2

10

Algorytm  Prima  

(minimalne drzewo spinające)

Dane: skończony graf spójny  G  z  wagami (z krawędziami wypisanymi w 
dowolnym porządku) 

Wyniki: zbiór  E  krawędzi minimalnego drzewa spinającego grafu  G

Niech  E:= .

Wybierz   w  ze zbioru  V(G)  i niech  V := {w}

Dopóki  V  V(G), wykonuj wybierz w zbiorze  E(G)  krawędź  (u,v)  o 

najmniejszej możliwej wadze, taką że  u  V  i   v  V(G) \ V  dołącz krawędź  

(u,v)  do zbioru E i wierzchołek  v  do zbioru  V.

          2                                                                  

  b  

                 
                       
                         

 
    3                   1

           d                  e

       

          

1              

 

c

2

1

4

5

4

3

a

Algorytmy Prima i Kruskala są algorytmami zachłannymi, tzn. 
algorytmami wybierającymi zawsze najmniejszą krawędź, która 
należy dodać lub największą krawędź, którą należy odrzucić.

Przykład

11

12

ZADANIA

1. Czy jest możliwe, aby owad poruszający się wzdłuż krawędzi sześcianu przeszedł 
każdą krawędź dokładnie raz? Odpowiedź uzasadnij.

2. Zastosuj algorytm Fleury’ego aby otrzymać drogę Eulera w poniższym grafie

4. Wyznacz w podanym grafie cykl Eulera i cykl Hamiltona

3. Dla poniższego grafu wyznacz 

5. Czy w grafie Hamiltona istnieje obwód Eulera?

13

180

240

320

270

200

280

330

240

350

220

280

90

120

300

6. Zastosuj algorytm Prima, aby znaleźć minimalne drzewo rozpinające w    
poniższym grafie.

7. Danych jest n kul, z których każda waży 10 g., za wyjątkiem jednej, która 
waży 9 g. lub 11 g. Za pomocą k ważeń (na wadze szalkowej) należy 
rozstrzygnąć, która kula ma inną masę oraz czy jest ona lżejsza czy cięższa 
od pozostałych. Wyznacz, jaką maksymalną wartość może przyjmować n przy 
zadanym k jako funkcję f(k). Przedstaw algorytm ważenia dla dowolnego k i n 
= f(k).

8. Rozwiąż zadanie 7) dla k = 3. Tzn. wyznacz maksymalną liczbę kul, dla 
których w 3 ważeniach zawsze można rozstrzygnąć, która z kul jest inna oraz 
czy jest cięższa czy lżejsza od pozostałych.

9. Rozwiąż zadanie 7) przy założeniu, że nie trzeba odpowiedzieć czy 
wyjątkowa kula jest cięższa czy lżejsza, a jedynie odpowiedzieć, która z kul 
jest inna.

Rozwiąż zadanie 7)przy założeniu, że wiadomo, że wyjątkowa kula jest 
cięższa.