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}