Matematyka dyskretna 2002 09 Grafy nieskierowane

Matematyka Dyskretna
Andrzej Szepietowski
25 czerwca 2002 roku
Rozdział 1
Grafy (nieskierowane)

Definicja 1.1 Graf (nieskierowany) jest to para składajaca sie ze skoń-
� �

czonego zbioru wierzchołków oraz ze zbioru kraw� , gdzie kraw� to pary
edzi edzie
wierzchołków.

O kraw� mówimy, że łaczy wierzchołki i , a o wierzchołkach i ,
edzi �

że sa końcami kraw� . Stopień wierzchołka , oznaczany przez , jest to liczba
� edzi
kraw� wychodzacych z .
edzi �
Graf czesto przedstawiamy na rysunku jako zbiór punktów (lub kółek) połaczonych
� �
odcinkami (lub łukami).
Rysunek 1.1: Przykład grafu

Przykład 1.2 Rysunek 1.1 przedstawia graf ze zbiorem wierzchołków

edzi
i zbiorem kraw�

.

3
4 Rozdział 1. Grafy (nieskierowane)

�
Stopień wierzchołk� i wynosi 4, wierzchołki i sa stopnia 3, wierzchołki , i

stopnia 2.

Lemat 1.3 Niech , bedzie dowolnym grafem z kraw� Wtedy
� edziami.

Dowód: Jeżeli policzymy wszystkie kraw� �
edzie wychodzace ze wszystkich wierzchołków

grafu, to z jednej strony mamy sum� , a z drugiej ponieważ każda
e

kraw� jest liczona dwa razy, raz jak liczymy kraw� wychodzace z i
edz edzie �

drugi raz jak liczymy kraw� wychodzace z .
edzie �
Wniosek 1.4 Liczba wierzchołków o nieparzystych stopniach jest parzysta.

Graf nazywamy podgrafem grafu , jeżeli

oraz .
Przykład 1.5 Grafy �
przedstawione na rysunkach 1.5 i 1.6 sa podgrafami grafu z rysun-

ku 1.1 . Graf z 1.5 zawiera sześć wierzchołków
rysuku

i trzy kraw� .
edzie

Graf z rysuku 1.6 siedem wierzchołków
zawiera

i pieć kraw� .
� edzi

Graf pełny o wierzchołkach, oznaczany przez , jest to graf z wierzchołkami,
w którym każde dwa wierzchołki połaczone sa kraw� �
� � edzia.

Rysunek 1.2: a) Graf pełny . b) Graf pełny dwudzielny
a a
b b
c c
d d
e e
f f
a) b)

Graf jest dwudzielny, zbiór jego wierzchołków można rozbić na
jeżeli

dwie cześci , , tak, że każda kraw� ma końce w
� edz

obu zbiorach i . P dwudzielny ma zbiór wierzchołków rozbity na
ełny graf

dwa podzbiory: i , kraw� łacza każdy
a edzie � �

wierzchołek z z każdym wierzchołkiem z , czyli

.
1.1. Izomorfizm grafów 5
1.1 Izomorfizm grafów

Izomorfizmem grafu na graf nazywamy funkcje wza-
�

jemnie jednoznaczna spełniajaca warunek: wtedy i
� � � tylko

wtedy, gdy . Jeżeli taka funkcja istnieje, to mówimy, że grafy i
sa izomorficzne. Aatwo sprawdzić, że izomorfizm grafów jest relacja równoważności.
� �

Przykład 1.6 Rysunki 1.3a i 1.3b przedstawiaja ten sam graf ze zbiorem
�

wierzchołków oraz zbiorem kraw�
edzi

Graf z rysunku 1.4a jest izomorficzny z grafem . Izomorfizmem z

na jest funkcja określona nastepujaco: , , ,
� �

.

Graf z rysunku 1.4b nie jest izomorficzny z grafami i . Graf zawiera

wierzchołek stopnia jeden, a w grafie takiego wierzchołka nie ma.

Rysunek 1.3: Rysunki a) i b) przedstawiaja ten sam graf
�
a a
b d
c c
d b
a) b)

Rysunek 1.4: a) Graf izomorficzny z . b) Graf nieizomorficzny z
a a
b b
c c
d d
a) b)

Jeżeli mamy izomorfizm grafu na graf , to możemy

powiedzieć, że jest takim samym grafem co tylko ze zmienionymi nazwami wierz-
chołków.

Twierdzenie 1.7 Jeżeli grafy i sa izomorficzne, to:
�
6 Rozdział 1. Grafy (nieskierowane)

(a) i maja tyle samo wierzchołków, ,
�

(b) i maja tyle samo kraw� ,
� edzi,

(c) Dla każdego , i maja tyle samo wierzchołków stopnia .
�
Dowód:
(a) wynika bezpośrednio z definicji.

(b) Niech bedzie izomorfizmem z na . Ale okre wzajemna jednoznacz-
� śla także �

ność pomiedzy zbiorem kraw� .
� edzi

(c) Udowodnimy, że jeżeli jest stopnia , to i jest stopnia . Wiec
�
odwzorowuje wierzchołki stopnia na wierzchołki stopnia .

Niech , ... , beda wszystkimi wierzchołkami z połaczonymi kraw� z
� � � edziami

. Wtedy , ... , sa wszystkimi wierzchołkami z połaczonymi kraw�
� � edziami

z .
1.2 Drogi i cykle

Droga lub ścieżka w grafie jest to ci ag wierzchołków , dla każdego
� taki, że

� � edzia,
, wierzchołki , sa połaczone kraw� � czyli . O

drodze mówimy, że łaczy wierzchołki i . Mówimy także, że wierzcho-
�

łek jest osiagalny z wierzchołka . Droga jest zamknieta jeżeli .
� � Droga jest

prosta, jeżeli wszystkie wystepujace w niej wierzchołki sa różne. Droge
� � � �

nazywamy cyklem jeżeli , oraz wszystkie wierzchołki sa różne.
�

Przykład 1.8 W grafie z rysunku 1.1 ciag , , , , , , jest droga, a ciag , , , ,
� � �

jest cyklem. Ciag jest droga zamknieta, ale nie jest cyklem.
� � � �

Graf spójny, jeżeli dla każdych dwóch wierzchołków , istnieje ścieżka
jest
łaczaca i . Składowa spójności to maksymalny spójny podgraf grafu. Zauważmy, że w
� �

zbiorze wierzchołków grafu istnieje relacja osiagalności: i sa w relacji jeżeli
� �

lub jest osiagalny z . Relacja ta jest relacja równoważności i dzieli zbiór wierzchołków
� �
grafu na składowe spójności.
Przykład 1.9 Graf z rysunku 1.1 jest spójny, zawiera jedna składowa spójności (cały
� �
graf).
Graf z rysunku 1.5 nie jest spójny i zawiera trzy składowe spójności:

ze zbiorem wierzchołków i jedna kraw� �
� edzia

ze zbiorem wierzchołków i dwoma kraw�
edziami i ,

edzi.
z jednym wierzchołkiem i bez kraw�

Lemat 1.10 Je � �
żeli istnieje droga łaczaca wierzchołki i , , to istnieje też droga
prosta łaczaca i .
� �
1.3. Drzewa 7
Rysunek 1.5: Graf z trzema składowymi spójności

Dowód: Niech , bedzie najkrótsza droge łaczaca i . Droga
� � � � � �

ta jest prosta. Przypuśćmy bowiem, że , dla jakiegoś ; mielibyśmy wtedy

krótsza droge , łaczaca i , wbrew założeniu.
� � � � �
Dowolne dwa wierzchołki w cyklu moga być połaczone dwoma drogami prostymi.
� �

Na przykład w cyklu na rysunku 1.1, wierzchołki i łaczy droga oraz
�

droga . Tak, wiec, jeżeli w grafie sa cykle, to istnieja pary wierzchołkow, które sa
� � � �

połaczone dwoma drogami prostymi. Ale i na odwrót.
�

Lemat 1.11 Jeżeli w grafie istnieja dwa wierzchołki i , które można połaczyć
� �
dwoma różnymi drogami prostymi, to w grafie istnieje cykl.

Dowód: Niech , , beda dwoma roż-
� �

nymi prostymi drogami łaczacymi i . Możemy założyć, że (w przeciw-
� �

nym przypadku możemy usunać wspólny poczatek obu bedzie pierw-
� � dróg). Niech �

szym wierzchołkiem po , który wystepuje w drodze , i niech .
�

Wierzchołki nie wystepuja w drodze i droga
� �

tworzy cykl (w drodze tej wystepuja conajmniej trzy różne
� �

wierzchołki , oraz ).
Z tego lematu wynika, że graf jest acykliczny (nie ma cykli) wtedy i tylko wtedy, gdy
każde dwa wierzchołki grafu można połaczyć co najwyżej jedna droga prosta.
� � � �
1.3 Drzewa
Definicja 1.12 Spójny i acykliczny (bez cykli) graf to drzewo.
Z rozważań z poprzedniego podrozdziału wynika:
Lemat 1.13 Graf jest drzewem wtedy i tylko wtedy, gdy każde dwa jego wierzchołki moż-
na połaczyć dokładnie jedna prosta droga.
� � � �
8 Rozdział 1. Grafy (nieskierowane)
Rysunek 1.6: Przykład drzewa

Twierdzenie 1.14 Nastepujace trzy warunki sa równoważne:
� � �

(a) Graf jest drzewem.

(b) jest acykliczny, ale dodanie dowolnej kraw� psuje acykliczność; dodana kraw�
edzi edz

wraz z innymi kraw� grafu tworzy cykl.
edziami

(c) jest spójny, ale usuniecie dowolnej kraw�
� edzi psuje spójność; to znaczy bez

kraw� � �
edzi nie ma drogi łaczacej i .
Dowód:

Ponieważ jest drzewem, wiec jest acykliczny, przypuśćmy, że dodanie
�

kraw�
edzi nie dodaje cyklu w grafie, ale to oznacza, że w grafie nie ma drogi

łaczacej i . W przeciwnym przypadku mielibyśmy dwie drogi proste z do : jedną,
� �

która była w drzewie i drugą złożoną tylko z dodanej krawędzi, a więc na podstawie

lematu 1.11 dodanie kraw� zamykałoby cykl. Mamy sprzeczność, bo jako drzewo
edzi
jest spójny.

Trzeba pokazać, że jest spójny. Przypuśćmy jest, i że nie ma drogi
, że nie

łaczacej wierzchołki i . Ale wtedy dodanie kraw�
� � edzi nie dodaje cyklu (gdy-

by taki cykl powstał, to po usunieciu kraw� � �
� edzi z cyklu mielibyśmy droge prosta

łaczaca i ).
� �

jako drzewo jest spójny. Przypuśćmy, że odjecie kraw� nie psuje spój-
� edzi

ności. To znaczy, że w grafie istniały dwie drogi proste łaczace i , czyli na podstawie
� �
Lematu 1.11 w grafie jest cykl; sprzeczność.

Trzeba pokazać, że w nie ma cyklu. Gdyby w istniał cykl, to usuniecie
�
dowolnej kraw� tego cyklu nie psuje spójności; sprzeczność.
edzi

Lemat 1.15 W drzewie z wierzchołkami mamy kraw�
edzi.
Dowód: Przez indukcje ze wzgledu na liczbe wierzchołków. Jeżeli drzewo ma jeden
� � �
wierzchołek, to nie ma żadnych kraw�
edzi.
1.4. Przeszukiwanie grafów 9
Załóżmy teraz, że twierdzenie zachodzi dla każdego drzewa majacego mniej niż
�

wierzchołków i niech drzewo ma wierzchołków. W istnieje wierzchołek stopnia

� �
. Rzeczywiście, wezmy droge prosta w o maksymalnej długości .

Wierzchołek jest w grafie połaczony tylko z , bo inaczej mielibyśmy cykl lub dłuższa
� �

droge prosta. Usuńmy teraz z grafu wierzchołek i prowadzaca do niego kraw�
� � � � edz.

Otrzymany graf jest spójny i acykliczny ma wierzchołków i z założenia indukcyj-

nego kraw� czyli w grafie było kraw�
edzi, edzi.

Twierdzenie 1.16 Niech bedzie grafem z wierzchołkami, wtedy nastepujace trzy wa-
� � �
runki sa równoważne:
�

(a) Graf jest drzewem.

(b) jest acykliczny i posiada kraw�
edzi.

(c) jest spójny i posiada kraw�
edzi.
Dowód: Na podstawie lematu 1.15 z (a) wynika (b) i (c).

jest acykliczny, przypuśćmy, że nie jest drzewem. Wtedy na podstawie
twierdzenia 1.14 można do niego dodać jakaś kraw� nie psujac acykliczności. Jeże-
� edz �
li tak powstały graf nie jest drzewem, to dodajemy kolejne kraw� aż dojdziemy do
edzie,
acyklicznego grafu, w którym już żadnej kraw� nie można dodać bez dodania cyklu.
edzi

Tak powstały graf jest drzewem, ma wierzchołków i wiecej niż kraw� Doszli-
� edzi.
śmy wiec do sprzeczności z lematem 1.15.
�

jest spójny, przypuśćmy, że nie jest drzewem. Wtedy na podstawie twier-
dzenia 1.14 można z niego usunać jakaś kraw� nie psujac spójności. Jeżeli tak powstały
� � edz �
graf nie jest drzewem, to usuwamy kolejne kraw� aż dojdziemy do spójnego grafu,
edzie,
z którego już żadnej kraw� nie można usunać bez popsucia spójności. Tak powstały
edzi �

graf jest drzewem, ma wierzchołków i mniej niż kraw� Doszliśmy wiec do
edzi. �
sprzeczności z lematem 1.15.
Z powyższego dowodu wynika, że spójny graf z wierzchołkami nie może mieć

mniej niż kraw� czyli drzewo to spójny graf z minimalna liczba kraw�
edzi, � � edzi.
Podobnie, jeżeli graf ma wierzchołków i jest acykliczny, to nie może mieć wiecej niż
�

edzi, � � edzi.
kraw� czyli drzewa to grafy acykliczne z maksymalna liczba kraw�
Przykład 1.17 W drzewie z rysunku 1.6 nie można usunać żadnej kraw� bez rospój-
� edzi
nienia grafu. Nie można też dodać żadnej kraw� tak, aby nie powstał cykl. W grafie z
edzi

rysunku 1.1 można usunać kraw� �
� ed z i graf nadal bedzie spójny. Do grafu z rysun-

ku 1.5 można dodać kraw�
edz i nie powstanie żaden cykl.
1.4 Przeszukiwanie grafów
W rozdziale o strukturach danych zaprezentowano algorytmy przeszukiwania drzew w
głab i wszerz. Po niewielkich modyfikacjach algorytmy te można zastosować do przeszu-
�
kiwania grafów.
10 Rozdział 1. Grafy (nieskierowane)
Algorytm przeszukiwania grafu w głab.
�

Dane wejściowe: graf oraz wierzchołek poczatkowy ;
�

odwiedzamy i wkładamy go na STOS; zaznaczamy jako wierzchołek odwie-
dzony,

dopóki STOS nie jest pusty, powtarzamy:

jeżeli jest wierzchołkiem na wierzchu STOSU, to sprawdzamy, czy istnieje

wierzchołek , który jest połaczony kraw� � z wierzchołkiem i nie był jeszcze
� edzia
odwiedzony,

jeżeli takie sie znajdzie, to odwiedzamy , wkładamy go na wierzch STO-
�
SU i zaznaczamy jako wierzchołek odwiedzony,

jeżeli takiego nie ma, to zdejmujemy ze STOSU i cofamy sie do wierz-
�
chołka bedacego na STOSIE pod spodem.
� �
Rysunek 1.7: Przykład grafu

Przykład 1.18 Zastosujmy algorytm przeszukiwania w głab do grafu z rysunku 1.7. Po-
�
niższa tabela pokazuje jaki wierzchołek jest odwiedzany i jaka jest zawartość stosu po

każdej kolejnej iteracji petli algorytmu (przeszukanie zaczynamy od w� ). Przyjeto
� ezła �
zasade, że jeżeli jest kilka wierzchołków do wyboru, to wybieramy ten, którego nazwa stoi
�
wcześniej w alfabecie.
1.4. Przeszukiwanie grafów 11
Wierzchołek STOS
a a
b ab
c abc
d abcd
c abc
g abcg
f abcgf
g abcg
c abc
b ab
e abe
b ab
a a
W metodzie przeszukiwania w głab po każdym kroku algorytmu wierzchołki znajdujace
� �
sie na stosie tworza droge od wierzchołka wejściowego do wierzchołka aktualnie odwie-
� � �
dzanego.
Udowodnimy teraz, że algorytm odwiedzi wszystkie wierzchołki osiagalne z wierz-
�

chołka poczatkowego . Przypuśćmy bowiem, że w grafie istnieje wierzchołek osiagalny
� �

z , ale nie odwiedzony przez algorytm. Skoro jest osiagalny z , to istnieje droga
�

Poniewa ż był odwiedzony, a nie, to na tej drodze mamy dwa sasiednie wierzchołki
�

oraz takie, że był odwiedzony, a nie. W pewnym momencie algorytmu

wierzchołek był na stosie, a potem został z niego zdjety, ponieważ algorytm kończy
�
prace dopiero po zdjeciu wszystkich wierzchołków ze stosu. Zastanówmy sie teraz nad
� � �

krokiem algorytmu, w którym jest zdejmowany ze stosu. Ale nie mógł być zdjety ze
�

stosu, ponieważ istnieje jego sasiad , który nie był odwiedzony.
�
Aby udowodnić, że algorytm zawsze sie zatrzyma wystarczy zauważyć, że w każdej
�
iteracji petli albo jakiś wierzchołek jest wkładany na stos, albo jakiś jest zdejmowany ze
�
stosu. Z drugiej strony każdy wierzchołek jest tylko raz wkładany na stos (bo wkładane

sa tylko wierzchołki nieodwiedzane). Mamy wiec nie wiecej niż iteracji petli,
� � � �
a ponieważ w każdej etli algorytm wykonuje tylko kilka kroków, wiec czas działania
p� �

algorytmu jest rzedu .
�
Algorytm przeszukiwania wszerz.

Dane wejściowe: graf oraz wierzchołek poczatkowy ;
�

odwiedzamy , wkładamy go do KOLEJKI; zaznaczamy jako wierzchołek od-
wiedzony,

dopóki KOLEJKA nie jest pusta, powtarzamy:

bierzemy jeden wierzchołek z poczatku KOLEJKI,
�
12 Rozdział 1. Grafy (nieskierowane)

odwiedzamy wszystkie wierzchołki, które nie były jeszcze odwiedzane, a sa
�

połaczone kraw� � z wierzchołkiem , wkładamy je na koniec kolejki i zazna-
� edzia
czamy jako odwiedzone.
Przykład 1.19 Poniżej przedstawiono odwiedzane wierzchołki oraz zawartość kolejki po
każdej kolejnej iteracji petli algorytmu przeszukiwania wszerz dla grafu przedstawionego
�

na rysunku 1.7 (przeszukanie zaczynamy od w� ):
ezła
wierzchołki KOLEJKA
a a
b,c,d,e bcde
f cdef
g defg,
- efg,
- fg,
- g,

-
W metodzie przeszukiwania wszerz wierzchołki sa przeszukiwane w kolejności od wierz-
�
chołków bedacych najbliżej wierzchołka poczatkowego do wierzchołków bedacych dalej.
� � � � �
1.5 Liczenie składowych spójności
Algorytmu przeszukiwania grafów można użyć do liczenia składowych spójności.
Algorytm liczenia składowych spójności grafu

Dane wejściowe: graf .
Dane wyjściowe: liczba składowych spójności .

lsp:=0;

Powtarzaj dopóki sa jeszcze nieodwiedzone wierzchołki w grafie:
�

Wez jeden nieodwiedzony jeszcze wierzchołek ; lsp:=lsp+1;

przeszukaj (za pomoca algorytmu przeszukiwania grafu w głab) wszystkie
� �

wierzchołki osiagalne z i zaznacz je jako odwiedzone.
�
1.6 Drzewa spinajace
�

Definicja Drzewo spinajace (rozpinajace) grafu , to dowolne drzewo
1.20 � �

spełniajace warunek (zauważmy, że ma taki sam zbiór wierz-
�

chołków co ).
Przykład 1.21 Drzewo z rysunku 1.6 jest drzewem spinajacym dla grafu z rysunku 1.1.
�
1.6. Drzewa spinajace 13
�

Jeżeli graf nie jest spójny, to nie ma drzewa spinajacego. Z drugiej strony.
�
Twierdzenie 1.22 Każdy graf spójny zawiera jako podgraf drzewo spinajace.
�
Jako dowód przedstawimy algorytmy konstruowania drzewa spinajacego. W tym celu
�
lekko przerobimy algorytm przeszukiwania grafów w głab.
�
Algorytm konstruowania drzewa spinajacego przy przeszukiwania w głab.
� grafu �

Dane wejściowe: graf oraz wierzchołek poczatkowy ;
�

Dane wyjściowe: drzewo spinajace .
�

na poczatku drzewo spinajace nie zawiera żadnych kraw�
� � edzi:

odwiedzamy i wkładamy go na STOS; zaznaczamy jako wierzchołek odwie-
dzony,

dopóki STOS nie jest pusty, powtarzamy:

jeżeli jest wierzchołkiem na wierzchu STOSU, to sprawdzamy, czy istnieje

wierzchołek , który jest połaczony kraw� � z wierzchołkiem i nie był jeszcze
� edzia
odwiedzony,

jeżeli takie sie znajdzie, to odwiedzamy , wkładamy go na wierzch STO-
�

SU i zaznaczamy jako wierzchołek odwiedzony, kraw�
edz dodajemy do drze-
wa spinajacego:
�

jeżeli takiego nie ma, to zdejmujemy ze STOSU i cofamy sie do wierz-
�
chołka bedacego pod spodem.
� �
Rysunek 1.8: Drzewo spinajace dla grafu z rysunku 1.7
�

Przykład 1.23 Rysunek 1.8 przedstawia drzewo spinajace utworzone przez powyższy al-
�
gorytm dla grafu z rysunku 1.7
14 Rozdział 1. Grafy (nieskierowane)

Pokażemy teraz, że algorytm jest poprawny, czyli że tak utworzony graf jest drze-

wem. Zauważmy, że jeżeli wierzchołek (poza poczatkowym) jest wkładany na stos,
�

to do dokładana jest kraw� łaczaca z wierzchołkiem znajdujacym sie na stosie
edz � � � �

pod nim. Dlatego w każdym momencie wierzchołki na stosie stanowia droge w , łaczy
� � �
ona wierzchołek poczatkowy z aktualnie odwiedzanym wierzchołkiem. Ponieważ graf
�

jest spójny, to algorytm odwiedzi wszystkie wierzchołki grafu i jest grafem spój-

nym. Z każda kraw� � z możemy zwiazać wierzchołek, który jest wkładany na stos
� edzia �
w momencie jej powstania. Ponieważ, każdy wierzchołek jest wkładany na stos tylko

raz, mamy w kraw� (z poczatkowym wierzchołkiem nie jest zwiazana żadna
edzi � �

kraw� Tak wiec jest spójny, zawiera wszystkie wierzchołki grafu i ma
edz). �
kraw� jest wiec drzewem spinajacym.
edzi, � �
Podobnie można przerobić algorytm przeszukiwania grafu wszerz. Mówiac w skrócie
�
do drzewa należa te kraw� którymi przeszedł algorytm przeszukujac graf.
� edzie, �
1.7 Fundamentalny zbiór cykli

Niech bedzie spójnym grafem, a jego drzewem spinajacym. Kraw� drzewa
� � edzie

bedziemy nazywali gałeziami, a kraw� nie należace do drzewa cieciwami.
� � edzie � �

Z twierdzenia 1.14 wynika, że dodanie dowolnej cieciwy do drzewa utworzy cykl.
�

Oznaczmy ten cykl przez (oczywiście ). Zbiór tak utworzonych cykli stanowi
fundamentalny zbiór cykli. Jak za chwile pokażemy, każdy inny cykl w grafie jest różnica
� �
symetryczna cykli fundamentalnych. W tym podrozdziale cykle bedziemy traktować jako
� �
zbiory kraw�
edzi.
Przykład 1.24 Rozpatrzmy graf z rysunku 1.7 i jego drzewo spinajace z rysunku 1.8.
�

W tym przypadku � sa kraw� , , ,
gałeziami � edzie:

, � edzie ,
, , a cieciwami kraw�

, , . Fundamentalny zbiór cykli zawiera cykle:

, , ,

,
Zbiór kraw� grafu nazywamy pseudocyklem, jeżeli każdy wierzchołek grafu
edzi

�
jest parzystego stopnia. Przykładami pseudocykli sa cykle i zbiór pusty.
Lemat 1.25 Różnica symetryczna dowolnej liczby pseudocykli jest pseudocyklem.

Dowód: Wystarczy pokazać, że różnica symetryczna dwóch pseudocykli ,

jest pseudocyklem. Dla dowolnego wierzchołka zbiór kraw� przyległych
edzi

do w jest różnica symetryczna kraw� przyległych do w i w . A
� � edzi
ponieważ sa to zbiory parzystej mocy, wiec ich różnica symetryczna też jest parzystej
� �
mocy. Rzeczywiście dla dowolnych dwóch zbiorów i mamy

1.7. Fundamentalny zbiór cykli 15

Wezmy teraz dowolny cykl (lub pseudocykl) grafu i utwórzmy róznice
�

Jest to różnica symetryczna cykli fundamentalnych utworzonych z cieciw wchodzacych
� �
do . Pokażemy, że

W tym celu rozważmy zbiór

Na podstawie lematu 1.25, zbiór ten jest pseudocyklem. Z drugiej strony nie zawie-

ra żadnych cieciw, ponieważ każda cieciwa albo nie należy do żadnego składnika tej
� �

różnicy, jeżeli , albo należy do dokładnie dwóch: do i do . Zatem zbiór

jest podzbiorem drzewa , i jest pusty, bo inaczej musiałby zawierać wierzchołki stopnia
jeden, co jest sprzeczne z faktem, że jest pseudocyklem. Zatem

Udowodniliśmy zatem nastepujace:
� �
Twierdzenie 1.26 Każdy cykl (pseudocykl) jest różnica pewnej liczby cykli fundamental-
�
nych.

Przykład 1.27 (Kontynuacja przykładu 1.24) Cykl jest różnica
�
symetryczna cykli i . Rzeczywiście
�

Cykl jest różnica symetryczna cykli , i .
� �

Rzeczywiście

Lemat 1.28 Jeżeli graf jest spójny oraz posiada wierzchołków i kraw� to ma
edzi,

cykli fundamentalnych.

Dowód: Wynika, to z faktu, że drzewo spinajace ma kraw�
� edzi
Jeżeli graf nie jest spójny, to każda składow� spójności możemy traktowć osobno.
� a

Niech , , ... , beda składowymi spójności i niech składowa ma
� � grafu

wierzchołków i kraw� Dla każdej składowej mamy drzewo spinajace z
edzi. �

kraw� oraz cykli fundamentalnych. Niech zbiór cykli fundamentalnych
edziami
całego grafu bedzie sum� cykli fundamentalnych składowych. Każdy cykl w grafie należy
� a
16 Rozdział 1. Grafy (nieskierowane)
w całości do jednej składowej spójności, bo sam jest spójny, i może być przedstawiony

jako różnica symetryczna cykli fundamentalnych. W całym grafie mamy wiec
�

cykli fundamentalnych. Udowodniliśmy wiec nastepujace
� � �

Twierdzenie 1.29 W dowolnym grafie mamy cykli fundamentalnych,

gdzie jest liczba wierzchołków, liczba kraw� a liczba składowych spójności.
� � edzi, �

Aby przekonać sie, czy graf ma cykl wystarczy policzyć i jeżeli , to
�
graf nie ma cykli.
1.8 Minimalne drzewo spinajace
�

Wyobrazmy sobie, że każda kraw� w grafie ma długość . Na przy-
edz
kład, wierzchołki grafu sa miejscowościami i długość kraw� jest odległościa miejsco-
� edzi �
wo teraz skonstruować minimalne drzewo spinajace, czyli drzewo spinajace
ści. Chcemy � �

z minimalna sum� długości kraw�
� a edzi

Algorytm budowy minimalnego drzewa spinajacego
�

Dane wejściowe: graf z funkcja wagi .
�

Dane wyjściowe: minimalne drzewo spinajace .
�

Posortuj kraw� grafu według długości, od najkrótszej do najdłuższej.
edzie

Dla każdej kraw� wstaw ja do pod warunkiem, że nie tworzy ona
edzi �

cyklu z kraw� które już sa w .
edziami, �
Przykład 1.30 Po zastosowaniu powyższego algorytmu do grafu z rysunku 1.9a otrzyma-
my drzewo przedstawione na rysunku 1.9b

Najpierw poka że tak utworzony graf jest drzewem spinajacym. Po każdej
żemy, �
iteracji petli, graf nie zawiera cyklu, wiec na końcu też jest acykliczny. Przypuśćmy,
� �

że po zakończeniu algorytmu nie jest spójny. Istnieja wiec w dwa wierzchołki i ,
� �

które sa połaczone w droga (bo jest spójny), które nie sa
� � � ale �

połaczone w . Na drodze tej sa wiec dwa sasiednie wierzchołki i , które nie sa
� � � � �

połaczone w droga. Ale wtedy dodanie krawędzi do drzewa nie tworzy w
� �

nim cyklu i algorytm powinien dodać kraw� do , sprzeczność.
edz
1.9. Cykle i drogi Eulera 17
Rysunek 1.9: a) Graf z wagami, b) Jego minimalne drzewo spinajace
�
16
a a
b b
6 6
13 7 13 7
9
c c
d d
8 8
11 10 11
19
e e
f f
a) b)

Pokażemy teraz, że jest drzewem spinajacym. Przypuśćmy, że nie
minimalnym �

jest minimalne. Niech bedzie takim minimalnym drzewem, które ma z
�
najwieksza liczbe wspólnych kraw� Niech bedzie kraw� � z minimalna waga,
� � � edzi. � edzia � �

która należy do , ale nie należy do . Jeżeli dodamy do to otrzymamy cykl. Niech

bedzie kraw� � w tym cyklu, która należy do , ale nie należy do .
� edzia
Niech bedzie które powstaje z po zamianie na . powstaje przez
� drzewem,

usuniecie z grafu . Jest to graf spójny z kraw� czyli drzewo.
� edziami,

Jeżeli , to drzewo byłoby drzewem z mniejsza od waga, wbrew mi-
� �

nimalności . Jeżeli , to drzewo byłoby minimalnym drzewem z wieksza
� �

od liczba wspólnych z kraw� znowu sprzeczność. Mamy wiec .
� edzi, �

Jeżeli dodamy teraz kraw� do , to otrzymamy cykl (to może być inny cykl
edz

niż ten w ). W tym cyklu istnieje kraw� , która należy do , ale nie
edz

do . Przypuśćmy, że . W takim przypadku algorytm powinien wstawić

kraw� do drzewa , bo w momencie rozpatrywania w drzewie nie ma jeszcze
edz

i wstawienie nie zamyka cyklu. Wynika, to z faktu, że graf jest

drzewem, � edz nie tworzy cyklu z kraw� z . Mamy wiec
wiec kraw� edziami �

co jest sprzeczne z faktem, że była najlżejsza kraw� � z i
� edzia
nienależaca do .
� �
1.9 Cykle i drogi Eulera
Droga Eulera to droga, która przechodzi przez każda kraw� grafu dokładnie jeden raz.
� edz
Cykl Eulera to taka droga zamknieta, w której każda kraw� grafu wystepuje dokładnie
� edz �
raz.
Euler w 18. wieku pokazał, że istnieje dość prosta charakteryzacja grafów z droga
�
lub cyklem Eulera. Mianowicie spójny graf posiada cykl Eulera, wtedy i tylko wtedy gdy
każdy jego wierzchołek jest parzystego stopnia, a posiada droge Eulera jeżeli co najwyżej
�
18 Rozdział 1. Grafy (nieskierowane)
dwa jego wierzchołki sa stopnia nieparzystego. Pamietamy, wniosek 1.4, że w każdym
� �
grafie liczba wierzchołków nieparzystego stopnia jest parzysta. Tak wiec graf z droga
� �
Eulera ma dwa lub zero wierzchołków nieparzystego stopnia.

Przykład 1.31 Graf na rysunku 1.1 ma dwa wierzchołki nieparzystego stopnia i i

posiada droge Eulera .
�

Wyobrazmy sobie, że idziemy wzdłuż kraw� grafu, i po przejściu każdej kraw�
edzi edzi
usuwamy ja z grafu. Przechodzac przez jakiś wierzchołek usuwamy dwie kraw� ta,
� � edzie, �
która weszliśmy do wierzchołka, i ta, która go opuściliśmy. Dlatego, jeżeli po dojściu do
� � �
jakiegoś wierzchołka, nie ma już kraw� z niego odchodzacych, to albo doszliśmy do
edzi �
wierzchołka poczatkowego, albo do wierzchołka nieparzystego stopnia.
�
Z tego wynika, że jeżeli w grafie istnieje droga Eulera, to moga w nim być co najwyżej
�
dwa wierzchołki nieparzystego stopnia, poczatek i koniec drogi, a jeżeli droga Eulera jest
�
zamknieta i stanowi cykl Eulera, to wszystkie wierzchołki w grafie sa parzystego stopnia.
� �
Pokażemy teraz, że sa to także warunki wystarczajace. Zaczniemy od cyklu Eulera.
� �
Twierdzenie 1.32 Spójny graf posiada cykl Eulera wtedy i tylko wtedy, gdy każdy jego
wierzchołek jest parzystego stopnia.
Dowód: Konieczność warunku udowodniliśmy wyżej. Teraz pokażemy, że jest to wa-
runek wystarczajacy. Załóżmy, że każdy wierzchołek jest parzystego stopnia. Niech
�
bedzie najdłuższa pod wzgledem liczby kraw� droga w grafie bez powtarzania kraw�
� � � edzi � edzi.
Z rozważań zrobionych wyżej wynika, że jest to droga zamknieta. Przypuśćmy, że droga
�
ta nie zawiera jeszcze wszystkich kraw� grafu. Ponieważ graf jest spójny, wieć istnieje
edzi �

wierzchołek na tej drodze, od którego odchodzi kraw� nie należaca do . Może-
edz �
my teraz utworzyć dłuższa droge bez powtarzania kraw� zawiera ona i potem idzie
� � edzi:
wzdłuż . Jest to sprzeczne z założeniem, że była najdłuższa droga.
� �
Twierdzenie 1.33 Spójny graf posiada droge Eulera wtedy i tylko wtedy, gdy posiada co
�
najwyżej dwa wierzchołki nieparzystego stopnia.
Dowód: Konieczność warunku pokazano wyżej. Teraz pokażemy, że jest to warunek
wystarczajacy. Ponieważ graf nie może posiadać tylko jednego stopnia niepa-
� wierzchołka
rzystego, to wystarczy rozważyć graf z dwoma wierzchołkami i nieparzystego stopnia.

Dodajmy do grafu nowy wierzchołek i połaczmy go kraw� z i . Teraz każdy
� edziami
wierzchołek jest stopnia parzystego i posiada cykl Eulera. Po usunieciu z niego nowych
�
kraw� i wierzchołka otrzymamy droge Eulera w pierwotnym grafie.
edzi �
Powyższy dowód, chociaż krótki, ma te wade, że nie daje dobrego algorytmu znaj-
� �
dowania drogi Eulera. Nie sposób przegladać wszystkich możliwych dróg, bo jest ich
� �
bardzo dużo.
Poniżej pokażemy dwa znacznie szybkie algorytmy znajdowania cyklu Eulera.
Algorytm wyszukiwania cyklu Eulera

Dane wejściowe: spójny graf ze wszystkimi wierzchołkami parzystego stopnia.

Zaczynamy od dowolnego wierzchołka .
1.9. Cykle i drogi Eulera 19

Powtarzamy, aż do wyczerpania kraw�
edzi:

Jeżeli z bierzacego wierzchołka nie odchodzi żadna kraw� to koniec
� edz,
algorytmu.

Jeżeli z bierzacego wierzchołka odchodzi tylko jedna kraw� to prze-
� edz,
chodzimy wzdłuż tej kraw� do nastepnego wierzchołka, usuwamy ta kraw� i
edzi � � edz

wierzchołek z grafu.

Jeżeli z odchodzi wiecej niż jedna kraw� to wybieramy ta kraw� któ-
� edz, � edz,
rej usuniecie nie rozspójnia grafu; przechodzimy wzdłuż tej kraw� do nastepnego
� edzi �
wierzchołka, usuwamy ta kraw� z grafu.
� edz
Rysunek 1.10: Przykład grafu z cyklem Eulera

Przykład 1.34 W grafie z rysunku 1.10 wszystkie wierzchołki sa parzystego stopnia. Prze-
�

śledzmy, jak działa powyższy algorytm. Zaczynamy od wierzchołka i przyjmijmy, że w
razie wyboru algorytm wybierze kraw� do wierzchołka z wcześniejsza (według alfabe-
edz �

tu) litera. Tak wiec przejdzie do potem do i do . Rysunek 1.11 przedstawia nasz graf
� �

po tych trzech krokach, usunieciu odwiedzanych kraw� i wierzchołka (z którego nie
� edzi
odchodza już żadne kraw�
� edzie).

Teraz algorytm nie może wybrać kraw� ponieważ usuniecie tej kraw� roz-
edzi � edzi

spójni graf. Zamiast tego algorytm powinien wybrać kraw� i przejść do wierz-
edz

chołka , a potem do . Teraz znowu nie powinien iść do tylko do , a potem już bez

problemów do końca cyklu Eulera: , , , , , .

Pokażemy teraz poprawność tego algorytmu. Przypuśćmy, że po kilku krokach je-

steśmy w wierzchołku , z którego odchodzi kilka kraw� Pokażemy, że wśród tych
edzi.
kraw� co najwyżej jedna jest zła (jej usuniecie może rozspójnić graf). Z przebiegu
edzi �
algorytmu wynika, że graf w aktualnej postaci (po usunieciu być może jakiś kraw�
� edzi
lub wierzchołków) jest nadal spójny i co najwyżej dwa wierzchołki w nim sa nieparzy-
�

stego stopnia i (co zachodzi jeżeli ). Wiec posiada on droge Eulera. Idzmy
� �
20 Rozdział 1. Grafy (nieskierowane)
Rysunek 1.11: Graf po przejściu trzech kraw�
edzi

ta droga zaczynajac od . Droga ta kończy sie w lub i przechodzi kilka razy przez
� � � �

. Mamy wiec kilka petli, które zaczynaja sie i kończa w i być może końcowy odci-
� � � � �

nek zaczynajacy sie w i kończacy w . Otóż tylko pierwsza kraw� tego ostatniego
� � � edz

odcinka może rozspójniać graf. Wszystkie inne kraw� wychodzace z sa cześciami
edzie � � �
cykli.
Aby udowodnić, że algorytm dobrze działa, trzeba pokazać, że wszystkie kraw�
edzie
grafu beda odwiedzone. Po każdej iteracji algorytmu graf jest spójny, wiec jeżeli z wierz-
� � �
chołka nie odchodza żadne kraw� to znaczy, że nie ma już żadnych kraw� w
� edzie, edzi
grafie.
Powyższy algorytm mimo, że prosty i szybki wymaga sprawdzania, czy usuniecie
�
kraw� nie rozspójni grafu.
edzi
Drugi algorytm wyznaczania cyklu Eulera.
Dane wejściowe: spójny graf, w którym wszystkie wierzchołki sa parzystego stopnia.
�
Pomocniczy STOS.
Dane wyjściowe: CE cykl Eulera.

Zaczynamy od dowolnego wierzchołka i wkładamy go na STOS,

Natepnie powtarzamy dopóki STOS nie jest pusty
�

Niech bedzie wierzchołkiem z wierzchu STOSU
�

jeżeli z odchodza jakieś nieodwiedzane kraw� to wybieramy jedna z
� edzie, �
nich, przechodzimy na jej drugi koniec, zaznaczamy jako odwiedzona i jej drugi
�
koniec wkładamy na STOS.

Jeżeli wszystkie kraw� odchodzace z były już odwiedzone, to zdejmu-
edzie �

jemy ze STOSU, przekładamy na wyjście CE oraz przechodzimy do wierzchołka

znajdujacego sie pod na STOSIE.
� �
1.10. Drogi i cykle Hamiltona 21
Przykład 1.35 Prześledzmy działanie algorytmu na przykładzie z rysunku 1.10. Poniższa
tabela zawiera: odwiedzany wierzchołek, stan STOSU oraz stan pliku wyjściowego CE po
każdym kroku z pierwszych szesnastu kroków.
Krok wierzchołek STOS CE
1 a a -
2 b ab -
3 c abc -
4 d abcd -
5 a abcda -
6 d abcd a
7 e abcde a
8 f abcdef a
9 g abcdefg a
10 d abcdefgd a
11 g abcdefg ad
12 f abcdef adg
13 h abcdefh adg
14 b abcdefhb adg
15 i abcdefhbi adg
16 f abcdefhbif adg
Po szesnastu krokach wszystkie kraw� zostały odwiedzone i teraz STOS krok po
edzie
kroku zostanie przełożony na wyjście CE. Otrzymamy nastepujacy cykl Eulera:
� �

Z algorytmu wynika, że kolejne wierzchołki na obu stosach sa połaczone kraw�
� � edziami
i że każda kraw� (jako para sasiednich wierzchołków) pojawia sie na STOSIE tylko
edz � �
raz. Należy wiec tylko pokazać, że wszystkie kraw� znajda sie na wyjściu. Jeżeli
� edzie �
pominieto jakieś kraw� to ponieważ graf jest spójny jakaś nieodwiedzona kraw�
� edzie, edz

musi przylegać do wierzchołka , który jest w wynikowym cyklu, ale jest przekładany
na wyjście tylko tedy, gdy nie odchodza od niego już żadne nieodwiedzane kraw�
� edzie.
W każdej iteracji algoryt przechodzi jakaś kraw� Albo wkładajac jej koniec na
� edz. �
STOS, albo przekładajac ja na wyjście CE. A ponieważ każda kraw� jest odwiedzana
� � edz
dokładnie dwa razy, raz jak jest wkładana na STOS i drugi raz jak jest przekładana na CE,
wiec czas działania algorytmu jest proporcjonalny do liczby kraw� w grafie.
� edzi
1.10 Drogi i cykle Hamiltona
Droga Hamiltona to taka droga w grafie, która przechodzi dokładnie raz przez każdy
wierzchołek grafu. Cykl Hamiltona to zamknieta droga Hamiltona.
�

Przykład 1.36 Graf z rysunku 1.1 posiada droge Hamiltona , ale nie po-
�

siada cyklu Hamiltona. Każdy graf pełny z posiada cykl Hamiltona.
22 Rozdział 1. Grafy (nieskierowane)
Inaczej niż dla cyklu lub drogi Eulera nie jest znane żadne proste kryterium rozstrzy-
gania, czy dany graf posiada droge lub cykl Hamiltona. Nie jest także znany żaden al-
�
gorytm wyszukiwania drogi lub cyklu Hamiltona działajacy w czasie wielomianowym.
�
Naiwnym sposobem szukania drogi Hamiltona jest sprawdzanie wszystkich możliwych
dróg w grafie, ale algorytm ten jest bardzo czasochłonny, bo mamy około możliwych
dróg w grafie z wierzchołkami.
Innym algorytmem szukania drogi Hamiltona jest tak zwane wyszukiwanie z nawro-
tami. Mówiac w skrócie szukanie z nawrotami idzie pierwsza możliw� ścieżka tak daleko
� � a �
jak to tylko możliwe okładajac kolejne odwiedzane w� na stos. W momencie, gdy al-
� ezły
gorytrm utknie w ślepej uliczce, to cofa sie o jeden krok i próbuje innej drogi. Załóżmy,
�
że wierzchołki grafu sa uporzadkowane na przykład według alfabetu lub sa kolejnymi
� � �

liczbami naturalnymi
Algorytm z nawrotami wyszukiwania drogi Hamiltona

Dane wejściowe: graf oraz wierzchołek poczatkowy .
�

Dane wyjściowe: droga Hamiltona zaczynajaca sie od , lub informacja, że takiej drogi
� �
nie ma.

włóż na STOS

powtarzaj aż do skutku:

jeżeli jest wierzchołkiem na wierzchu STOSU, to szukamy wierzchołka

o najniższym możliwie numerze połaczonego z kraw� � i nie wystepujacy
� edzia � �

na STOSIE. Jeżeli w poprzedniej iteracji zdjeto ze STOSU wierzchołek , to
�
powinien być wiekszy od .
�

Jeżeli takie znajdziemy, to wkładamy je na STOS. Jeżeli wierzchołki na
STOSIE tworza już droge Hamiltona, to koniec algorytmu.
� �

Jeżeli takiego nie znajdziemy, to zdejmujemy ze STOSU.
Przykład 1.37 Prześledzmy działanie algorytmu na przykładzie grafu z rysunku 1.1. Po-
niższa tabela zawiera: odwiedzany wierzchołek, oraz stan STOSU po każdym kolejnym
kroku (szukanie rozpoczynamy od wierzchołka ).
1.11. Kolorowanie grafów 23
Krok wierzchołek STOS
1 d d
2 a da
3 b dab
4 c dabc
5 f dabcf
6 e dabcfe
7 f dabcf
8 g dabcfg
9 f dabcf
10 c dabc
11 g dabcg
12 f dabcgf
13 e dacgfe
Powyższy algorytm mimo, że szybszy od naiwnego algorytmu sprawdzania wszyst-
kich dróg, ma wykładnicza złożoność czasow�
� a.
1.11 Kolorowanie grafów
Chodzi o takie pokolorowanie wierzchołków grafu, żeby wierzchołki połaczone kraw� �
� edzia
były pokolorowane innymi kolorami i żeby liczba kolorów była jak najmniejsza.

Definicja 1.38 Pokolor grafu kolorami jest to funkcja
owanie

, taka że jeżeli .

Najmniejsze takie , że graf można �
pokolorować kolorami nazywamy liczba

chromatyczna grafu i oznaczamy przez .
�
W przypadku kolorowania grafów, podobnie jak dla dróg Hamiltona, nie sa znane do-
�
bre i szybkie algorytmy. Naiwny algorytm sprawdzajacy wszystkie możliwe kolorowania
�
działa zbyt długo. Także tu mamy algorytm z nawrotami.
Algorytm z nawrotami kolorowania wierzchołków grafu

Dane wejściowe: graf oraz liczba naturalna .

Dane wyj pokolorowanie wierzchołków grafu za pomoca kolorów
ściowe: �

lub informacja, że takiego pokolorowania nie ma.

dla każdego podstaw ( oznacza, że nie ma jeszcze
koloru).

włóż pierwszy wierzchołek na STOS,

powtarzaj aż do skutku:

jeżeli jest wierzchołkiem na wierzchu STOSU, to próbujemy przypisać mu

kolor, wiekszy od bieżacego koloru , który nie koliduje z kolorami wierzchoł-
� �
ków znajdujacych sie na STOSIE. Jeżeli to sie uda, to wkładamy kolejny wierzcho-
� � �

łek na stos. Jeżeli sie nie uda, to zdejmujemy ze stosu i podstawiamy .
�
24 Rozdział 1. Grafy (nieskierowane)
W tym algorytmie próbujemy kolejnym wierzchołkom przypisać pierwszy z rzedu
�
kolor i pokolorowane wierzchołki umieszczamy na stosie. Jak zabrniemy w ślepa uliczke,
� �
to cofamy sie do poprzedniego wierzchołka na stosie i próbujemy nastepnego koloru.
� �
Przykład 1.39 Zastosujmy powyżwszy algorytm do grafu z rysunku 1.12, aby znalezć

kolorowanie trzema kolorami . Najpierw każdy wierzchołek dostaje kolor , co
oznacza, że nie jest jeszcze pokolorowany.
Rysunek 1.12: Przykład grafu

Zaczynamy od wierzchołka . W pierwszych pieciu krokach algorytm pokoloruje wierz-
�

chołki , , , i w nastepujacy sposób:
� �
u a b c d e f
c(u) 1 2 1 2 3 0
a na stosie mamy wierzchołki

Teraz algorytm nie może pokolorować wierzchołka , bo jest on połaczony z , , , które
�
sa pokolorowane kolorami 1, 2, 3. Dlatego jest zdjete ze stosu:
� �

Teraz zdejmujemy wierzchołek , bo nie można mu przypisać wyższego koloru, i podsta-

wiamy .

Teraz zmieniamy kolor na , a nastepnie kolorujemy i wkładamy na
�
stos.
u a b c d e f
c(u) 1 2 1 3 2 0

�
W tym momencie pokolorowanie nie jest możliwe, wiec zdejmujemy go ze stosu

1.11. Kolorowanie grafów 25
Wierzchołek też nie może być pokolorowany wyższym kolorem, wiec też go zdejmujemy.
�

Wierzchołek ma w tym momencie najwyższy kolor , więc zmiana koloru nie jest
możliwa i zdejmujemy go ze stosu. Mamy teraz nastepujace kolorowanie
� �
u a b c d e f
c(u) 1 2 1 0 0 0
i stos

Teraz zmieniamy kolor na , a nastepnie już bez nawrotów kolorujemy
�

, , . Ostateczne kolorowanie wyglada tak:
�
u a b c d e f
c(u) 1 2 3 1 2 3

Jeżeli zastosujemy powyższy algorytm do pokolorowania grafu pełnego ko-

lorami, to wypróbuje on wszystkie kolorowań pierwszych wierzchołków.
dla

Pesymistyczny czas działania algorytmu jest wiec .
�

Problem kolorowania grafów jest trywialny, jeżeli mamy tylko jeden kolor .
Jednym kolorem można pokolorować tylko grafy bez kraw�
edzi.
Proste jest też kolorowanie grafów dwoma kolorami. Grafy, które można pokolorować
dwoma kolorami, to grafy dwudzielne. Grafu nie można pokolorować dwoma kolorami,
jeżeli zawiera cykl nieparzystej długości. Poniżej pokażemy, że i na odwrót: jeżeli graf
nie ma cyklu nieparzystej długości, to można go pokolorować dwoma kolorami.
Poniżej przedstawiamy algorytm kolorowania grafów dwoma kolorami. Dla prostoty
zakładamy, że kolorowane grafy sa spójne. Algorytm można łatwo przerobić tak, aby
�
kolorował wszystkie grafy.
Algorytm kolorowania grafu dwoma kolorami

Dane wejściowe: spójny graf .

Dane wyj pokolorowanie wierzchołków grafu za pomoca dwóch kolorów
ściowe: �

lub informacja, że takiego pokolorowania nie ma.

wez pierwszy wierzchołek , pokoloruj go pierwszym kolorem .

powtarzaj aż do skutku: Wez wszystkie wierzchołki, które sa połaczone kraw� �
� � edzia
z jakimś wierzchołkiem pokolorowanym w poprzedniej iteracji i nie maja jeszcze
�
koloru..

Jeżeli wśród nich żadne dwa nie sa połaczone kraw� � to pokoloruj je
� � edzia,
jednym kolorem (innym niż wierzchołki kolorowane w poprzedniej iteracji).

Jeżeli wśród nich sa dwa połaczone kraw� � to pokolorowanie dwoma
� � edzia,
kolorami nie jest możliwe.
26 Rozdział 1. Grafy (nieskierowane)

Kolorowanie otrzymywane w tym algorytmie jest prawidłowe. Niech oznacza

wierzchołki kolorowane w -tej iteracji, . Wierzchołki z sa kolorowane na
�

pierwszy kolor, jeżeli jest parzyste, i na drugi kolor, jeżeli jest nieparzyste. Zauważmy,

że dowolny wierzchołek może być połaczony kraw� � tylko z wierzchołka-
� edzia

mi ze zbiorów i . zawiera wszystkie wierzchołki, które sa połaczone z
� �

wierzchołkami z i nie miały koloru po pokolorowaniu , tak wiec żaden ze zbiorów
�

z nie zawiera wierzchołków połaczonych z .
�

Zauważmy, że jeżeli dwa wierzchołki i należa do , to istnieja drogi
�

oraz takie, że . Niech

, bedzie ostatnim wspólnym wierzchołkiem na obu drogach. Ponieważ zbiory
�

sa to wspólne wierzchołki musza mieć te same indeksy. Droga
� rozłaczne, �
�

jest droga z parzysta liczba kraw� Dlatego, jeżeli i sa połaczone kraw� �
� � � edzi. � � edzia,
to w grafie mamy cykl nieparzystej długości i pokolorowanie dwoma kolorami nie jest
możliwe.
Z powyższych rozważań wynika
Lemat 1.40 Graf jest dwudzielny (może być pokolorowany dwoma kolorami) wtedy i tyl-
ko wtedy, gdy nie zawiera cykli nieparzystej długości.
Wniosek 1.41 Każde drzewo można pokolorować dwoma kolorami.
Nie jest znany algorytm kolorujacy grafy trzema kolorami (lub dowolna wieksza
� � � �
liczba kolorów) działajacy w czasie wielomianowym.
� �
Ponieważ nie sa znane szybkie algorytmy kolorowania grafów stosuje sie heurystyki,
� �
czyli algorytmy niedokładne. Na przykład nastepujaca heurystyka
� �
Heurystyka kolorowania grafu

Posortuj wierzchołki grafu według ich stopni.

Dla każdego wierzchołka po kolei przypisz mu najniższy możliwy kolor.
W wielu przypadkach heurystyka ta da optymalne rozwiazanie, na przykład dla grafu
�
z rysunku 1.12.
1.12 Hiperkostka

Hiperkostka wymiaru 1 jest przedstawiona na rysunku 1.13a. Składa sie ona z dwóch
�

wierzchołków 0 i 1 połaczonych kraw� � Hiperkostke wymiaru 2 (rysunek 1.13b)
� edzia. �

budujemy z dwóch kostek . W pierwszej kostce numerujemy wierzchołki przez 00 i 01
(dopisujemy 0 na poczatek nazwy każdego wierzchołka). W drugiej kostce numerujemy
�
wierzchołki przez 10 i 11 (dopisujemy 1 na poczatek). Nastepnie łaczymy kraw�
� � � edziami
odpowiadajace sobie wierzchołki z obu kopii 00 z 10 i 01 z 11.
�

Podobnie budujemy hiperkostke wymiaru z dwóch kostek . W pierwszej
�
kostce numerujemy wierzchołki dopisujac 0 na poczatku nazwy każdego wierzchołka.
� �
W drugiej kostce numerujemy wierzchołki dopisujac 1 na poczatek. Nastepnie łaczymy
� � � �
1.13. Rozgłaszanie wiadomości 27

Rysunek 1.13: a) Hiperkostka , b) Hiperkostka
01 11
1
0 00 10
a) b)

kraw� odpowiadajace sobie wierzchołki z obu czyli wierzchołek jest
edziami � kopii,

połaczony z wierzchołkiem , dla każdego . Rysunek 1.14 przedstawia
�

hiperkostke .
�

W rezultacie hiperkostka to graf , gdzie zawiera wszystkie

ciagi bitów długości , a dwa wierzchołki , sa połaczone kraw� � wtedy i tylko
� � � edzia
wtedy, gdy różnia sie dokładnie jednym bitem.
� �

Jak łatwo widać w kostkach i sa cykle Hamiltona (w jest droga Hamiltona).
�
Ogólniej mamy

� � � �
Lemat 1.42 Każda hiperkostka zawiera droge Hamiltona. zaczynajaca sie w wierz-

chołku i kończaca w wierzchołku .
� �

Dowód przez indukcje ze wzgledu na wymiar kostki. zawiera droge Hamiltona
� � �

zawiera droge Hamiltona z do . składa sie z dwóch
Załóżmy, że � �

z
hiperkostek . Droga w zaczyna sie w punkcie . W pierszej hiperkostce (tej
�

0 na poczatku każdego wierzchołka) przechodzi do , potem kraw� � do
� edzia
�
i w drugiej hiperkostce (tej z 1 na poczatku każdego wierzchołka) w odwrotnym kierunku

do .

Cykl Hamiltona w tworzy tak zwany kod Graya. Jest to ciag wszyskich elemen-
�
towych ciagów bitów, każdy wystepuje raz, każde dwa kolejne różnia sie jednym bitem
� � � �
oraz ostatni ciąg różni się jednym bitem od pierwszego.
1.13 Rozgłaszanie wiadomości

Graf może przedstawiać sieć połaczeń. Wierzchołki sa agentami, a kraw�
� � edzie
to łacza, którymi agenci moga sie komunikować. Wyobrazmy sobie, że jeden agent posia-
� � �
da jakaś wiadomość, która chce przekazać wszystkim innym agentom w sieci. Reguły sa
� � �
nastepujace. Komunikacja odbywa sie synchronicznie w taktach. W każdym takcie każdy
� � �
agent może przekazać wiadomość jednemu swojemu sasiadowi.
�
Powyższy problem nazywa sie problemem rozgłaszania. Poniżej pokażemy, że można
�

go bardzo efektywnie rozwiazać, jeżeli graf jest hiperkostka . B� traktować
� � edziemy
ciag bitów jako przedstawienie dwójkowe liczby naturalnej.
�
28 Rozdział 1. Grafy (nieskierowane)

Rysunek 1.14: Hiperkostka

Najpierw prześledzmy działanie tego protokułu na hiperkostce (rysunek 1.14).

Załóżmy, że wierzchołek jest żródłem wiadomości. W pierwszym takcie przeka-

zuje on ja do wierzchołka . Zauważmy, że po pierwszym takcie wiadomość jest
�
znana wierzchołkom o numerach mniejszych od 2 i, że te wierzchołki tworza hiperkostke
� �

wymiaru 1. W drugim takcie przekaże wiadomość do wierzchoł-
wierzchołek

ka , a wierzchołek do . Po drugim takcie wiadomość znaja
�
wierzchołki numerach mniejszych od 4 i tworza � wymiaru 2. W trzecim
o � one hiperkostke

takcie przekazuje wiadomość do , do , do

, a do . Tak wiec po trzech taktach wszystkie wierzchołki w
�
znaja wiadomość.
�

Protokół rozsyłania wiadomości w hiperkostce

Na poczatku wiadomość ma wierzchołek .
�

Powtarzaj dla

w -tym takcie każdy wierzchołek przekazuje wiadomość do wierzchołka

.

Aby pokazać poprawność tego protokołu, pokażemy przez indukcje, że po -tym

takcie wiadomość jest znana wszystkim wierzchołkom o numerach mniejszych od .

Przed pierwszym taktem wiadomość jest znana wierzchołkom o numerach mniejszych

od , czyli wierzchołkowi 0. Załóżmy, że przed -tym taktem wiadomość jest znana
1.14. Zbieranie informacji 29

�
wszystkim o numerach od . S to dokładnie wierzchołki
wierzchołkom mniejszych a

�
postaci , gdzie (jeżeli to jest pustym ciagiem). W

-tym takcie każdy taki wierzchołek przekaże wiadomość do , czyli po

-tym takcie wiadomość beda znały wszystkie wierzchołki, które maj pierwszych
� � a na
�
bitach zera, czyli wszystkie wierzchołki o numerach mniejszych od .
Protokół ten (po małych przeróbkach) można także stosować do grafu pełnego lub do
innego grafu, który zawiera hiperkostke.
�
1.14 Zbieranie informacji
Hiperkostka jest także wygodna struktura do zbierania informacji, gdy chcemy do jed-
� �
nego wierzchołka zebrać informacje od wszystkich wierzchołków. Informacje te należy
przesyłać w odwrotnym kierunku niż w protkóle rozsyłania. Zakładamy, że przesyłane
�
informacje sa łaczone w pakiety i wierzchołek może przesłać w jednym takcie cały pakiet
� �
zawierajacy kilka informacji.
�

Protokół zbierania wiadomości w hiperkostce

Powtarzaj dla

w -tym takcie każdy wierzchołek postaci , gdzie

przesyła swój pakiet do wierzchołka ,

Przykład 1.43 Prześledzmy działanie tego protokułu na hiperkostce (rysunek 1.14).

W pierwszym takcie wierzchołek przekazuje swoją wiadomość do , wierzchołek

do , wierzchołek do , a wierzchołek do .

W drugim takcie wierzchołek przekazuje zebrane wiadomości (swoją i te, kt.ore

otrzymał w poprzednim takcie) do , a wierzchołek do .

W trzecim takcie wierzchołek przekazuje zebrane wiadomości do . a wierz-

chołek do .
1.15 Plotkowanie
Plotkowanie polega na tym, że na poczatku każdy wierzchołek ma jakaś wiadomość i
� �
chce ja rozesłać do wszystkich innych wierzchołków w grafie.
�
Znajac protokoły do zbierania i rozsyłania wiadomości możemy zaprojektować proto-
�
kół plotkowania, który najpierw zbiera wszystkie informacje do jednego w� a nastepnie
ezła, �
rozsyła je do wszystkich wierzchołków.
1.16 Zadania
1. Ile krawędzi ma graf pełny ?
2. Ile maksymalnie krawędzi może mieć graf z wierzchołkami?
30 Rozdział 1. Grafy (nieskierowane)

3. Ile jest grafów ze zbiorem wierzchołków ?

4. Ile krawędzi ma dwudzielny graf pełny ?
5. Udowodnij, że izomorfizm grafów jest relacja równoważności.
�

6. Narysuj wszystkie grafy ze zbiorem wierzchołków . Które z nich sa
�
izomorficzne?
7. Narysuj możliwie jak najwiecej nieizomorficznych grafów z czterema wierzchoł-
�

kami .
8. Narysuj dwa nieizomorficzne grafy z ta sam� (możliwie jak najmniejsza) liczba
� a � �
wierzchołków.
9. Narysuj dwa nieizomorficzne drzewa z ta sam� (możliwie jak najmniejsza) liczba
� a � �
wierzchołków.
10. Narysuj dwa nieizomorficzne grafy z ta sam� (możliwie jak najmniejsza) liczba
� a � �
wierzchołków i ta sam� liczba kraw�
� a � edzi.
11. Narysuj dwa nieizomorficzne grafy, które maja ta sam� liczba wierzchołków stop-
� � a �
nia , dla każdego .
12. Zastosuj algorytm przeszukiwania grafu w głab (wszerz) do grafów z rysunków 1.1
�
i 1.10.
13. Zkonstruuj drzewa spinajace dla grafów z rysunków 1.1 i 1.10.
�
14. Korzystajac z drzew spinajacych z poprzedniego zadania, znajdz zbiór cykli funda-
� �
mentalnych dla grafów.
15. Zmodyfikuj algorytm przeszukiwania grafu wszerz tak, aby wyznaczał on także
drzewo spinajace (złożone z tych kraw� którymi przeszedł algorytm). Zastosuj
� edzi,
ten algorytm do grafów z rysunków 1.1, 1.7 i 1.10.
16. Sprawdz, które grafy przedstawione na rysunkach w tym rozdziale posiadaja cykl
�
(lub droge) Eulera.
�
17. Sprawdz, które grafy przedstawione na rysunkach w tym rozdziale posiadaja cykl
�
lub droge Hamiltona.
�
18. Zastosuj algorytm kolorowania z nawrotami do grafu z rysunku 1.7.
19. Znajdz graf, dla którego heurystyka przedstawiona w podrozdziale o kolorowaniu
grafów nie znajduje optymalnego kolorowania.

20. Narysuj hiperkostke . Wskaż w niej cykl Hamiltona. Prześledz na niej protokół
�
rozsyłania wiadomości.
1.17. Problemy 31
1.17 Problemy

Oto algorytm konstrukcji minimalnego drzewa spinajacego dla grafu
�

: (1) edzi
zaczynamy od zbioru wszystkich kraw� grafu , (2) sortujemy

kraw� według długości, od najdłuższej do najkrótszej (3) dla każdej kraw�
edzie edzi

usuwamy ja z , jeżeli jej usuniecie nie rozspójnia grafu .
� �
Udowodnij poprawność tego algorytmu.
Zastosuj powyższy algorytm do grafu z rysunku 1.9a.

Niech bedzie dowolnym grafem z wagami kraw� , a
� edzi

dowolnym minimalnym drzewem spinajacym. Pokaż, że dla dowolnego wierzchołka
�

do należa te kraw� wychodzacych z , które maja najkrótsze wagi, to znaczy,
� edzie �

� edziami
jeżeli i sa dwiema kraw� przyległymi do takimi, że oraz , to

.

Wyszukiwarka

Podobne podstrony:
Matematyka dyskretna 2004 10 Grafy skierowane
Matematyka dyskretna 2002 02 Arytmetyka
Matematyka dyskretna 2002 08 Struktury danych
Matematyka dyskretna 2002 11 Poprawność programów
Matematyka dyskretna 2002 07 Rekurencja
Matematyka Dyskretna Grafy Zadania
2002 09 Creating Virtual Worlds with Pov Ray and the Right Front End
Lista zadan nr 3 z matematyki dyskretnej
Algorytmy Matematyka Dyskretna
2002 09 Genialne schematy
2002 09 Transformator Tesli, część 1

więcej podobnych podstron