Matematyka Dyskretna
Andrzej Szepietowski
25 marca 2004 roku
Rozdział 1
Grafy (nieskierowane)
Najpierw podamy podstawowe definicje i fakty, część z nich była już przedstawiona w
rozdziale pierwszym.
Definicja 1.1 Graf (nieskierowany) G = (V, E) jest to para składająca się ze skończo-
nego zbioru wierzchołków V oraz ze zbioru krawędzi E, gdzie krawędzie to pary wierz-
chołków E ą" {{u, v} | u, v " V, u = v}.

Rysunek 1.1: Przykład grafu
a
c
b d
g
e f
Stopień wierzchołka v, oznaczany przez d(v), jest to liczba krawędzi wychodzących z v.
W rozdziale o kombinatoryce udowodniliśmy następujący lemat.
Lemat 1.2 W dowolnym grafie G = (V, E) z m = |E| krawędziami zachodzi
" d(v) = 2m.
v"V
" Liczba wierzchołków o nieparzystych stopniach jest parzysta.
3
4 Rozdział 1. Grafy (nieskierowane)
Graf H = (VH , EH) nazywamy podgrafem grafu G = (VG, EG), jeżeli VH ą" VG
oraz EH ą" EG. Graf pełny o n wierzchołkach, oznaczany przez Kn, jest to graf z n
wierzchołkami, w którym każde dwa wierzchołki połączone są krawędzią.
Rysunek 1.2: Graf pełny dwudzielny K3,3
a c
b
e f
d
Graf G = (V, E) jest dwudzielny, jeżeli zbior jego wierzchołków można rozbić na
dwie części V = V1 *" V2, V1 )" V2 = ", tak, że każda krawędz
e " E ma końce w
obu zbiorach V1 i V2. Pełny graf dwudzielny Km,n ma zbior wierzchołków rozbity na
dwa podzbiory: V1 = {v1, . . . , vm} i V2 = {w1, . . . , wn}, a krawędzie łączą każdy
wierzchołek z V1 z każdym wierzchołkiem z V2, czyli E = {{vi, wj} | 1 d" i d" m, 1 d"
j d" n}.
1.1 Izomorfizm grafów
Izomorfizmem grafu G = (VG, EG) na graf H = (VH , EH) nazywamy funkcjÄ™ wza-
jemnie jednoznaczną h : VG VH spełniającą warunek: {u, v} " EG wtedy i tylko
wtedy, gdy {h(u), h(v)} " EH . Jeżeli taka funkcja istnieje, to mówimy, że grafy G i H
sÄ… izomorficzne. A
atwo sprawdzić, że izomorfizm grafów jest relacją równoważności.
Przykład 1.3 Rysunki 1.3a i 1.3b przedstawiają ten sam graf G4 = (V4, E4) ze zbiorem
wierzchołków V4 = {a, b, c, d} oraz zbiorem krawędzi
E4 = {{a, b}, {a, c}, {a, d}, {b, c}}
Graf G5 = (V5, E5) z rysunku 1.4a jest izomorficzny z grafem G4. Izomorfizmem z G5
na G4 jest funkcja h : V5 V4 określona następująco: h(a) = c, h(b) = b, h(c) = a,
h(d) = d.
Graf G6 z rysunku 1.4b nie jest izomorficzny z grafami G4 i G5. Graf G4 zawiera
wierzchołek d stopnia jeden, a w grafie G6 takiego wierzchołka nie ma.
Jeżeli mamy izomorfizm grafu G = (VG, EG) na graf H = (VH , EH), to możemy
powiedzieć, że H jest takim samym grafem co G tylko ze zmienionymi nazwami wierz-
chołków.
Twierdzenie 1.4 Jeżeli grafy G = (VG, EG) i H = (VH , EH) są izomorficzne, to:
(a) G i H mają tyle samo wierzchołków, |VG| = |VH |,
1.2. Drogi i cykle 5
Rysunek 1.3: Rysunki a) i b) przedstawiajÄ… ten sam graf G4
a
a d
c c
b b
a) b)
Rysunek 1.4: a) Graf G5 izomorficzny z G4. b) Graf G6 nieizomorficzny z G4
a a
b b
c c
d d
a) b)
(b) G i H mają tyle samo krawędzi, |EG| = |EH |,
(c) Dla każdego k, G i H mają tyle samo wierzchołków stopnia k.
Dowód:
(a) wynika bezpośrednio z definicji.
(b) Niech h będzie izomorfizmem z VG na VH. Ale h określa także wzajemną jednoznacz-
ność pomiędzy zbiorem krawędzi h({u, v}) = {h(u), h(v)}.
(c) Udowodnimy, że jeżeli v " VG jest stopnia k, to i h(v) " VH jest stopnia k. Niech
v1, ... , vk będą wszystkimi wierzchołkami z VG połączonymi krawędziami z v. Wtedy
h(v1), ... , h(vk) są wszystkimi wierzchołkami z VH połączonymi krawędziami z h(v).
Pokazaliśmy więc, że h odwzorowuje wierzchołki stopnia k na wierzchołki stopnia k.
Należy zwrócić uwagę, że warunki (a), (b) oraz (c) nie są wystarczające do izomorfi-
zmu grafów. Istnieją pary grafów G i H, które spełniają wszystkie trzy warunki, ale nie
sÄ… izomorficzne.
1.2 Drogi i cykle
Droga lub ścieżka w grafie jest to ciąg wierzchołków v0, v1, . . . , vk, taki, że dla każdego
i, 1 d" i d" k, wierzchołki vi-1, vi są połączone krawędzią, czyli {vi-1, vi} " EG. O
6 Rozdział 1. Grafy (nieskierowane)
drodze v0, v1, . . . , vk mówimy, że łączy wierzchołki v0 i vk. Mówimy także, że wierzcho-
łek vk jest osiągalny z wierzchołka v1. Droga jest zamknięta jeżeli v0 = vk. Droga jest
prosta, jeżeli wszystkie występujące w niej wierzchołki są różne. Drogę v0, v1, . . . , vk
nazywamy cyklem jeżeli v0 = vk, k e" 3 oraz wszystkie wierzchołki v1, . . . , vk są różne.
Graf G jest spójny, jeżeli dla każdych dwóch wierzchołków u, v " VG istnieje ścieżka
łącząca u i v. Składowa spójności to maksymalny spójny podgraf grafu. Zauważmy, że w
zbiorze wierzchołków grafu istnieje relacja osiągalności: u i v są w relacji jeżeli u = v
lub v jest osiągalny z u. Relacja ta jest relacją równoważności i dzieli zbior wierzchołków
grafu na składowe spójności.
Przykład 1.5 Grafy z rysunków 1.1, 1.2 oraz 1.3 są spójne. Graf z rysunku 1.5 nie jest
spójny i zawiera trzy składowe spójności:
" H1 ze zbiorem wierzchołków {a, d} i jedną krawędzią {a, d}
" H2 ze zbiorem wierzchołków {b, c, f} i dwoma krawędziami {b, c} i {c, f},
" H3 z jednym wierzchołkiem {e} i bez krawędzi.
Rysunek 1.5: Graf z trzema składowymi spójności
a c
b
e f
d
W rozdziale 1 udowodniliśmy następujące fakty:
Lemat 1.6 W dowolnym grafie G:
" Jeżeli istnieje droga łącząca wierzchołki u i v, u = v, to istnieje też droga prosta

Å‚Ä…czÄ…ca u i v.
" Jeżeli istnieją dwa wierzchołki u i v, u = v które można połączyć dwoma różnymi

drogami prostymi, to istnieje tez
cykl.
" Graf jest acykliczny (nie ma cykli) wtedy i tylko wtedy, gdy każde dwa jego wierz-
chołki można połączyć co najwyżej jedną drogą prostą.
1.3 Drzewa
Definicja 1.7 spójny i acykliczny (bez cykli) graf to drzewo.
1.3. Drzewa 7
Rysunek 1.6: Przykład drzewa
a
c
b d
g
e f
Lemat 1.8 Graf jest drzewem wtedy i tylko wtedy, gdy każde dwa jego wierzchołki można
połączyć dokładnie jedną prostą drogą.
Twierdzenie 1.9 Następujące trzy warunki są równoważne:
(a) Graf G jest drzewem.
(b) G jest acykliczny, ale dodanie dowolnej krawędzi psuje acykliczność; dodana kra-
wędz
wraz z innymi krawędziami grafu G tworzy cykl.
(c) G jest spójny, ale usunięcie dowolnej krawędzi {u, v} psuje spójność; to znaczy bez
krawędzi {u, v} nie ma drogi łączącej u i v.
Dowód:
(a) Ò! (b) Ponieważ G jest drzewem, wiÄ™c jest acykliczny, przypuśćmy, że dodanie kra-
wędzi {u, v} nie dodaje cyklu w grafie, ale to oznacza, że w grafie G nie ma drogi łączącej
u i v. W przeciwnym przypadku mielibyśmy dwie drogi proste z u do v: jedną, która była
w drzewie G i drugą złożoną tylko z dodanej krawędzi, a więc na podstawie lematu 1.6
dodanie krawędzi zamykałoby cykl. Mamy sprzeczność, bo G jako drzewo jest spójny.
(b) Ò! (a) Trzeba pokazać, że G jest spójny. Przypuśćmy, że nie jest, i że nie ma drogi Å‚Ä…-
czącej wierzchołki u i v. Ale wtedy dodanie krawędzi {u, v} nie dodaje cyklu (gdyby taki
cykl powstał, to po usunięciu krawędzi {u, v} z cyklu mielibyśmy drogę prostą łaczącą u
i v).
(a) Ò! (c) G jako drzewo jest spójny. Przypuśćmy, że odjÄ™cie krawÄ™dzi nie psuje spój-
ności. To znaczy, że w grafie istniały dwie drogi proste łączące u i v, czyli na podstawie
Lematu 1.6 w grafie G jest cykl; sprzeczność.
(c) Ò! (a) Trzeba pokazać, że w G nie ma cyklu. Gdyby w G istniaÅ‚ cykl, to usuniÄ™cie
dowolnej krawędzi tego cyklu nie psuje spójności; sprzeczność.
Lemat 1.10 W drzewie z n wierzchołkami mamy n - 1 krawędzi.
8 Rozdział 1. Grafy (nieskierowane)
Dowód: Przez indukcję ze względu na liczbę wierzchołków. Jeżeli drzewo ma jeden
wierzchołek, to nie ma żadnych krawędzi.
Założmy teraz, że twierdzenie zachodzi dla każdego drzewa mającego mniej niż n
wierzchołków i niech drzewo G ma n wierzchołków. W G istnieje wierzchołek v stopnia
d(v) = 1. Rzeczywiście, weżmy drogę prostą w G o maksymalnej długości v1, v2, . . . , vk.
Wierzchołek v1 jest w grafie połączony tylko z v2, bo inaczej mielibyśmy cykl lub dłuż-
szą drogę prostą. Usuńmy teraz z grafu G wierzchołek v i prowadzącą do niego krawędz
.
Otrzymany graf jest spójny i acykliczny ma n - 1 wierzchołków i z założenia indukcyj-
nego n - 2 krawędzi, czyli w grafie G było n - 1 krawędzi.
Twierdzenie 1.11 Niech G będzie grafem z n wierzchołkami, wtedy następujące trzy wa-
runki są równoważne:
(a) Graf G jest drzewem.
(b) G jest acykliczny i posiada n - 1 krawędzi.
(c) G jest spójny i posiada n - 1 krawędzi.
Dowód: Na podstawie lematu 1.10 z (a) wynika (b) i (c).
(b) Ò! (a) G jest acykliczny, przypuśćmy, że nie jest drzewem. Wtedy na podstawie
twierdzenia 1.9 można do niego dodać jakąś krawędz
nie psując acykliczności. Jeżeli tak
powstały graf nie jest drzewem, to dodajemy kolejne krawędzie, aż dojdziemy do acy-
klicznego grafu, w którym już żadnej krawędzi nie można dodać bez dodania cyklu. Tak
powstały graf jest drzewem, ma n wierzchołków i więcej niż n - 1 krawędzi. Doszliśmy
więc do sprzeczności z lematem 1.10.
(c) Ò! (a) G jest spójny, przypuśćmy, że nie jest drzewem. Wtedy na podstawie twier-
dzenia 1.9 można z niego usunąć jakąś krawędz
nie psując spójności. Jeżeli tak powstały
graf nie jest drzewem, to usuwamy kolejne krawędzie, aż dojdziemy do spójnego grafu,
z którego już żadnej krawędzi nie można usunąć bez popsucia spójności. Tak powstały
graf jest drzewem, ma n wierzchołków i mniej niż n - 1 krawędzi. Doszliśmy więc do
sprzeczności z lematem 1.10.
Z powyższego dowodu wynika, że spójny graf z n wierzchołkami nie może mieć
mniej niż n - 1 krawędzi, czyli drzewo to spójny graf z minimalną liczbą krawędzi.
Podobnie, jeżeli graf ma n wierzchołków i jest acykliczny, to nie może mieć więcej niż
n - 1 krawędzi, czyli drzewa to grafy acykliczne z maksymalną liczbą krawędzi.
Przykład 1.12 W drzewie z rysunku 1.6 nie można usunąć żadnej krawędzi bez rospój-
nienia grafu. Nie można też dodać żadnej krawędzi tak, aby nie powstał cykl. W grafie z
rysunku 1.1 można usunąć krawędz
{a, b} i graf nadal będzie spójny. Do grafu z rysun-
ku 1.5 można dodać krawędż {a, b} i nie powstanie żaden cykl.
1.4 Przeszukiwanie grafów w głąb
W rozdziale o stosach kolejkach i drzewach zaprezentowano algorytmy przeszukiwania
drzew w głąb i wszerz. Po niewielkich modyfikacjach algorytmy te można zastosować do
przeszukiwania grafów.
1.4. Przeszukiwanie grafów w głąb 9
Algorytm przeszukiwania grafu w głąb.
Dane wejściowe: graf G = (V, E) oraz wierzchołek początkowy v " V ;
Odwiedzamy v, wkładamy go na STOS i zaznaczamy jako odwiedzony,
dopokiSTOS nie jest pusty, powtarzamy:
Niech v będzie wierzchołkiem na wierzchu STOSU,
sprawdzamy, czy istnieje wierzchołek u, który
jest połączony z v
nie był odwiedzony,
jeżeli takie u się znajdzie, to
odwiedzamy u,
wkładamy go na wierzch STOSU i
zaznaczamy jako wierzchołek odwiedzony,
jeżeli takiego u nie ma, to
zdejmujemy v ze STOSU
cofamy się do wierzchołka będącego na STOSIE pod spodem.
Przykład 1.13 Zastosujmy algorytm przeszukiwania w głąb do grafu z rysunku 1.1. Po-
niższa tabela pokazuje jaki wierzchołek jest odwiedzany i jaka jest zawartość stosu po
każdej kolejnej iteracji pętli algorytmu (przeszukanie zaczynamy od węzła a). Przyjęto
zasadę, że jeżeli jest kilka wierzchołków do wyboru, to wybieramy ten, którego nazwa stoi
wcześniej w alfabecie.
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łąb po każdym kroku algorytmu wierzchołki znaj-
dujące się na stosie tworzą drogę od wierzchołka wejściowego do wierzchołka aktualnie
odwiedzanego.
Udowodnimy teraz, że algorytm odwiedzi wszystkie wierzchołki osiągalne z wierz-
chołka początkowego v. Przypuśćmy bowiem, że w grafie istnieje wierzchołek w osiągal-
ny z v, ale nie odwiedzony przez algorytm. Skoro w jest osiÄ…galny z v, to istnieje droga
v = v0, v1, . . . , vk = w.
10 Rozdział 1. Grafy (nieskierowane)
Ponieważ v0 był odwiedzony, a vk nie, to na tej drodze mamy dwa sąsiednie wierzchołki
vi oraz vi+1 takie, że vi był odwiedzony, a vi+1 nie. W pewnym momencie algorytmu
wierzchołek vi był na stosie, a potem został z niego zdjęty, ponieważ algorytm kończy
pracę dopiero po zdjęciu wszystkich wierzchołków ze stosu. Zastanówmy się teraz nad
krokiem algorytmu, w którym vi jest zdejmowany ze stosu. Ale vi nie mogł być zdjęty ze
stosu, ponieważ istnieje jego sąsiad vi+1, który nie był odwiedzony.
Aby udowodnić, że algorytm zawsze się zatrzyma wystarczy zauważyć, że w każdej
iteracji pętli 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
są tylko wierzchołki nieodwiedzane). Mamy więc nie więcej niż 2n = 2|V | iteracji pętli,
a ponieważ w każdej pętli algorytm wykonuje tylko kilka kroków, więc czas działania
algorytmu jest rzędu O(n).
1.5 Algorytm przeszukiwania grafu wszerz.
Algorytm przeszukiwania wszerz.
Dane wejściowe: graf G = (V, E) oraz wierzchołek początkowy v " V ;
Odwiedzamy v, wkładamy go do KOLEJKI i zaznaczamy jako odwiedzony,
dopoki KOLEJKA nie jest pusta, powtarzamy:
bierzemy jeden wierzchołek v z początku KOLEJKI,
odwiedzamy wszystkie wierzchołki, które
nie były jeszcze odwiedzane,
są połączone z v,
wkładamy je na koniec kolejki i zaznaczamy jako odwiedzone.
Przykład 1.14 Poniżej przedstawiono odwiedzane wierzchołki oraz zawartość kolejki po
każdej kolejnej iteracji pętli algorytmu przeszukiwania wszerz dla grafu przedstawionego
na rysunku 1.1 (przeszukanie zaczynamy od węzła a):
wierzchołki KOLEJKA
a a
b,c,d,e bcde
f cdef
g defg,
- efg,
- fg,
- g,
- "
W metodzie przeszukiwania wszerz wierzchołki są przeszukiwane w kolejności od wierz-
chołków będących najbliżej wierzchołka początkowego do wierzchołków będących dalej.
1.6. Liczenie składowych spójności 11
1.6 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 G = (V, E).
Dane wyjściowe: liczba składowych spójności  lsp.
lsp:=0;
Dopoki są jeszcze nieodwiedzone wierzchołki w grafie, powtarzaj:
Wez
jeden nieodwiedzony jeszcze wierzchołek v;
lsp:=lsp+1;
przeszukaj wszystkie wierzchołki osiągalne z v i zaznacz je jako odwiedzone.
1.7 Drzewa spinajÄ…ce
Definicja 1.15 Drzewo spinajÄ…ce (rozpinajÄ…ce) grafu G = (V, E), to dowolne drzewo
T = (V, ET ) spełniające warunek ET ą" E (zauważmy, że T ma taki sam zbior wierz-
chołków co G).
Przykład 1.16 Graf z rysunku 1.6 jest drzewem spinającym dla grafu z rysunku 1.1
Jeżeli graf G nie jest spójny, to nie ma drzewa spinającego. Z drugiej strony.
Twierdzenie 1.17 Każdy graf spójny zawiera jako podgraf drzewo spinające.
Jako dowód przedstawimy algorytmy konstruowania drzewa spinającego. W tym celu
lekko przerobimy algorytm przeszukiwania grafów w głąb.
Algorytm konstruowania drzewa spinającego przy przeszukiwania grafu w głąb.
Dane wejściowe: graf G = (V, E) oraz wierzchołek początkowy v0 " V ;
Dane wyjściowe: drzewo spinające T = (V, ET ).
Na początku drzewo spinające nie zawiera żadnych krawędzi: ET := "
odwiedzamy v0, wkładamy na STOS; zaznaczamy jako odwiedzony,
dopoki STOS nie jest pusty, powtarzamy:
Niech v będzie wierzchołkiem na wierzchu STOSU,
sprawdzamy, czy istnieje nieodwiedzony wierzchołek u, który jest połączony z v.
jeżeli takie u się znajdzie, to
odwiedzamy u,
wkładamy go na wierzch STOSU
zaznaczamy jako wierzchołek odwiedzony,
krawędz
{v, u} dodajemy do drzewa spinajÄ…cego:
jeżeli takiego u nie ma, to
zdejmujemy v ze STOSU
cofamy się do wierzchołka będącego pod spodem.
12 Rozdział 1. Grafy (nieskierowane)
Rysunek 1.7: Drzewo spinajÄ…ce dla grafu z rysunku 1.1
a
c
b d
g
e f
Przykład 1.18 Rysunek 1.7 przedstawia drzewo spinające utworzone przez powyższy al-
gorytm dla grafu z rysunku 1.1
Pokażemy teraz, że algorytm jest poprawny, czyli że tak utworzony graf T jest drze-
wem. Zauważmy, że jeżeli wierzchołek u (poza początkowym) jest wkładany na stos,
to do T dokładana jest krawędz
łącząca u z wierzchołkiem znajdującym się na stosie
pod nim. Dlatego w każdym momencie wierzchołki na stosie stanowią drogę w T , łączy
ona wierzchołek początkowy z aktualnie odwiedzanym wierzchołkiem. Ponieważ graf
jest spójny, to algorytm odwiedzi wszystkie wierzchołki grafu G i T jest grafem spój-
nym. Z każdą krawędzią z T możemy związać wierzchołek, który jest wkładany na stos
w momencie jej powstania. Ponieważ, każdy wierzchołek jest wkładany na stos tylko
raz, mamy w T n - 1 krawędzi (z początkowym wierzchołkiem nie jest związana żadna
krawędz
). Tak więc T jest spójny, zawiera wszystkie wierzchołki grafu G i ma n - 1
krawędzi, jest więc drzewem spinającym.
Podobnie można przerobić algorytm przeszukiwania grafu wszerz. Mówiąc w skrocie
do drzewa należą te krawędzie, którymi przeszedł algorytm przeszukując graf.
1.8 Fundamentalny zbior cykli
Niech G będzie spójnym grafem, a T jego drzewem spinającym. Krawędzie drzewa bę-
dziemy nazywali gałęziami, a krawędzie nie należące do drzewa T cięciwami.
Z twierdzenia 1.9 wynika, że dodanie dowolnej cięciwy e do drzewa T utworzy cykl.
Oznaczmy ten cykl przez Ce (oczywiście e " Ce). Zbior tak utworzonych cykli stanowi
fundamentalny zbior cykli. Jak za chwilę pokażemy, każdy inny cykl w grafie jest różnicą
symetryczną cykli fundamentalnych. W tym podrozdziale cykle będziemy traktować jako
zbiory krawędzi.
Przykład 1.19 Rozpatrzmy graf z rysunku 1.1 i jego drzewo spinające z rysunku 1.7.
W tym przypadku gałęziami są krawędzie: f1 = {a, b}, f2 = {b, c}, f3 = {c, d},
1.8. Fundamentalny zbior cykli 13
f4 = {c, g}, f5 = {f, g}, f6 = {b, e}, a cięciwami krawędzie e1 = {a, c}, e2 =
{a, d}, e3 = {b, f}, e4 = {a, e}. Fundamentalny zbior cykli zawiera cykle: Ce =
1
{e1, f1, f2} = abca, Ce = {e2, f1, f2, f3} = abcda, Ce = {e3, f2, f4, f5} = bcgfb,
2 3
Ce = {e4, f1, f6} = abea,
4
Zbior krawędzi C grafu nazywamy pseudocyklem, jeżeli każdy wierzchołek grafu
(V, C) jest parzystego stopnia. Przykładami pseudocykli są cykle i zbior pusty.
Lemat 1.20 różnica symetryczna dowolnej liczby pseudocykli jest pseudocyklem.
Dowód: Wystarczy pokazać, że różnica symetryczna C1 •" C2 dwóch pseudocykli C1,
C2 jest pseudocyklem. Dla dowolnego wierzchołka v " V zbior krawędzi przyległych
do v w C1 •" C2 jest różnicÄ… symetrycznÄ… krawÄ™dzi przylegÅ‚ych do v w C1 i w C2. A
ponieważ są to zbiory parzystej mocy, więc ich różnica symetryczna też jest parzystej
mocy. Rzeczywiście dla dowolnych dwóch zbiorów A i B mamy
|A •" B| = |A *" B| - |A )" B| = |A| + |B| - 2|A )" B|.
Weżmy teraz dówolny cykl (lub pseudocykl) C grafu G i utworzmy roznicę
Ce.
e"C-T
Jest to różnica symetryczna cykli fundamentalnych utworzonych z cięciw wchodzących
do C. Pokażemy, że
C = Ce.
e"C-T
W tym celu rozważmy zbior
D = C •" Ce.
e"C-T
Na podstawie lematu 1.20, zbior ten jest pseudocyklem. Z drugiej strony D nie zawie-
ra żadnych cięciw, ponieważ każda cięciwa e albo nie należy do żadnego składnika tej
różnicy, jeżeli e " C, albo należy do dokładnie dwóch: do C i do Ce. Zatem zbior D
/
jest podzbiorem drzewa T , i jest pusty, bo inaczej musiałby zawierać wierzchołki stopnia
jeden, co jest sprzeczne z faktem, że D jest pseudocyklem. Zatem
C = Ce.
e"C-T
Udowodniliśmy zatem następujące:
Twierdzenie 1.21 Każdy cykl (pseudocykl) jest różnicą pewnej liczby cykli fundamental-
nych.
14 Rozdział 1. Grafy (nieskierowane)
Przykład 1.22 (Kontynuacja przykładu 1.19) Cykl {e1, e2, f3} = acda jest różnicą
symetryczną cykli Ce i Ce . Rzeczywiście
1 2
{e1, e2, f3} = {e1, f1, f2} •" {e2, f1, f2, f3} = Ce •" Ce
1 2
Cykl {e1, f4, f5, e3, f6, e4} = acgfbea jest różnicą symetryczną cykli Ce , Ce i Ce .
1 3 4
Rzeczywiście
{e1, f4, f5, e3, f6, e4} = {e1, f1, f2}•"{e3, f2, f4, f5}•"{e4, f1, f6} = Ce •"Ce •"Ce .
1 3 4
Lemat 1.23 Jeżeli graf G jest spójny oraz posiada n wierzchołków i m krawędzi, to ma
m - n + 1 cykli fundamentalnych.
Dowód: Wynika, to z faktu, że drzewo spinające ma n - 1 krawędzi
Jeżeli graf nie jest spójny, to każdą składową spójności możemy traktowć osobno.
Niech G1, G2, ... , Gp będą składowymi spójności grafu G i niech składowa Gi ma ni
wierzchołków i mi krawędzi. Dla każdej składowej Gi mamy drzewo spinające Ti z ni-1
krawędziami oraz mi -ni +1 cykli fundamentalnych. Niech zbior cykli fundamentalnych
całego grafu będzie sumą cykli fundamentalnych składowych. Każdy cykl w grafie należy
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 G mamy więc
p
(mi - ni + 1) = m - n + p
i=1
cykli fundamentalnych. Udowodniliśmy więc następujące
Twierdzenie 1.24 W dowolnym grafie G mamy r(G) = m-n+p cykli fundamentalnych,
gdzie n jest liczbą wierzchołków, m liczbą krawędzi, a p liczbą składowych spójności.
Aby przekonać się, czy graf G ma cykl wystarczy policzyć r(G) i jeżeli r(G) = 0, to
graf nie ma cykli.
1.9 Minimalne drzewo spinajÄ…ce
Wyobraz
my sobie, że każda krawędz
e w grafie G = (V, E) ma długość w(e). Na przy-
kład, wierzchołki grafu są miejscowościami i długość krawędzi jest odległością miejsco-
wości. Chcemy teraz skonstruować minimalne drzewo spinające, czyli drzewo spinające
T = (V, ET ) z minimalną sumą długości krawędzi
w(e).
e"ET
Algorytm budowy minimalnego drzewa spinajÄ…cego
Dane wejściowe: graf G = (V, E) z funkcją wagi w : E R.
Dane wyjściowe: minimalne drzewo spinające T = (V, ET ).
1.9. Minimalne drzewo spinajÄ…ce 15
ET := ";
Posortuj krawędzie E grafu G według długości, od najkrótszej do najdłuższej.
Dla każdej krawędzi e " E
wstaw e do ET pod warunkiem, że nie tworzy cyklu z krawędziami, które już są w ET .
Przykład 1.25 Po zastosowaniu powyższego algorytmu do grafu z rysunku 1.8a otrzyma-
my drzewo przedstawione na rysunku 1.8b
Rysunek 1.8: a) Graf z wagami, b) Jego minimalne drzewo spinajÄ…ce
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)
Najpierw pokażemy, że tak utworzony graf T jest drzewem spinającym. Po każdej
iteracji pętli, graf T nie zawiera cyklu, więc na końcu też jest acykliczny. Przypuśćmy,
że po zakończeniu algorytmu T nie jest spójny. Istnieją więc w G dwa wierzchołki x i y,
które są połączone w G drogą x = x1 . . . , xk = y (bo G jest spójny), ale które nie są
połączone w T . Na drodze tej są więc dwa sąsiednie wierzchołki xi i xi+1, które nie są
połączone w T drogą. Ale wtedy dodanie krawędzi {xi, xi+1} do drzewa T nie tworzy w
nim cyklu i algorytm powinien dodać krawędż {xi, xi+1} do T , sprzeczność.
Pokażemy teraz, że T jest minimalnym drzewem spinającym. Przypuśćmy, że T nie
jest minimalne. Niech S = (V, ES) będzie takim minimalnym drzewem, które ma z T
największą liczbę wspolnych krawędzi. Niech e będzie krawędzią z minimalną wagą,
która należy do T , ale nie należy do S. Jeżeli dodamy e do S to otrzymamy cykl. Niech
f będzie krawędzią w tym cyklu, która należy do S, ale nie należy do T .
Niech S będzie drzewem, które powstaje z S po zamianie f na e. S powstaje przez
usunięcie f z grafu (V, ES *" {e}). Jest to graf spójny z n - 1 krawędziami, czyli drzewo.
Jeżeli w(e) < w(f), to drzewo S byłoby drzewem z mniejszą od S wagą, wbrew mi-
nimalności S. Jeżeli w(e) = w(f), to drzewo S byłoby minimalnym drzewem z większą
od S liczbą wspolnych z T krawędzi, znowu sprzeczność. Mamy więc w(e) > w(f).
Jeżeli dodamy teraz krawędz
f do T , to otrzymamy cykl (to może być inny cykl
niż ten w (V, ES *" {e}). W tym cyklu istnieje krawędz
e , która należy do T , ale nie
do S. Przypuśćmy, że w(f) < w(e ). W takim przypadku algorytm powinien wstawić
16 Rozdział 1. Grafy (nieskierowane)
krawędz
f do drzewa T , bo w momencie rozpatrywania f w drzewie nie ma jeszcze e
i wstawienie f nie zamyka cyklu. Wynika, to z faktu, że graf (V, ET *" {f} - {e }) jest
drzewem, więc krawędz
f nie tworzy cyklu z krawędziami z ET - {e }. Mamy więc
w(e ) d" w(f) < w(e) co jest sprzeczne z faktem, że e była najlżejszą krawędzią z T i
nienależącą do S.
1.10 Cykle i drogi Eulera
Droga Eulera to droga, która przechodzi przez każdą krawędz
grafu dokładnie jeden raz.
Cykl Eulera to taka droga zamknięta, w której każda krawędz
grafu występuje dokładnie
raz.
Euler w 18. wieku pokazał, że istnieje dość prosta charakteryzacja grafów z drogą
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 drogę Eulera jeżeli co najwyżej
dwa jego wierzchołki są stopnia nieparzystego. Pamiętamy, lemat 1.2, że w każdym grafie
liczba wierzchołków nieparzystego stopnia jest parzysta. Tak więc graf z drogą Eulera ma
dwa lub zero wierzchołków nieparzystego stopnia.
Przykład 1.26 W grafie z rysunku 1.1 wszystkie wierzchołki są parzystego stopnia i po-
siada o cykl Eulera a, b, e, a, c, b, a, d, f, g, c, d, a.
Wyobrażmy sobie, że idziemy wzdłuż krawędzi grafu, i po przejściu każdej krawędzi
usuwamy ją z grafu. Przechodząc przez jakiś wierzchołek usuwamy dwie krawędzie, tą,
którą weszliśmy do wierzchołka, i tą, którą go opuściliśmy. Dlatego, jeżeli po dojściu do
jakiegoś wierzchołka, nie ma już krawędzi z niego odchodżących, to albo doszliśmy do
wierzchołka początkowego, albo do wierzchołka nieparzystego stopnia.
Z tego wynika, że jeżeli w grafie istnieje droga Eulera, to mogą w nim być co najwyżej
dwa wierzchołki nieparzystego stopnia, początek i koniec drogi, a jeżeli droga Eulera jest
zamknięta i stanowi cykl Eulera, to wszystkie wierzchołki w grafie są parzystego stopnia.
Pokażemy teraz, że są to także warunki wystarczające. Zaczniemy od cyklu Eulera.
Twierdzenie 1.27 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 wystarczający. Założmy, że każdy wierzchołek jest parzystego stopnia. Niech C
będzie najdłuższą pod względem liczby krawędzi drogą w grafie bez powtarzania krawę-
dzi. Z rozważań zrobionych wyżej wynika, że jest to droga zamknięta. Przypuśćmy, że
droga ta nie zawiera jeszcze wszystkich krawędzi grafu. Ponieważ graf jest spójny, więć
istnieje wierzchołek v na tej drodze, od którego odchodzi krawędz
e nie należąca do C.
Możemy teraz utworzyć dłuższą drogę bez powtarzania krawędzi: zawiera ona e i potem
idzie wzdłuż C. Jest to sprzeczne z założeniem, że C była najdłuższą drogą.
Twierdzenie 1.28 spójny graf posiada drogę Eulera wtedy i tylko wtedy, gdy posiada co
najwyżej dwa wierzchołki nieparzystego stopnia.
1.10. Cykle i drogi Eulera 17
Dowód: Konieczność warunku pokazano wyżej. Teraz pokażemy, że jest to warunek wy-
starczający. Ponieważ graf nie może posiadać tylko jednego wierzchołka stopnia niepa-
rzystego, to wystarczy rozważyć graf z dwoma wierzchołkami u i v nieparzystego stopnia.
Dodajmy do grafu nowy wierzchołek z i połączmy go krawędziami z u i v. Teraz każdy
wierzchołek jest stopnia parzystego i posiada cykl Eulera. Po usunięciu z niego nowych
krawędzi i wierzchołka z otrzymamy drogę Eulera w pierwotnym grafie.
Powyższy dowód, chociaż krótki, ma tę wadę, że nie daje dobrego algorytmu znaj-
dowania drogi Eulera. Nie sposob przeglądąć wszystkich możliwych drog, 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 G ze wszystkimi wierzchołkami parzystego stopnia.
Zaczynamy od dowolnego wierzchołka v0.
Powtarzamy, aż do wyczerpania krawędzi:
Jeżeli z bierzącego wierzchołka v nie odchodzi żadna krawędz
, to
koniec algorytmu.
Jeżeli z bierzącego wierzchołka v odchodzi tylko jedna krawędz
, to
przechodzimy wzdłuż tej krawędzi do następnego wierzchołka,
usuwamy tą krawędz
i wierzchołek v z grafu.
Jeżeli z v odchodzi więcej niż jedna krawędz
, to
wybieramy tą krawędz
, której usunięcie nie rozspójnia grafu;
przechodzimy wzdłuż tej krawędzi do następnego wierzchołka,
usuwamy tą krawędz
z grafu.
Rysunek 1.9: Przykład grafu z cyklem Eulera
a c
b
h d i
g
e f
Przykład 1.29 W grafie z rysunku 1.9 wszystkie wierzchołki są parzystego stopnia. Prze-
śledz
my, jak działa powyższy algorytm. Zaczynamy od wierzchołka a i przyjmijmy, że w
18 Rozdział 1. Grafy (nieskierowane)
razie wyboru algorytm wybierze krawędz
do wierzchołka z wcześniejszą (według alfabe-
tu) literą. Tak więc a przejdzie do b potem do c i do d. Rysunek 1.10 przedstawia nasz graf
po tych trzech krokach, usunięciu odwiedzanych krawędzi i wierzchołka c (z którego nie
odchodzą już żadne krawędzie).
Rysunek 1.10: Graf po przejściu trzech krawędzi
a
b
h d i
g
e f
Teraz algorytm nie może wybrać krawędzi {d, a} ponieważ usunięcie tej krawędzi roz-
spójni graf. Zamiast tego algorytm powinien wybrać krawędz
{d, e} i przejść do wierz-
chołka e, a potem do f. Teraz znowu nie powinien iść do g tylko do h, a potem już bez
problemów do końca cyklu Eulera: b, i, f, g, d, a.
Pokażemy teraz poprawność tego algorytmu. Przypuśćmy, że po kilku krokach je-
steśmy w wierzchołku v, z którego odchodzi kilka krawędzi. Pokażemy, że wśrod tych
krawędzi co najwyżej jedna jest zła (jej usunięcie może rozspójnić graf). Z przebiegu al-
gorytmu wynika, że graf w aktualnej postaci (po usunięciu być może jakiś krawędzi lub
wierzchołków) jest nadal spójny i co najwyżej dwa wierzchołki w nim są nieparzystego
stopnia v i v0 (co zachodzi jeżeli v = v0). Więc posiada on drogę Eulera. Idżmy tą drogą

zaczynając od v. Droga ta kończy się w v lub v0 i przechodzi kilka razy przez v. Mamy
więc kilka pętli, które zaczynają się i kończą w v i być może końcowy odcinek zaczyna-
jący się w v i kończący w v0. Otoż tylko pierwsza krawędż tego ostatniego odcinka może
rozspójniać graf. Wszystkie inne krawędzie wychodzące z v są częściami cykli.
Aby udowodnić, że algorytm dobrze działa, trzeba pokazać, że wszystkie krawędzie
grafu będą odwiedzone. Po każdej iteracji algorytmu graf jest spójny, więc jeżeli z wierz-
chołka v nie odchodzą żadne krawędzie, to znaczy, że nie ma już żadnych krawędzi w
grafie.
Powyższy algorytm mimo, że prosty i szybki wymaga sprawdzania, czy usunięcie
krawędzi nie rozspójni grafu.
1.11. Drogi i cykle Hamiltona 19
1.11 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 zamknięta droga Hamiltona.
Przykład 1.30 Graf z rysunku 1.2 posiada cykl Hamiltona a, b, c, d, e, f, a. Każdy graf
pełny Kn z n e" 3 posiada cykl Hamiltona.
Inaczej niż dla cyklu lub drogi Eulera nie jest znane żadne proste kryterium rozstrzy-
gania, czy dany graf posiada drogę lub cykl Hamiltona. Nie jest także znany żaden al-
gorytm wyszukiwania drogi lub cyklu Hamiltona działający w czasie wielomianowym.
Naiwnym sposobem szukania drogi Hamiltona jest sprawdzanie wszystkich możliwych
drog w grafie, ale algorytm ten jest bardzo czasochłonny, bo mamy około n! możliwych
drog w grafie z n wierzchołkami. Innym algorytmem szukania drogi Hamiltona jest tak
zwane wyszukiwanie z nawrotami, które idzie pierwszą możliwą ścieżką tak daleko jak
to tylko możliwe okładając kolejne odwiedzane wierzchołki na stos. W momencie, gdy
algorytrm utknie w ślepej uliczce, to cofa się o jeden krok i probuje innej drogi. Algorytm
z nawrotami mimo, że trochę szybszy od naiwnego sprawdzania wszystkich drog, ma
wykładniczą złożoność czasową. Założmy, że wierzchołki grafu są kolejnymi liczbami
naturalnymi V = {1, . . . , n}
Algorytm z nawrotami wyszukiwania drogi Hamiltona
Dane wejściowe: graf G = (V, E) oraz wierzchołek początkowy v " V .
Dane wyjściowe: droga Hamiltona zaczynająca się od v, lub informacja, że takiej drogi
nie ma.
włoż v na STOS
Dopóki STOS nie jest pusty powtarzaj:
Niech u będzie wierzchołkiem na wierzchu STOSU,
szukamy wierzchołka w o najniższym numerze takiego że:
w jest połączone z u
w nie występujący na STOSIE.
Jeżeli w poprzedniej iteracji zdjęto ze STOSU wierzchołek x, to
numer w powinien być większy od numeru x.
Jeżeli takie w znajdziemy, to
wkładamy w na STOS.
Jeżeli wierzchołki na STOSIE tworzą już drogę Hamiltona, to
koniec algorytmu; znaleziono drogÄ™ Hamiltona.
Jeżeli takiego w nie znajdziemy, to
zdejmujemy u ze STOSU.
Jeżeli STOS jest pusty i nie znaleziono dotąd drogi Hamiltona, to
W grafie nie ma drogi Hamiltona.
Przykład 1.31 Prześledz
my 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 a). Algorytm stwierdza, że w grafie nie ma
drogi Hamiltona.
20 Rozdział 1. Grafy (nieskierowane)
Krok wierzchołek STOS
1 a a
2 b ab
3 c abc
4 d abcd
5 c abc
6 g abcg
7 f abcgf
8 c abc
9 b ab
10 e abe
11 b ab
12 a a
1.12 Kolorowanie grafów
Chodzi o takie pokolorowanie wierzchołków grafu, żeby wierzchołki połączone krawę-
dzią były pokolorowane innymi kolorami i żeby liczba kolorów była jak najmniejsza.
Definicja 1.32 Pokolorowanie grafu G = (V, E) k kolorami jest to funkcja c : V
{1, . . . , k}, taka że c(u) = c(v) jeżeli {u, v} " E.

Najmniejsze takie k, że graf G można pokolorować k kolorami nazywamy liczbą chro-
matycznÄ… grafu G i oznaczamy przez Ç(G).
1.12.1 Kolorowanie z nawrotami
W przypadku kolorowania grafów, podobnie jak dla drog Hamiltona, nie są znane dobre
i szybkie algorytmy. Także tu mamy algorytm z nawrotami.
Algorytm z nawrotami kolorowania wierzchołków grafu
Dane wejściowe: graf G = (V, E) oraz liczba naturalna k.
Dane wyjściowe: pokolorowanie wierzchołków grafu G za pomocą k kolorów c : V
{1, . . . , k} lub informacja, że takiego pokolorowania nie ma.
dla każdego v " V
podstaw c(v) := 0 (c(u) = 0 oznacza, że u nie ma jeszcze koloru).
włoż pierwszy wierzchołek na STOS,
Dopóki STOS nie jest pusty wykonuj:
Niech u będzie wierzchołkiem na wierzchu STOSU,
probujemy przypisać wierzchołkowi u kolor, który
jest większy od bieżącego koloru c(u),
nie koliduje z kolorami wierzchołków znajdujących się na STOSIE.
Jeżeli uda się pokolorować u, to
Sprawdzamy, czy pokolorowano już wszystkie wierzchołki
Jeżeli tak, to
1.12. Kolorowanie grafów 21
Koniec, znaleziono kolorowanie;
Jeżeli nie, to
wkładamy kolejny wierzchołek na stos.
Jeżeli nie uda się pokolorować u, to
zdejmujemy u ze stosu i podstawiamy c(u) := 0.
Jeżeli STOS pusty i nie znaleziono dotąd kolorowania, to
grafu nie można pokolorować k kolorami.
W tym algorytmie probujemy kolejnym wierzchołkom przypisać pierwszy z rzędu
kolor i pokolorowane wierzchołki umieszczamy na stosie. Jak zabrniemy w ślepą uliczkę,
to cofamy się do poprzedniego wierzchołka na stosie i probujemy następnego koloru.
Przykład 1.33 Zastosujmy powyżwszy algorytm do grafu z rysunku 1.11, aby znalez
ć
kolorowanie trzema kolorami {1, 2, 3}. Najpierw każdy wierzchołek dostaje kolor 0, co
oznacza, że nie jest jeszcze pokolorowany.
Rysunek 1.11: Przykład grafu
f a
b
e c
d
Zaczynamy od wierzchołka a. W pierwszych pięciu krokach algorytm pokoloruje wierz-
chołki a, b, c, d i e w następujący sposob:
u a b c d e f
c(u) 1 2 1 2 3 0
a na stosie mamy wierzchołki
ST OS = abcdef.
Teraz algorytm nie może pokolorować wierzchołka f, bo jest on połączony z a, d, e, które
są pokolorowane kolorami 1, 2, 3. Dlatego f jest zdjęte ze stosu:
ST OS = abcde.
Teraz zdejmujemy wierzchołek e, bo nie można mu przypisać wyższego koloru, i podsta-
wiamy c(e) := 0.
ST OS = abcd.
Teraz zmieniamy kolor d na c(d) = 3, a następnie kolorujemy c(e) := 2 i wkładamy f na
stos.
22 Rozdział 1. Grafy (nieskierowane)
u a b c d e f
c(u) 1 2 1 3 2 0
ST OS = abcdef.
W tym momencie pokolorowanie f nie jest możliwe, więc zdejmujemy go ze stosu
ST OS = abcde.
Wierzchołek e też nie może być pokolorowany wyższym kolorem, więc też go zdejmujemy.
ST OS = abcd.
Wierzchołek d ma w tym momencie najwyższy kolor c(d) = 3, więc zmiana koloru nie jest
możliwa i zdejmujemy go ze stosu. Mamy teraz następujące kolorowanie
u a b c d e f
c(u) 1 2 1 0 0 0
i stos
ST OS = abc.
Teraz zmieniamy kolor c na c(c) := 3, a następnie już bez nawrotów kolorujemy c(d) :=
1, c(e) := 2, c(f) := 3. Ostateczne kolorowanie wyglÄ…da 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 Kn n - 1 ko-
lorami, to wyprobuje on wszystkie (n-1)! kolorowań dla pierwszych n-1 wierzchołków.
Pesymistyczny czas działania algorytmu jest więc &!(2n).
1.12.2 Kolorowanie grafu dwoma kolorami
Problem kolorowania grafów jest trywialny, jeżeli mamy tylko jeden kolor k = 1. Jed-
nym kolorem można pokolorować tylko grafy bez krawędzi. 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 niepa-
rzystej długości. Poniżej pokażemy, że i na odwrot: jeżeli graf nie ma cyklu nieparzy-
stej długości, to można go pokolorować dwoma kolorami. Przedstawiamy teraz algorytm
kolorowania grafów dwoma kolorami. Dla prostoty zakładamy, że kolorowane grafy są
spójne. Algorytm można łatwo przerobić tak, aby kolorował wszystkie grafy.
Algorytm kolorowania grafu dwoma kolorami
Dane wejściowe: spójny graf G = (V, E).
Dane wyjściowe: pokolorowanie wierzchołków grafu G za pomocą dwóch kolorów c :
V {1, 2} lub informacja, że takiego pokolorowania nie ma.
1.12. Kolorowanie grafów 23
wez
pierwszy wierzchołek v, pokoloruj go pierwszym kolorem c(v) := 1.
powtarzaj aż do skutku:
Wez
wszystkie niepokolorowane jeszcze wierzchołki, które
są połączone z jakimś wierzchołkiem pokolorowanym w poprzedniej iteracji
Jeżeli wśrod nich żadne dwa nie są połączone krawędzią, to
pokoloruj je jednym kolorem (innym niż w poprzedniej iteracji).
Jeżeli wśrod nich są dwa połączone krawędzią, to
pokolorowanie dwoma kolorami nie jest możliwe.
Kolorowanie otrzymywane w tym algorytmie jest prawidłowe. Niech Wi oznacza
wierzchołki kolorowane w i-tej iteracji, W0 = {v}. Wierzchołki z Wi są kolorowane na
pierwszy kolor, jeżeli i jest parzyste, i na drugi kolor, jeżeli jest nieparzyste. Zauważmy,
że dowolny wierzchołek u " Wi może być połączony krawędzią tylko z wierzchołka-
mi ze zbiorów Wi-1 i Wi+1. Wi+1 zawiera wszystkie wierzchołki, które są połączone z
wierzchołkami z Wi i nie miały koloru po pokolorowaniu Wi, tak więc żaden ze zbiorów
Wj z j > i + 1 nie zawiera wierzchołków połączonych z Wi.
Zauważmy, że jeżeli dwa wierzchołki u i w należa do Wi, to istnieją drogi v =
u0, u1, . . . , ui = u oraz v = w0, w1, . . . , wi = w takie, że uj, wj " Wj. Niech uk =
wk, będzie ostatnim wspolnym wierzchołkiem na obu drogach. Ponieważ zbiory Wj
są rozłączne, to wspolne wierzchołki muszą mieć te same indeksy. Droga u, . . . , uk =
wk, . . . , w jest drogą z parzystą liczbą krawędzi. Dlatego, jeżeli u i v są połączone kra-
wędzią, 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.34 Graf jest dwudzielny (może być pokolorowany dwoma kolorami) wtedy i tyl-
ko wtedy, gdy nie zawiera cykli nieparzystej długości.
Wniosek 1.35 Każde drzewo można pokolorować dwoma kolorami.
Nie jest znany algorytm kolorujący grafy trzema kolorami (lub dowolną większą licz-
bą kolorów) działający w czasie wielomianowym.
1.12.3 Heurystyki kolorowania grafów
Ponieważ nie są znane szybkie algorytmy kolorowania grafów stosuje się heurystyki, czy-
li algorytmy niedokładne. Na przykład następująca heurystyka
Heurystyka kolorowania grafu według stopni
Posortuj wierzchołki grafu według stopni, od największego do najmniejszego.
Dla każdego wierzchołka po kolei
przypisz mu najniższy możliwy kolor.
W wielu przypadkach heurystyka ta da optymalne rozwiązanie, na przykład dla grafu
z rysunku 1.11.
24 Rozdział 1. Grafy (nieskierowane)
1.13 Hiperkostka
Rysunek 1.12: a) Hiperkostka H1, b) Hiperkostka H2
01 11
1
0 00 10
a) b)
Hiperkostka H1 wymiaru 1 jest przedstawiona na rysunku 1.12a. Składa się ona z
dwóch wierzchołków 0 i 1 połączonych krawędzią. Hiperkostkę H2 wymiaru 2 (rysu-
nek 1.12b) budujemy z dwóch kostek H1. W pierwszej kostce numerujemy wierzchołki
przez 00 i 01 (dopisujemy 0 na początek nazwy każdego wierzchołka). W drugiej kostce
numerujemy wierzchołki przez 10 i 11 (dopisujemy 1 na początek). Następnie łączymy
krawędziami odpowiadające sobie wierzchołki z obu kopii 00 z 10 i 01 z 11.
Rysunek 1.13: Hiperkostka H3
001 011
101 111
100 110
000 010
1.13. Hiperkostka 25
Podobnie budujemy hiperkostkę Hk wymiaru k z dwóch kostek Hk-1. W pierwszej
kostce numerujemy wierzchołki dopisując 0 na początku nazwy każdego wierzchołka.
W drugiej kostce numerujemy wierzchołki dopisując 1 na początek. Następnie łączy-
my krawędziami odpowiadające sobie wierzchołki z obu kopii, czyli wierzchołek 0x jest
połączony z wierzchołkiem 1x, dla każdego x " {0, 1}k-1. Rysunek 1.13 przedstawia
hiperkostkÄ™ H3.
W rezultacie hiperkostka to graf Hk = (V, E), gdzie V = {0, 1}k zawiera wszystkie
ciągi bitów długości k, a dwa wierzchołki u, v " V są połączone krawędzią wtedy i tylko
wtedy, gdy różnią się dokładnie jednym bitem.
Jak łatwo widać w kostkach H2 i H3 są cykle Hamiltona (w H1 jest droga Hamiltona).
Ogolniej mamy
Lemat 1.36 Każda hiperkostka Hk zawiera drogę Hamiltona. zaczynającą się w wierz-
chołku 0k i kończącą w wierzchołku 10k-1.
Dowód przez indukcję ze względu na wymiar kostki. H1 zawiera drogę Hamiltona 0, 1
Założmy, że Hk-1 zawiera drogę Hamiltona z 0k-1 do 10k-2. Hk składa się z dwóch
hiperkostek Hk-1. Droga w Hk zaczyna siÄ™ w punkcie 0k. W pierszej hiperkostce (tej z 0
na początku każdego wierzchołka) przechodzi do 010k-2, potem krawędzią do 110k-2 i
w drugiej hiperkostce (tej z 1 na początku każdego wierzchołka) w odwrotnym kierunku
do 10k-1.
Cykl Hamiltona w Hk tworzy tak zwany kod Graya. Jest to ciÄ…g wszyskich k elemen-
towych ciągów bitów, każdy występuje raz, każde dwa kolejne różnią się jednym bitem
oraz ostatni ciąg różni się jednym bitem od pierwszego.
1.13.1 Rozgłaszanie wiadomości
Graf G = (V, E) może przedstawiać sieć połączeń. Wierzchołki są agentami, a krawędzie
to łącza, którymi agenci mogą się komunikować. Wyobraz
my sobie, że jeden agent posia-
da jakąś wiadomość, którą chce przekazać wszystkim innym agentom w sieci. Reguły są
następujące. Komunikacja odbywa się synchronicznie w taktach. W każdym takcie każdy
agent może przekazać wiadomość jednemu swojemu sąsiadowi.
Powyższy problem nazywa się problemem rozgłaszania. Poniżej pokażemy, że można
go bardzo efektywnie rozwiązać, jeżeli graf jest hiperkostką Hk. Będziemy traktować
ciąg bitów jako przedstawienie dwójkowe liczby naturalnej.
Najpierw prześledz
my działanie tego protokółu na hiperkostce H3 (rysunek 1.13).
Założmy, że wierzchołek 0 = 000 jest żrodłem wiadomości. W pierwszym takcie przeka-
zuje on ją do wierzchołka 1 = 001. Zauważmy, że po pierwszym takcie wiadomość jest
znana wierzchołkom o numerach mniejszych od 2 i, że te wierzchołki tworzą hiperkostkę
wymiaru 1. W drugim takcie wierzchołek 0 = 000 przekaże wiadomość do wierzchoł-
ka 2 = 010, a wierzchołek 1 = 001 do 3 = 011. Po drugim takcie wiadomość znają
wierzchołki o numerach mniejszych od 4 i tworzą one hiperkostkę wymiaru 2. W trzecim
takcie 0 = 000 przekazuje wiadomość do 4 = 100, 1 = 001 do 5 = 101, 2 = 010 do
6 = 110, a 3 = 011 do 7 = 111. Tak więc po trzech taktach wszystkie wierzchołki w H3
znają wiadomość.
26 Rozdział 1. Grafy (nieskierowane)
Protokół rozsyłania wiadomości w hiperkostce Hk
Na początku wiadomość ma wierzchołek 0 = 0k.
Dla każdego i od 1 do k, wykonuj:
każdy wierzchołek x < 2i-1 przekazuje wiadomość do wierzchołka x + 2i-1.
Aby pokazać poprawność tego protokołu, pokażemy przez indukcje, że po i-tym
takcie wiadomość jest znana wszystkim wierzchołkom o numerach mniejszych od 2i.
Przed pierwszym taktem wiadomość jest znana wierzchołkom o numerach mniejszych
od 20 = 1, czyli wierzchołkowi 0. Założmy, że przed i-tym taktem wiadomość jest znana
wszystkim wierzchołkom o numerach mniejszych od 2i-1. Są to dokładnie wierzchołki
postaci x = 0k-i+1Ã, gdzie à " {0, 1}i-1 (jeżeli i = 1 to à jest pustym ciÄ…giem). W
i-tym takcie każdy taki wierzchoÅ‚ek przekaże wiadomość do x+2i-1 = 0k-i1Ã, czyli po
i-tym takcie wiadomość będą znały wszystkie wierzchołki, które mają na k-i pierwszych
bitach zera, czyli wszystkie wierzchołki o numerach mniejszych od 2i.
Protokół ten (po małych przerobkach) można także stosować do grafu pełnego lub do
innego grafu, który zawiera hiperkostkę.
1.13.2 Zbieranie informacji
Hiperkostka jest także wygodną strukturą do zbierania informacji, gdy chcemy do jed-
nego wierzchołka zebrać informacje od wszystkich wierzchołków. Informacje te należy
przesyłąć w odwrotnym kierunku niż w protkole rozsyłania. Zakładamy, że przesyłane
informacje są łączone w pakiety i wierzchołek może przesłać w jednym takcie cały pakiet
zawierajÄ…cy kilka informacji.
Protokół zbierania wiadomości w hiperkostce Hk
Dla każdego i od 1 do k, wykonuj:
każdy wierzchoÅ‚ek postaci x = 0i-11Ã, gdzie à " {0, 1}k-i
przesyÅ‚a swoj pakiet do wierzchoÅ‚ka 0i-10Ã,
Przykład 1.37 Prześledz
my działanie tego protokułu na hiperkostce H3 (rysunek 1.13).
W pierwszym takcie wierzchołek 100 przekazuje swoją wiadomość do 000, wierzchołek
101 do 001, wierzchołek 110 do 010, a wierzchołek 111 do 011.
W drugim takcie wierzchołek 010 przekazuje zebrane wiadomości (swoją i te, kt.ore
otrzymał w poprzednim takcie) do 000, a wierzchołek 011 do 001.
W trzecim takcie wierzchołek 001 przekazuje zebrane wiadomości do 000. a wierz-
chołek 011 do 001.
1.13.3 Plotkowanie
Plotkowanie polega na tym, że na początku każdy wierzchołek ma jakąś wiadomość i
chce ją rozesłać do wszystkich innych wierzchołków w grafie.
Znając protokoły do zbierania i rozsyłania wiadomości możemy zaprojektować pro-
tokół plotkowania, który najpierw zbiera wszystkie informacje do jednego węzła, a na-
stępnie rozsyła je do wszystkich wierzchołków.
1.14. Zadania 27
1.14 Zadania
1. Narysuj graf G = (V, E), gdzie:
a) V = {a, b, c, d, e, f} oraz E = {{a, d}, {a, f}, {b, c}, {b, e}, {c, f}, {d, e}}
b) V = {1, 2, 3, 4, 5, 6, 7} oraz E = {{1, 3}, {2, 4}, {2, 6}, {3, 5}, {3, 7}, {4, 6}{5, 7}}.
2. Ile krawędzi ma graf pełny Kn?
3. Ile maksymalnie krawędzi może mieć graf z n wierzchołkami?
4. Ile jest grafów ze zbiorem wierzchołków {1, . . . , n}?
5. Ile krawędzi ma dwudzielny graf pełny Km,n?
6. Udowodnij, że izomorfizm grafów jest relacją równoważności.
7. Narysuj wszystkie grafy ze zbiorem wierzchołków V = {a, b, c}. które z nich są
izomorficzne?
8. Narysuj dwa izomorficzne grafy z czteroma (pięcioma) wierzchołkami, wskaż izo-
morfizm pomiędzy nimi.
9. Wypisz jak najdłuższą drogę prostą w grafie z rysunku 1.2.
10. Udowodnij, że w każdym grafie są dwa wierzchołki tego samego stopnia.
11. Narysuj możliwie jak najwięcej nieizomorficznych grafów z czterema wierzchoł-
kami {a, b, c, d}.
12. Narysuj dwa (możliwie jak najmniejsze) nieizomorficzne grafy: a) z tą samą licz-
bą wierzchołków; b) z tą samą liczbą wierzchołków i tą samą liczbą krawędzi; c)
które mają tą samą liczbą wierzchołków stopnia k, dla każdego k.
13. Narysuj dwa nieizomorficzne drzewa z tą samą (możliwie jak najmniejszą) liczbą
wierzchołków.
14. Czy istnieje graf z n wierzchołkami, który: a) ma n - 1 krawędzi i nie jest drze-
wem, b) ma mniej niż n - 1 krawędzi i jest spójny, c) ma więcej niż n - 1
krawędzi i nie jest spójny, d) ma więcej niż n - 1 krawędzi i nie ma cyklu, e)
ma mniej niż n - 1 krawędzi i posiada cykl.
15. Zastosuj algorytm przeszukiwania grafu w głąb (wszerz) do grafu z rysunku 1.9.
16. Skonstruj drzewo spinajÄ…ce dla grafu z rysunku 1.9.
17. KorzystajÄ…c z drzew spinajÄ…cych z poprzedniego zadania, znajdz
zbior cykli funda-
mentalnych dla grafów.
28 Rozdział 1. Grafy (nieskierowane)
18. Dany jest graf G = (V, E) gdzie
V = {a, b, c, d, e, f, g, h} oraz
E = {{a, b}, {a, c}, {a, e}, {a, g}, {a, h}, {b, c}, {b, d}, {e, f}, {e, g}, {f, g}, }.
Bez rysowania grafu zastosuj algorytm konstruowania drzewa spinajÄ…cego przy
przeszukiwaniu w głąb oraz algorytm przeszukiwania grafu wszerz.
19. Dany jest graf G = (V, E) gdzie
V = {a, b, c, d, e, f, g, h} oraz
E = {{a, d}, {b, g}, {c, e}, {c, h}, {d, g}, }.
Bez rysowania grafu zastosuj algorytm liczenia składowych spójności. Czy graf G
posiada cykl?
20. Udowodnij, że jeżeli stopień każdego wierzchołka v w grafie G spełnia warunek
n-1
d(v) e" , to graf G jest spójny.
2
21. Sprawdz
, które grafy przedstawione na rysunkach w tym rozdziale posiadają cykl
(lub drogÄ™) Eulera. Zastosuj algorytmy opisany w tym rozdziale do wyznaczania
takich dróg.
22. Sprawdz
, które grafy przedstawione na rysunkach w tym rozdziale posiadają cykl
lub drogÄ™ Hamiltona.
23. Dla jakiego n graf pełny Kn posiada (a) cykl Eulera, (b) cykl Hamiltona.
24. Dla jakich m i n dwudzielny graf pełny Km,n posiada (a) cykl Eulera, (b)
cykl Hamiltona.
25. Dla jakiego n graf pełny Kn z usuniętą jedną krawędzią posiada (a) drogę
Eulera, (b) drogÄ™ Hamiltona, (c) cykl Eulera, (d) cykl Hamiltona.
26. Udowodnij, że jeżeli stopień każdego wierzchołka v w grafie G spełnia warunek
n
d(v) e" , to graf G posiada cykl Hamiltona.
2
27. Zastosuj algorytm kolorowania z nawrotami do grafu z rysunku 1.1.
28. Które z grafów przedstawionych na rysunkach w tym rozdziale mogą być pokolo-
rowane dwoma kolorami.
29. Zastosuj heurystykę kolorowania grafu według stopni do grafów z rysunku 1.3. Czy
otrzymana liczba kolorów jest optymalna?
30. Jaka jest liczba chromatyczna: (a) grafu pełnego Kn (b) grafu pełnego Kn z
usuniętą jedną krawędzią?
31. Znajdz
graf, dla którego heurystyka kolorowania według stopini, przedstawiona w
podrozdziale o kolorowaniu grafów, nie znajduje optymalnego kolorowania.
1.15. Problemy 29
32. Udowodnij, że dla każdego grafu G jego liczba chromatyczna spełnia nierówność
Ç(G) d" "(G)+1, gdzie "(G) oznacza maksymalny stopieÅ„ wierzchoÅ‚ka w grafie
G. Podaj przykÅ‚ad grafu, dla którego zachodzi równość Ç(G) = "(G) + 1.
33. Narysuj hiperkostkę H4. Wskaż w niej cykl Hamiltona. Prześledz
na niej protokół
rozsyłania wiadomości.
1.15 Problemy
1.15.1 Drzewa spianajÄ…ce
Zmodyfikuj algorytm przeszukiwania grafu wszerz tak, aby wyznaczał on także drzewo
spinające (złożone z tych krawędzi, którymi przeszedł algorytm). Zastosuj ten algorytm
do grafów z rysunków 1.1 i 1.9.
Niech G = (V, E) będzie grafem, a Tw drzewem spinającym powstałym przy prze-
szukiwaniu wszerz grafu G. Niech v0 " V będzie korzeniem tego drzewa, czyli wierz-
chołkiem, z którego startuje przeszukanie. Udowodnij, że dla dowolnego wierzchołka
v " V najkrótsza droga od v do v0 w drzewie Tw jest także najkrótszą drogą z v do v0 w
całym grafie G.
Niech Tg będzie drzewem spinającym powstałym przy przeszukiwaniu w głąb grafu
G = (V, E). Udowodnij, że dla każdej pary wierzchołków u, v połączonych krawędzią
{u, v} " E w grafie G, albo u jest potomkiem v, albo v jest potomkiem u w drzewie Tg.
1.15.2 Grafy dwuspójne
Wierzchołek v grafu spójnego G = (V, E) nazywamy punktem artykulacji, jeżeli jego
usunięcie (z przyległymi krawędziami) rozspójnia graf. Istnieją wtedy dwa różne od niego
wierzchołki u i w, takie, że każda droga z u do w przechodzi przez v. Graf spójny bez
punktów artykulacji nazywamy dwuspójnym. Które grafy przedstawione na rysunkach w
tym rozdziale nie są dwuspójne? Udowodnij następujący:
Lemat 1.38 Niech Tg będzie drzewem spinającym powstałym przy przeszukiwaniu w
głąb grafu G = (V, E) i niech r będzie jego korzeniem. Wówczas korzeń r jest punk-
tem artykulacji wtedy i tylko wtedy, gdy ma w drzewie Tg co najmniej dwóch synów, a
wierzchołek v = r jest punktem artykulacji wtedy i tylko wtedy, gdy istnieje syn w wierz-

chołka v taki, że ani w ani żaden jego potomek nie jest połączony krawędzią z żadnym
przodkiem v.
1.15.3 Skojarzenia
Skojarzeniem nazywamy dowolny zbiór parami rozłącznych krawędzi. Niech graf G =
(V, E) będzie grafem dwudzielnym z podziałem V = V1 *" V2 takim, że: V1 )" V2 = ",
n
|V1| = |V2| = oraz krawędzie są tylko pomiędzy V1 i V2. W takim grafie skojarze-
2
n
nie nazywamy doskonałym jeżeli zawiera krawędzi. Wtedy każdy wierzchołek z V1
2
30 Rozdział 1. Grafy (nieskierowane)
jest skojarzony z jednym wierzchołkiem z V2 i na odwrót każdy wierzchołek z V2 jest
skojarzony z jednym wierzchoÅ‚kiem z V1. Dla dowolnego zbioru C ‚" V1 niech
N(C) = {u " V2 | "v"C {u, v} " E}.
N(C) zawiera wszystkich sąsiadów wierzchołków z C.
Udowodnij, że w grafie G istnieje doskonałe skojarzenie wtedy i tylko wtedy, gdy dla
każdego zbioru C ‚" V1 zachodzi |N(C)| e" |C|.
Wskazówka Skorzystaj z twierdzenia Halla o reprezentantach.
1.15.4 Minimalne drzewo spinajÄ…ce
Oto algorytm konstrukcji minimalnego drzewa spinajÄ…cego T = (V, ET ) dla grafu G =
(V, E):
zaczynamy od zbioru wszystkich krawędzi ET := E;
sortujemy krawędzie E według długości, od najdłuższej do najkrótszej
dla każdej krawędzi e " E
usuwamy e z ET , jeżeli jej usunięcie nie rozspójnia grafu T .
Udowodnij poprawność tego algorytmu. Zastosuj go do grafu z rysunku 1.8a.
Niech G = (V, E) będzie dowolnym grafem z wagami krawędzi w, a T = (V, ET )
dowolnym minimalnym drzewem spinającym. Pokaż, że dla dowolnego wierzchołka v "
V do ET należą te krawędzie wychodzących z v, które maja najkrótsze wagi, to znaczy,
jeżeli e i f są dwiema krawędziami przyległymi do v takimi, że e " ET oraz f " ET , to
/
w(e) d" w(f).
1.15.5 Cykle Eulera
Rozważ następujący algorytm:
Algorytm wyznaczania cyklu Eulera.
Dane wejściowe: spójny graf, w którym wszystkie wierzchołki są parzystego stopnia.
Pomocniczy STOS.
Dane wyjściowe: CE  cykl Eulera.
Zaczynamy od dowolnego wierzchołka v0 i wkładamy go na STOS,
dopoki STOS nie jest pusty, powtarzamy:
Niech v będzie wierzchołkiem z wierzchu STOSU
jeżeli z v odchodzą jakieś nieodwiedzane krawędzie, to
wybieramy jednÄ… z nich,
przechodzimy na jej drugi koniec,
zaznaczamy jako odwiedzonÄ…
jej drugi koniec wkładamy na STOS.
Jeżeli wszystkie krawędzie odchodzące z v były już odwiedzone, to
zdejmujemy v ze STOSU,
przekładamy na wyjście CE
przechodzimy do wierzchołka znajdującego się pod v na STOSIE.
1.15. Problemy 31
Prześledz
działanie algorytmu na przykładzie z rysunku 1.9. Pokaż, że algorytm działa
poprawnie i oszacuj czas jego działania.
Wskazówki Pokaż, że wierzchołki na obu stosach są połączone krawędziami, że każda
krawędż (jako para sąsiednich wierzchołków) pojawia się na STOSIE tylko raz, oraz że
wszystkie krawędzie znajdą sie na wyjściu. Zauważ, że w każdej iteracji algoryt przecho-
dzi jakąś krawędż. Albo wkładając jej koniec na STOS, albo przekładając ją na wyjście
CE.