WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT 

GRAFY i SIECI (4) 

J.Sikorski 

Strona 1 / 13 

DROGI i CYKLE HAMILTONA w grafach skierowanych 

Dla grafu skierowanego 

 

D = ( V, A ) 

rozważmy zagadnienie istnienia cyklu elementarnego, który zawiera 

wszystkie wierzchołki grafu, czyli cyklu Hamiltona, 

Graf skierowany pełny bez pętli  D

n

  jest hamiltonowski 

dla każdego n 

≥

 2  i zawiera  (n

−−−−

1)!  cykli Hamiltona. 

Przykład cykli Hamiltona w grafie D

3

 i D

4

 

D

3

:  (3

−

1)! = 2 

D

4

:  (4

−

1)! = 6 

1

2

3

1

2

3

 

1

2

3

4

1

2

3

4

1

2

3

4

1

2

3

4

1

2

3

4

1

2

3

4

 

Twierdzenie  (Meyniel, 1973) 

Jeśli D jest silnie spójnym grafem skierowanym bez pętli o  n 

≥

 2 

wierzchołkach i dla dowolnej pary wierzchołków niezależnych 

zachodzi warunek  

1

2

)

(

)

(

−

≥

+

n

w

d

v

d

, to graf 

D ma cykl Hamiltona. 

(odpowiednik tw. Ore) 

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT 

GRAFY i SIECI (4) 

J.Sikorski 

Strona 2 / 13 

Wniosek

  (twierdzenie Nash-Williams, 1969) 

Je

ś

li D jest grafem skierowanym bez p

ę

tli, w którym  

2

)

(

n

v

d

≥

+

  i  

2

)

(

n

v

d

≥

−

  dla każdego wierzchołka v, to graf D ma cykl Hamiltona. 

(odpowiednik tw. Diraca) 

TURNIEJE 

Graf skierowany bez pętli nazywamy 

turniejem, jeśli dla każdej pary 

wierzchołków  u  i  v  zawiera on dokładnie jeden łuk:   

albo  (u, v), albo (v, u). 

•

 

turniej może reprezentować wyniki spotkań par uczestniczących w 

rozgrywkach sportowych typu „każdy z każdym” (bez remisów) 

Przykład turnieju 

c

a

b

d

 

Twierdzenie (Rédei, 1934) 

Każdy turniej zawiera drogę Hamiltona. 

Przykład dróg Hamiltona w turnieju: 

(d, a, b, c),  (d, b, c, a)  i  (d, c, a, b) 

c

a

b

d

 

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT 

GRAFY i SIECI (4) 

J.Sikorski 

Strona 3 / 13 

Twierdzenie (Thomassen, 1982) 

Każdy turniej zawiera drogę Hamiltona, która zaczyna się 

w wierzchołku o najwyższym stopniu wyjściowym i kończy 

w wierzchołku o najwyższym stopniu wejściowym. 

Przykład turnieju bez cyklu Hamiltona 

c

a

b

d

 

Ten turniej nie jest silnie spójny. 

Twierdzenie (Camion, 1959) 

Każdy silnie spójny turniej zawiera cykl Hamiltona. 

Przykład cyklu Hamiltona w silnie spójnym turnieju 

c

a

b

d

 

cykl Hamiltona:  (a, b, d, c, a) 

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT 

GRAFY i SIECI (4) 

J.Sikorski 

Strona 4 / 13 

DRZEWA i LASY 

Lasem nazywamy graf nieskierowany, który nie zawiera cykli 

elementarnych. 

Drzewem nazywamy graf spójny, który nie zawiera cykli elementarnych. 

Przykłady drzewa i lasu 

takie krawędzie
są wykluczone

drzewo

las

 

 

Twierdzenie 

Niech G będzie grafem nieskierowanym o  n  wierzchołkach. 

Wówczas następujące stwierdzenia są równoważne: 

1.

 

Graf G jest drzewem. 

2.

 

Graf G nie zawiera cykli elementarnych i ma  n

−

1  krawędzi. 

3.

 

Graf G jest spójny i ma  n

−

1  krawędzi. 

4.

 

Graf G jest spójny i każda krawędź jest mostem. 

5.

 

Dowolne dwa wierzchołki grafu G są połączone dokładnie jedną 

drogą. 

6.

 

Graf G nie zawiera cykli elementarnych, ale dołączenie dowolnej 

nowej krawędzi do G tworzy dokładnie jeden taki cykl. 

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT 

GRAFY i SIECI (4) 

J.Sikorski 

Strona 5 / 13 

Dowód 

Dla  n = 1 równoważność stwierdzeń jest oczywista. 

Załóżmy zatem, że  n 

≥

 2. 

(1. ⇒ 2.) Indukcja względem liczby wierzchołków; załóżmy, że implikacja 

zachodzi dla dowolnego drzewa o liczbie wierzchołków nie większej od  n 

−

1.  

Pokażemy, że zachodzi dla n. Usuńmy z G jedną krawędź. Ponieważ G nie 

zawiera cykli elementarnych, to usunięcie krawędzi prowadzi do rozpadu G na 

dwa drzewa, które na mocy założenia indukcyjnego mają razem (n 

−

2) 

krawędzi. Zatem G musi mieć (n 

−

1) krawędzi. 

(2. ⇒ 3.) Gdyby G nie był spójny, to łączna liczba krawędzi w jego składowych, 

będących drzewami, byłaby co najmniej o 2 mniejsza od liczby wierzchołków. 

Przeczy to założeniu, że G ma  n

−

1  krawędzi. 

(3. ⇒ 4.) Usunięcie dowolnej krawędzi daje graf o  n  wierzchołkach i  n 

−

2  

krawędziach, który nie jest spójny. 

(4. ⇒ 5.) Ponieważ G jest spójny, to każda para wierzchołków jest połączona co 

najmniej jedną drogą. Gdyby dla pewnej pary wierzchołków były dwie takie 

drogi, to powstałby cykl. Przeczy to założeniu, że każda krawędź jest mostem. 

(5. ⇒ 6.) Graf G nie może zawierać cyklu elementarnego, bo oznaczałoby to,  

ż

e istnieje para wierzchołków połączona dwiema drogami wierzchołkowo 

rozłącznymi. Dołączenie nowej krawędzi utworzy cykl elementarny. Może być 

tylko jeden taki cykl, bowiem istnienie dwóch takich cykli oznaczałoby, że w G 

istnieje cykl elementarny nie zawierający dołączanej krawędzi. 

(6. ⇒ 1.) Graf G musi być spójny. Gdyby tak nie było, to dodanie krawędzi 

łączącej składowe grafu nie powodowałoby powstania cyklu elementarnego.  

 

 

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT 

GRAFY i SIECI (4) 

J.Sikorski 

Strona 6 / 13 

Wniosek 

W drzewie o  n 

≥

 2  wierzchołkach co najmniej dwa z nich 

są stopnia 1 (są liśćmi). 

Dowód 

2

2

)

1

(

2

2

)

(

−

=

−

=

=

∑

∈

n

n

E

i

d

V

i

.  

 

Wniosek

 

Je

ś

li graf G o n wierzchołkach jest lasem zło

ż

onym z k drzew, to 

liczba jego kraw

ę

dzi  m = n – k. 

Dla grafu spójnego  G = (V, E)  ka

ż

de drzewo  G

T

 = (V, T)  takie, 

ż

e 

T 

⊆

 E  nazywamy 

drzewem rozpinającym

 (dendrytem) grafu G. 

Przykład drzewa rozpinaj

ą

cego 

5

4

3

1

2

 

Twierdzenie

  (Cayley, 1889)

 

Graf  pełny K

n

  (dla n 

≥

 2)  ma  n

 n

−

2   

ró

ż

nych drzew rozpinaj

ą

cych. 

Przykład liczby drzew rozpinaj

ą

cych w grafie pełnym 

K

4

 : 

4

3

1

2

,  

n

 n

−

2

 = 4

2

 = 16 

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT 

GRAFY i SIECI (4) 

J.Sikorski 

Strona 7 / 13 

Dowód

 (zarys dowodu – konstrukcja kodu Prüfera dla drzewa) 

Załó

ż

my, 

ż

e wierzchołki grafu s

ą

 ponumerowane liczbami 

naturalnymi  1, ..., n. Łatwo sprawdzi

ć

, 

ż

e dla  n = 2  tw. zachodzi. 

Poka

ż

emy, 

ż

e dla  n 

≥

 3  istnieje wzajemnie jednoznaczna 

odpowiednio

ść

 pomi

ę

dzy drzewami rozpinaj

ą

cymi graf pełny K

n

   

a  n

 n

−

2  

ci

ą

gami (a

1

, a

2

, ..., a

n

−

2

), gdzie  a

i

  jest liczb

ą

 naturaln

ą

 

spełniaj

ą

c

ą

 nierówno

ść

  1 

≤

 a

i

 

≤

 n. 

Załó

ż

my, 

ż

e T jest drzewem rozpinaj

ą

cym  K

n

 . Wybieramy 

wierzchołek  v  stopnia 1 o najmniejszym numerze i przyjmujemy 

jako a

1

 numer wierzchołka s

ą

siedniego z v w drzewie T. Usuwamy z 

T wierzchołek v wraz z incydentn

ą

 z nim kraw

ę

dzi

ą

. Powtarzamy 

powy

ż

sze post

ę

powanie kolejno dla  a

2

, a

3

, ..., a

n

−

2

 . 

Aby ustali

ć

 odwrotn

ą

  odpowiednio

ść

 pomi

ę

dzy ci

ą

giem (a

1

, a

2

, ..., 

a

n

−

2

)  a drzewem rozpinaj

ą

cym, we

ź

my dowolny ci

ą

g (a

1

, a

2

, ..., a

n

−

2

), 

którego ka

ż

dy wyraz spełnia warunek 1 

≤

 a

i

 

≤

 n, i zbudujmy 

odpowiadaj

ą

ce mu drzewo T. Niech v b

ę

dzie najmniejsz

ą

 liczb

ą

 ze 

zbioru  N = {1, 2, ..., n}, która nie wyst

ę

puje w ci

ą

gu (a

1

, a

2

, ..., a

n

−

2

). 

Dodajemy do T kraw

ę

d

ź

 {a

1

, v}. Usuwamy a

1

 z ci

ą

gu i podstawiamy 

N 

←

 N \ {v}. Powtarzamy to post

ę

powanie kolejno dla  a

2

, a

3

, ..., a

n

−

2

. 

Na ko

ń

cu ł

ą

czymy kraw

ę

dzi

ą

 ostatnie dwa wierzchołki, które 

pozostały w N.  

 

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT 

GRAFY i SIECI (4) 

J.Sikorski 

Strona 8 / 13 

Przykład kodowania drzew rozpinaj

ą

cych w grafie pełnym 

K

4

 : 

n

 n

−

2

 = 4

2

 = 16 

4

3

1

2

(1, 1)

(1, 2)

(1, 3)

(1, 4)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 1)

(3, 2)

(3, 3)

(3, 4)

(4, 1)

(4, 2)

(4, 3)

(4, 4)

4

3

1

2

4

3

1

2

4

3

1

2

4

3

1

2

4

3

1

2

4

3

1

2

4

3

1

2

4

3

1

2

4

3

1

2

4

3

1

2

4

3

1

2

4

3

1

2

4

3

1

2

4

3

1

2

4

3

1

2

 

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT 

GRAFY i SIECI (4) 

J.Sikorski 

Strona 9 / 13 

Przykład u

ż

ycia kodu Prüfera 

kodowanie:

    

5

4

3

1

2

1

2

3

4

(1, 1, 4)

 

odkodowanie:

    

(3, 1, 5)

5

4

3

1

2

1

2

3

4

 

Drzewo przeglądu grafu w głąb 

Po zako

ń

czeniu przeszukiwania grafu G = (V, E) metod

ą

 w gł

ą

b 

uzyskujemy ci

ą

g jego ponumerowanych wierzchołków: (

1

i

v

, ..., 

n

i

v

). 

Wyznaczamy zbiór kraw

ę

dzi 

T

, który tworzy drzewo rozpinaj

ą

ce 

G

: 

 

1.

 

rozpocznij od  

T

 = 

∅

, 

2.

 

dla ka

ż

dego  

j 

= 

n

, 

n 

−

1, ..., 2  wykonaj co nast

ę

puje: 

2.1.

 

wybierz z ci

ą

gu  (

1

i

v , ..., 

n

i

v )  wierzchołek 

v

, który jest 

s

ą

siedni z wierzchołkiem 

j

i

v

 i ma najwi

ę

kszy indeks 

spo

ś

ród wierzchołków poprzedzaj

ą

cych w ci

ą

gu 

j

i

v

, 

2.2.

 

doł

ą

cz do zbioru  

T

  kraw

ę

d

ź

  {

j

i

v

, 

v

}. 

 

WY

Ż

SZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZ

Ą

DZANIA 

WIT

 

GRAFY i SIECI (4) 

J.Sikorski 

Strona 10 / 13 

Przykład drzewa przeglądu grafu w głąb  

Ci

ą

g wyznaczony metod

ą

 przeszukania w gł

ą

b: (5, 6, 3, 2, 7, 1, 10, 4, 9, 8) 

7

1

5

4

6

2

3

8

9

10

 

Zbiór kraw

ę

dzi drzewa rozpinaj

ą

cego: 

{{8, 9}, {9, 10}, {4, 10}, {10, 1}, {1, 7}, {7, 2}, {2, 3}, {3, 6}, {6, 5}} 

Drzewo przeglądu grafu wszerz 

Po zako

ń

czeniu przeszukiwania grafu 

G

 = (

V

, 

E

) metod

ą

 wszerz 

uzyskujemy ci

ą

g jego ponumerowanych wierzchołków: (

1

i

v

, ..., 

n

i

v

). 

Wyznaczamy zbiór kraw

ę

dzi 

T

, który tworzy drzewo rozpinaj

ą

ce 

G

: 

 

1.

 

rozpocznij od  

T

 = 

∅

, 

2.

 

dla ka

ż

dego  

j 

= 

n

, 

n 

−

1, ..., 2  wykonaj co nast

ę

puje: 

2.1.

 

wybierz z ci

ą

gu  (

1

i

v

, ..., 

n

i

v

)  wierzchołek 

v

, który jest 

s

ą

siedni z wierzchołkiem 

j

i

v

 i ma najmniejszy indeks 

spo

ś

ród wierzchołków ci

ą

gu, 

2.2.

 

doł

ą

cz do zbioru  

T

  kraw

ę

d

ź

  {

j

i

v

, 

v

}. 

 

WY

Ż

SZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZ

Ą

DZANIA 

WIT

 

GRAFY i SIECI (4) 

J.Sikorski 

Strona 11 / 13 

Przykład drzewa przeglądu grafu wszerz  

Ci

ą

g wyznaczony metod

ą

 przeszukania wszerz: (5, 6, 8, 3, 7, 9, 10, 2, 4, 1) 

7

1

5

4

6

2

3

8

9

10

 

Zbiór kraw

ę

dzi drzewa rozpinaj

ą

cego: 

{{1, 7}, {4, 3}, {2, 8}, {10, 6}, {9, 6}, {7, 6}, {3, 6}, {8, 5}, {6, 5}} 

Terminologia dla drzew rozpinających: 

Dla  

G

T

 = (

V

, 

T

) , które jest drzewem rozpinaj

ą

cym grafu  

G

 = (

V

, 

E

): 

gałęziami

 (drzewa) nazywamy elementy zbioru  

T

 , 

cięciwami

 (grafu) nazywamy elementy zbioru  

E

 \ 

T

 . 

Je

ś

li  

e

  jest ci

ę

ciw

ą

, to graf  (

V

, 

T

∪

{

e

}) zawiera dokładnie jeden cykl 

C

e

. 

Zbiór  

Ω

 = { 

C

e

 : 

e

 

∈

 

E

 \ 

T

 }  nazywamy 

zbiorem cykli fundamentalnych

 

grafu 

G

  (wzgl

ę

dem drzewa rozpinaj

ą

cego 

G

T

) 

WY

Ż

SZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZ

Ą

DZANIA 

WIT

 

GRAFY i SIECI (4) 

J.Sikorski 

Strona 12 / 13 

Przykład gałęzi, cięciw i cykli fundamentalnych 

 

C

{2, 3}

C

{2, 4}

C

{4, 5}

5

4

3

1

2

3

1

2

4

3

1

2

5

4

3

 

T

 = {{1, 2}, {1, 3}, {3, 4}, {3, 5}},   

E

 \ 

T

  = {{2, 3}, {2, 4}, {4, 5}} 

Ω

 = { 

C

{2, 3}

,  

C

{2, 4}

,   

C

{4, 5}

} 

Twierdzenie 

Niech 

G

 = (

V

, 

E

)  b

ę

dzie grafem spójnym a  

G

T

 = (

V

, 

T

)  jego 

dowolnym drzewem rozpinaj

ą

cym. Je

ż

eli ka

ż

dy cykl b

ę

dziemy 

traktowali jak zbiór kraw

ę

dzi, to ka

ż

dy cykl prosty 

C

 w grafie 

G

 

mo

ż

na jednoznacznie przedstawi

ć

 jako ró

ż

nic

ę

 symetryczn

ą

 cykli 

fundamentalnych: 

 

C

 = 

1

e

C

⊗

 

2

e

C

⊗

 ... 

⊗

 

k

e

C

, 

gdzie  

{

}

k

e

e ...,

,

1

 = C \ T  jest zbiorem cięciw względem drzewa G

T

 . 

WY

Ż

SZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZ

Ą

DZANIA 

WIT

 

GRAFY i SIECI (4) 

J.Sikorski 

Strona 13 / 13 

Przykład przedstawiania cyklu prostego jako różnicy symetrycznej 

C

{2, 3}

C

{2, 4}

C

{4, 5}

5

4

3

1

2

3

1

2

4

3

1

2

5

4

3

5

4

3

1

2

C

 

T = 

{

{1, 2}, {1, 3}, {3, 4}, {3, 5}

}

,   C \ T  = 

{

{2, 3}, {2, 4}, {4, 5}

}

 

 zbiór cykli fundamentalnych  

{

C

{2, 3}

, C

{2, 4}

, C

{4, 5}

}

 

C

{2, 3}

C

{2, 4}

C

{4, 5}

3

1

2

4

3

1

2

⊗

4

3

2

=

{{2, 3}, {3, 4}, {2, 4}}

4

3

2

5

4

3

⊗

=

5

4

3

2

C

{{2, 3}, {3, 4}, {2, 4}}

 

C = 

{

{2, 3}, {3, 5}, {4, 5}, {2, 4}

}

 

=

 (

C

{2, 3}

 

⊗

 C

{2, 4}

)

 

⊗

 C

{4, 5}