WĘDRÓWKI PO 

GRAFACH

• Obchody Eulera

• Cykle Hamiltona

 

 

U źródeł teorii grafów

• 1736: Euler odwiedza Królewiec 

(Königsberg, Kaliningrad).

• Rozwiązuje zagadkę 7 mostów.

• Uogólnia problem i też go 

rozwiązuje, otrzymując  1. 
twierdzenie teorii grafów

.

 

 

Mosty Królewieckie

A

B

C

D

A

C

B

D

 

 

Spacery i obchody

• Dla danego 

multigrafu

 G, ciąg    

W=v_0e_0v_1e_1...v_{k-1}e_{k-1}v_k  nazywamy

 

spacerem

, gdy e_i=v_iv_{i+1} jest krawędzią w 

G  dla każdego i<k. 

• W (Na ?) spacerze wierzchołki i krawędzie mogą 

się powtarzać

.

• Spacer jest 

zamknięty

, gdy  v_0=v_k.   

• Zamknięty spacer zawierający każdą krawędź 

dokładnie raz (dokładniej: tyle razy, ile wynosi jej 

krotność)  nazywamy 

obchodem Eulera

, a 

spójny

 

multigraf, dla którego istnieje obchód Eulera – 

grafem Eulera.            

 

 

Ilustracja

a

b

c

d

e

f

a-b-c-f-b-a-e -- spacer

a-b-c-b-f-a – spacer zamknięty

a

b

c

d

a-b-d-c-b-c-a – 
obchód Eulera

 

 

Tw. Eulera

Tw (Euler, 1736)

. Spójny graf G jest grafem Eulera 

wgdy wszystkie stopnie wierzchołków są 
parzyste.

Dowód

 :  oczywiste

   

Rozważmy najdłuższy spacer W w G 

zawierający każdą krawędź nie więcej niż raz.

  W musi być zamknięty 

(dlaczego?).

  

Jeśli W nie jest obchodem Eulera, to istnieje 

krawędź e poza W, ale incydentna z W.

  

Wtedy jednak W można wydłużyć – sprzeczność

. 

 

 

Wniosek

Lemat

.

 Jeśli wszystkie stopnie wierzchołków w G 

są parzyste, to krawędzie w G można 
zorientować (skierować, ,,ostrzałkować”) tak, 
by do każdego wierzchołka wchodziło tyle samo 
strzałek co wychodziło.

Dowód: 

W każdej składowej znajdźmy obchód 

Eulera i zorientujmy krawędzie wzdłuż niego. 

Uwaga:

 Adaptacja pierwotnego dowodu tego 

lematu pozwala na indukcyjny dowód Tw. 
Eulera.

 

 

Zwiedzamy muzeum

• Zwiedzamy muzeum będące 

labiryntem korytarzy, w którym 
obrazy wiszą po obu stronach.

• Cel: przejść każdy korytarz 2 razy 

i wrócić do wyjścia.

 

 

PLAN MUZEUM

a

b

c

d

e

a

b

c

d

e

Konkluzja:

 

KAŻDE

 muzeum da się tak przejść!

 

 

Rysowanie bez odrywania

Czy dany rysunek można narysować 

bez odrywania ołówka od papieru i 

bez powtarzania linii?

 

 

Trasa Eulera

• Spacer zawierający każdą krawędź 

dokładnie raz nazywamy 

trasą Eulera.

Wniosek.

 Spójny graf G ma trasę Eulera 

wgdy wszystkie stopnie wierzchołków 

są parzyste, oprócz co najwyżej dwóch.

Dowód:  

Jeśli trzeba, dodajmy krawędź, 

by powstał graf Eulera. Z obchodu 

Eulera usuńmy dodaną krawędź. 

 

 

Więcej nieparzystych

Wniosek.

 Jeśli multigraf G ma 2k nieparzystych 

stopni wierzchołków, to E(G) można pokryć przy 
pomocy k (krawędziowo rozłącznych) spacerów, 
w których żadna krawędź się nie powtarza.

Dowód:  

Dodajmy do G k krawędzi łączących 

parami wierzchołki nieparzyste. Nowy multigraf 
jest grafem Eulera i ma obchód Eulera W.

   Usuwając z W dodane krawędzie, dzielimy go na 

k spacerów o żądanej własności.  

 

 

Problem Chińskiego 

Listonosza

• Obchodem listonosza

 nazywamy 

zamknięty spacer przechodzący 
przez każdą krawędź 

co najmniej

 

raz.

• Problem (Guan 1960, Edmonds 

1965):

 Znaleźć najkrótszy obchód 

listonosza w spójnym multigrafie.

 

 

Rozwiązanie

• Niech G ma 2k nieparzystych 

stopni.

• Niech H będzie najmniejszym (co 

do liczby krawędzi) podgrafem 
rozpiętym w G, który ma te same 
nieparzyste wierzchołki co G.

 

Problem 1: 

Jak efektywnie wyznaczyć 

H

 

?    

(ćwiczenia)

  

 

 

Rozwiązanie – c.d.

• Dublując krawędzie  H w G 

otrzymamy graf Eulera G+H.

• Obchód Eulera W w G+H 

wyznacza obchód listonosza w G.

Problem 2: 

Wykazać, że

 

W jest 

najkrótszym obchodem listonosza 
w G? 

(ćwiczenia)

 

 

A

B

C

D

E

F

G

H

I

J

 

 

A

B

C

D

E

F

G

H

I

J

 

 

Ilustracja

 

 

Zabawka Hamiltona

• Sir William Hamilton (1859):

• Przejść 

bez powtórzeń

 wszystkie 

wierzchołki dwunastościanu i wrócić do 
punktu wyjścia, poruszając się wzdłuż 
krawędzi.

 

 

Cykl Hamiltona

• Cyklem Hamiltona

 w grafie G 

nazywamy rozpięty podgraf grafu G, 
który jest cyklem.

• Graf posiadający cykl Hamiltona 

nazywamy 

hamiltonowskim 

lub

 

Hamiltona.

• Ścieżką Hamiltona 

w grafie G 

nazywamy rozpięty podgraf grafu G, 
który jest ścieżką.

 

 

Euler vs. Hamilton

• Obchód (trasa) Eulera w grafie G 

jest cyklem (ścieżką) Hamiltona w 

grafie krawędziowym L(G).

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

 

 

Ale...

• Nie każdy graf jest grafem 

krawędziowym, np. K_{1,3}.

• Problem rozstrzygnięcia czy graf jest 

hamiltonowski jest 

NP-zupełny

.

• Problemy rozstrzygnięcia czy graf 

jest eulerowski oraz czy graf jest 
grafem krawędziowym są w 

klasie P

.

 

 

Warunek konieczny

Fakt 1.

 Jeśli istnieje w G zbiór 

wierzchołków S taki, że G-S ma 
więcej niż |S| składowych spójności, 
to G 

nie

 jest hamiltonowski.

Dowód: 

Jeśli usunąć z cyklu k 

wierzchołków, to rozpadnie się on 
na co najwyżej k składowych, więc 
to samo jest prawdą dla grafu 
hamiltonowskiego

. 

 

 

Wnioski

1. 

Graf Hamiltona musi być 2-spójny.

 

2. 

Dwudzielny graf Hamiltona musi 

mieć równy dwupodział, a więc musi 
mieć parzysta liczbę wierzchołków.

NIE!!!

 

 

Inny warunek konieczny

Fakt 2.

 Jeśli G  jest hamiltonowski, to 

podgraf złożony z krawędzi incydentnych 
z wierzchołkami 

stopnia dwa

 w G musi 

być sumą ścieżek lub cyklem Hamiltona. 

NIE!!!

 

 

Tw. Diraca 

• Jak duże δ(G) gwarantuje cykl Hamiltona?

Tw.(Dirac 1952).

 Jeśli |V(G)|=n>2 i δ(G) ≥ 

n/2, to G jest hamiltonowski.

Dowód: 

• Przy powyższych założeniach G jest spójny.

• Rozważmy najdłuższą ścieżkę P w G.

• Jej końce, u i v, mają wszystkich sąsiadów 

w zbiorze V(P).

 

 

Dowód Tw. Diraca – c.d.

• Niech R będzie zbiorem wierzchołków 

położonych na P bezpośrednio ,,na 
prawo” od sąsiadów v. Precyzyjniej

:

}

1

)

,'

(

)

,

(

),

(

'

,'

:

)

(

{













u

w

d

u

w

d

G

E

v

w

w

P

V

w

R

P

P

u

v

w’

w













)

(

2

/

|

)

(

|

,

2

/

|

|

u

N

R

n

u

N

n

R

 

 

Dowód Tw. Diraca – 

dokończenie

• Zatem w G istnieje cykl C taki, że 

V(C)=V(P).

• Jeśli C nie jest cyklem Hamiltona, to na 

podstawie spójności grafu G, musi istnieć 
krawędź o dokładnie jednym końcu w V(C). 

• To jednak oznacza, że w G jest ścieżka 

dłuższa niż P – sprzeczność.



C

 

 

Tw. Ore

Tw.(Ore 1960).

 Jeśli |V(G)|=n>2 i 

dla każdej pary 

nie

sąsiednich 

wierzchołków u i v, 

to G jest hamiltonowski.

,

)

(

)

(

n

v

d

u

d

G

G





Dowód: 

Taki sam jak dowód Tw. Diraca.

 

 

Tw. Chvátala-Erdősa

• Jeśli κ(G)>k i |V(G)|>2k, to G ma cykl 

długości większej niż 2k 

(ćw.)

• Jeśli α(G)<k i |V(G)|>3k, to G ma cykl 

długości większej niż n/k  

(ćw.)

Tw. (Chvátal, Erdős, 1972) 

Jeśli |V(G)|>2 i

),

(

)

(

G

G







to G jest hamiltonowski.

 

 

Dowód

• Niech κ(G)=k.

 

• Niech C będzie najdłuższym cyklem.

• Przypuśćmy, że istnieje wierzchołek v poza C.

• Z Tw. Mengera, istnieje co najmniej min{k,|

V(C)|} rozłącznych (z wyjątkiem v) V(C)-{v} 

ścieżek. 

(

ćw.)

• Ich końce w V(C) nie mogą być sąsiednie na C.

 

• Zatem tych ścieżek jest co najmniej k ≤ |V(C)|/2. 

• Następcy ich końców na cyklu (zgodnie z 

ruchem wskazówek zegara) tworzą wraz z v 

zbiór niezależny mocy co najmniej k+1 – 

sprzeczność

.

 

 

Ilustracja

C

v

P_1

P_2

u_1

u_2

w_2

w_1

Cykl w_1-w_2-...-u_1-P_1-v-P_2-u_2-...-w_1 jest dłuższy niż C.