Algorytmy grafowe
Grafy
G = (V,E)  graf
Gdzie:
V  zbiór wierzchołków
E  zbiór krawędzi
Grafy:
Skierowane
Nieskierowane
Spójność grafu
Graf G jest spójny, jeśli każde dwa wierzchołki można połączyć
ścieżką.
a) Graf spójny
b) Graf niespójny
Dwuspójność grafu
Graf G jest dwuspójny, jeśli między każdymi dwoma wierzchołkami
istnieją dwie różne ścieżki. Jeśli graf zawiera tylko 2 węzły, to jest
dwuspójny.
Punkt artykulacji (wierzchołek rozdzielający)  jego usunięcie
 rozspujnia graf (dzieli na dwuspójne składowe).
Silna spójność grafu
Graf skierowany G jest silnie spójny, jeśli dla każdych dwóch
wierzchołków v i w grafu G istnieją ścieżki skierowane z v do w oraz z
w do v.
Jeśli G nie jest silnie spójny, to można podzielić go na co najmniej dwie
silnie spójne składowe.
Reprezentacja grafu
Są dwie możliwości prezentacji
grafów w komputerze:
a) Lista sąsiedztwa
b) Macierz sąsiedztwa
Cykl, cykl prosty
W grafie skierowanym cyklem nazywamy ścieżkę która
zaczyna się i kończy w tym samym wierzchołku i zawiera co najmniej
jedną krawędz
.
W cyklu prostym dodatkowo wierzchołki v1, v2, & , vk są różne.
W grafie nieskierowanym cyklem nazywamy ścieżkę ,
gdzie v0=vk i v1, v2, & , vk są różne oraz k e"2.
Graf nie zawierający cykli nazywamy acyklicznym.
Cykl  przykłady grafów
Graf skierowany:
<1,2,4,3,4,1> - cykl
1 2
<1,2,4,1> - cykl prosty
4 3
<2,2> - pętla
Graf nieskierowany:
1 2
<1,2,3,1> - cykl
3
Cykl Eulera
Cykl Eulera przechodzi przez każdą krawędz
grafu dokładnie raz (ale
może odwiedzać wielokrotnie ten sam wierzchołek). Warunkiem istnienia
cyklu jest:
spójność grafu,
dla grafu skierowanego należy sprawdzić czy ilość krawędzi
wchodzących do danego wierzchołka jest równa ilości krawędzi
wychodzących,
dla grafu nieskierowanego z każdego wierzchołka musi wychodzić
parzysta liczba krawędzi.
Cykl Eulera c.d.
Do powstania cyklu Eulera przyczynił się tzw. problem mostów
królewieckich.
Mosty na rzece Pregole
Odpowiadający im graf nieskierowany
Cykl Eulera c.d.
2
2
1 2
1
1
3
4
4 3
3
4
5
5
5
Graf bez cyklu
Eulera
Grafy z cyklem
Eulera
Algorytm znajdujący cykl Eulera w grafie to algorytm Fleury ego.
Algorytm Fleury ego
Oznaczenia:
G = (V, E)  graf nieskierowany
V(G)  zbiór wierzchołków
C  ciąg zawierający kolejne wierzchołki grafu, tak aby tworzyły one
cykl Eulera
m  liczba krawędzi
Krawędz
incydentna: jeśli (u,v) jest krawędzią grafu nieskierowanego
G=(V,E), to (u,v) jest incydentna z wierzchołkami u i v.
Stopień wierzchołka: stopniem wierzchołka w grafie nieskierowanym jest
liczba incydentnych z nim krawędzi.
Most: mostem w grafie G jest każda krawędz
, której usunięcie rozspójnia
graf.
Algorytm Fleury ego  c.d.
Fleury(G)
C �!"
v �! dowolny wierzcholek z V[G]
while " w grafie krawędzie incydentne z v
do
wybierz dowolną krawędz
(v, w),
wybierajać krawędzie będące mostami jedynie w ostatecznosci
v �! w
G = G \ (u,v)
C = C *" (u,v)
if ciąg C zawiera wszystkie krawędzie grafu G then
zostala wyznaczona w nim droga Eulera
Złożoność obliczeniowa:
else
O(m2)
droga nie zostala wyznaczona
Cykl Hamiltona
Cykl Hamiltona to taki cykl w grafie, w którym każdy wierzchołek grafu
występuje dokładnie jeden raz.
1 2
Przykładowe cykle Hamiltona:
6 3
<1,2,6,5,3,4,1>
5 4
<1,5,6,2,4,3,1>
Nie istnieje żaden algorytm rozwiązujący ten problem w czasie
wielomianowym. Algorytmy znajdujące cykl Hamiltona należą do klasy
NP-zupełnych.
Stosuje się często algorytmy genetyczne, heurystyczne lub algorytmy
przybliżone, które nie wymagają rozważenia dużej liczby przypadków,
ale nie zawsze zwracają też rozwiązanie optymalne.
Cykl Hamiltona  c.d.
Znalezienie cyklu Hamiltona o minimalnej sumie wag krawędzi jest
równoważne rozwiązaniu problemu komiwojażera (TSP).
Stosowane rozwiązania:
Wyznaczenie minimalnego drzewa rozpinającego (alg. Kruskala oraz
Prima) i przeglądnięcie go metodą preorder
Algorytmy genetyczne
Algorytm Nearest Neighbour for TSP
Algorytm Greedy TSP
Nearest Neighbour for TSP
Oznaczenia:
G = (V, E)  graf pełny nieskierowany
V(G)  zbiór wierzchołków
  permutacja miast
aj,k  koszt przejazdu z miasta j do miasta k
n  liczba wierzchołków (miast)
Nearest Neighbour for TSP(G)
Ą (1) �! dowolne miasto
for i = 2 do n
do Ą(i) �! min{aĄ (i-1),k : k "{V(G)\ {Ą(1),...Ą(i -1}}}
Złożoność obliczeniowa: O(n2)
Greedy TSP
Oznaczenia:
G = (V, E)  graf pełny nieskierowany
E(G)  zbiór krawędzi
  permutacja krawędzi
ei  krawędz

m  liczba krawędzi (połączeń między miastami)
Greedy TSP(G)
posortuj krawędzie z E niemalejąco względem kosztów
for i =1 do m
do Ą(i) �! ei jeżeli dolaczenie krawędzi nie stworzy podcyklu
Złożoność obliczeniowa: O(mlog(m))
Wyszukiwanie najkrótszej ścieżki w grafie
Algorytm Dijkstry
Algorytm służy do rozwiązywania problemu najkrótszych ścieżek z
jednym z
ródłem w Grafie. Wagi są nieujemne  np. mogą
reprezentować odległości między miastami.
Użyte symbole:
G = (V, E)  graf ważony skierowany
w(u,v) e" 0 dla każdej krawędzi grafu G (wagi są nieujemne)
s  wierzchołek startowy
S  zbiór zawierający wierzchołki, dla których wagi najkrótszych
ścieżek ze z
ródła s zostały już obliczone
Q  kolejka priorytetowa (kluczami są aktualne odległości od s),
Q = V  S
Adj [u]  następniki wierzchołka u
Algorytm Dijkstry c.d.
Dijkstra(G, w, s)
S �!"
Q �! V[G]
whileQ `""
do u �! MIN(Q)
S �! S *"{u}
for każdy wierzcholek v " Adj[u]
do RELAKSACJA(u, v, w)
2
OV )
(
Złożoność obliczeniowa -
Algorytm Dijkstry c.d.
Relaksacja krawędzi (u,v) polega na sprawdzeniu, czy przechodząc
przez wierzchołek u, można znalez
ć krótszą od dotychczas najkrótszej
ścieżki do v. Procedura relaksacji wygląda następująco:
RELAKS(u,v, w)
if d[v] > d[u]+ w(u,v)
then d[v] �! d[u]+ w(u,v)
Ą[v] �! u
Gdzie:
d[v] - dotychczas najkrótsza ścieżka od z
ródła do v
Ą[v] - poprzednik v
Algorytm Dijkstry c.d.
W algorytmie Dijkstry pamiętany jest zbiór S zawierający te wierzchołki,
dla których wagi najkrótszych ścieżek ze z
ródła s zostały już obliczone.
Algorytm polega na wielokrotnym powtarzaniu operacji:
Wybraniu wierzchołka o najmniejszym oszacowaniu wagi najkrótszej
ścieżki od zbioru S
Dodaniu tego wierzchołka do S
Wykonaniu przeliczenia oszacowań z uwzględnieniem nowo dodanego
wierzchołka  tzw. Relaksacja problemu.
W poniższym przykładzie wierzchołki czarne należą do zbioru S.
Czerwone krawędzie pokazują oszacowania dróg.
Algorytm Dijkstry - przykład
Algorytm Bellmana-Forda
Algorytm służy do rozwiązywania problemu najkrótszych ścieżek z
jednego z
ródła w ogólnym przypadku, gdzie wagi mogą być ujemne (
w(u,v) " ).
Algorytm zwraca wartość FALSE, jeśli w grafie istnieje cykl o ujemnej
wadze osiągalny ze z
ródła.
W przeciwnym wypadku oblicza najkrótsze ścieżki i ich wagi.
Użyte symbole:
oznaczenia jak w algorytmie Dijkstry
Algorytm Bellmana-Forda c.d.
Interpretacja:
Wagi pomiędzy wierzchołkami można traktować np. jako koszt
przejazdu między dwoma miastami.
Wagę ujemną traktujemy jako zwrot kosztów podróży.
W takim przypadku istnieje niebezpieczeństwo powstania cyklu
zamkniętego, po którym podróż dawałaby nieskończone zyski.
Oczywiście w rzeczywistym przypadku taka sytuacja nie jest możliwa.
Z tego powodu algorytm wykrywa te cykle i zwraca wartość FALSE.
Algorytm Bellmana-Forda c.d.
Bellman - Ford(G, w, s)
for i �!1to V[G] -1
do for każda krawędz
(u,v)" E[G]
do RELAKSACJA(u,v, w)
for każda krawędz
(u,v)" E[G]
do if d[v] > d[u]+ w(u,v)
thenreturn FALSE
return TRUE
Złożoność obliczeniowa - OVE)
(
Algorytm Bellmana-Forda c.d.
Podobnie jak w algorytmie Dijkstry, w algorytmie Bellmana-Forda
wykorzystuje się metodę relaksacji, zmniejszając stopniowo
oszacowanie d[v] na wagę najkrótszej ścieżki ze z
ródła s do każdego
wierzchołka, aż zostanie osiągnięta rzeczywista waga najkrótszej
ścieżki.
W poniższym przykładzie czerwone krawędzie oznaczają tymczasowe,
 najlepsze krawędzie do wierzchołków od z
ródła. Wartości w
wierzchołkach to aktualne oszacowania najkrótszej drogi.
Algorytm Bellmana-Forda - przykład
Algorytm Floyda-Warshalla
Algorytm znajduje najkrótsze ścieżki między wszystkimi parami
wierzchołków skierowanych w grafie skierowanym G = (V,E).
Zakłada się, że wagi mogą być ujemne, ale brak jest cykli z wagami
ujemnymi.
( n )
D
Algorytm wylicza rekurencyjnie macierz najkrótszych ścieżek .
Użyte symbole:
(
dijn ) waga najkrótszej ścieżki z wierzchołka i do j, której wszystkie
wewnętrzne wierzchołki należą do zbioru {1,2, & , k}
W  macierz sąsiedztwa, gdzie:
W = (wij )
0, jeżelii = j
ńł
�łwaga krawędzi (i, j), jeżelii `" j i (i, j) " E
wij =
�ł
�ł"
jeżelii `" j i (i, j) " E
ół
Algorytm Floyda-Warshalla c.d.
Floyd -Warshall(W )
n �! rozmiar grafu
D(0) �! W
for k �!1to n
do for i �!1to n
do for j �!1to n
( ( ( (
dijk ) �! min(dijk -1), dikk -1) + dkjk -1))
return D(n)
"
Do konstruowania najkrótszej ścieżki buduje się macierz poprzedników :
ńł
�łNIL, jeżelii = j lub wij = "
(0)
Ąij =
�łi,jeżelii `" j lub wij < "
�ł
ół
(k -1) ( ( (
ńł
jeżeliĄijk ) d" Ąikk -1) + Ąkjk -1)
ij
�łĄ
(
Ąijk ) =
�ł
(k -1) ( ( (
jeżeliĄijk ) > Ąikk -1) +Ąkjk -1)
�łĄ
kj
ół
Algorytm Floyda-Warshalla c.d.
Działanie algorytmu polega na badaniu w każdej iteracji czy
dołożenie wierzchołka k do ścieżki między każdymi dwoma
wierzchołkami nie polepszy oszacowania odległości między nimi.
(
Jeśli tak, oszacowanie dijk ) jest zmniejszane.
(
(
dkjk -1)
dikk -1)
(
dijk )
Algorytm Floyda-Warshalla - przykład
0 3 8 4 -4 NIL 1 1 2 1
�ł�ł �ł �ł
�ł" 0 " 1 7 �ł �ł �ł
NIL NIL NIL 2 2
�ł�ł �ł �ł
�ł�ł �ł �ł
D(2) = " 4 0 5 11 "(2) = NIL 3 NIL 2 2
�ł�ł �ł �ł
2 5 -5 0 -2�ł �ł 4 1 4 NIL 1
�ł �ł
�ł" " " 6 0 �ł �ł
NIL NIL NIL 5 NIL�ł
�łłł �ł łł
0 3 8 4 -4 NIL 1 1 2 1
�ł�ł �ł�ł
�ł" 0 " 1 7 �ł �ł�ł
NIL NIL NIL 2 2
�ł�ł �ł�ł
�ł�ł �ł�ł
D(3) = " 4 0 5 11 "(3) = NIL 3 NIL 2 2
�ł�ł �ł�ł
2 -1 -5 0 -2�ł �ł 4 3 4 NIL 1
�ł �ł
�ł" " " 6 0 �ł �ł
NIL NIL NIL 5 NIL�ł
�łłł �łłł
0 3 -1 4 -4 NIL 1 4 2 1
�ł�ł �ł �ł
0 3 8 " -4 NIL 1 1 NIL 1
�ł�ł �ł �ł
�ł �ł
�ł" 0 " 1 7 �ł �ł �ł
3 0 -4 1 -1�ł �ł 4 NIL 4 2 1
NIL NIL NIL 2 2
�ł�ł �ł �ł
�ł�ł �ł �ł
�ł�ł �ł �ł
D(4) = 7 4 0 5 3 "(4) = 4 3 NIL 2 1
�ł�ł �ł �ł
D(0) = " 4 0 " " "(0) = NIL 3 NIL NIL NIL
�ł�ł �ł �ł
�ł�ł �ł �ł
2 -1 -5 0 -2�ł �ł 4 3 4 NIL 1
2 " -5 0 " 4 NIL 4 NIL NIL�ł
�ł �ł
�ł�ł �ł
�ł�ł �ł
�ł" " " 6 0 �ł �ł
8 5 1 6 0 4 3 4 5 NIL�ł
NIL NIL NIL 5 NIL�ł �łłł �ł łł
�łłł �ł łł
0 1 -3 2 -4 NIL 3 4 5 1
�ł
0 3 8 " -4 NIL 1 1 NIL 1
�ł�ł �ł�ł�ł �ł�ł
�ł �ł
�ł" 0 " 1 7 �ł �ł�ł
3 0 -4 1 -1�ł �ł 4 NIL 4 2 1
NIL NIL NIL 2 2
�ł
�ł�ł �ł�ł�ł �ł�ł
�ł
D(5) = 7 4 0 5 3 "(5) = 4 3 NIL 2 1
�ł�ł �ł�ł�ł �ł�ł
D(1) = " 4 0 " " "(1) = NIL 3 NIL NIL NIL
�ł
�ł�ł �ł�ł�ł �ł�ł
2 -1 -5 0 -2�ł �ł 4 3 4 NIL 1
2 5 -5 0 -2�ł 4 1 4 NIL 1
�ł
�ł �ł�ł�ł �ł�ł
�ł
�ł" " " 6 0 �ł �ł
8 5 1 6 0 4 3 4 5 NIL�ł
NIL NIL NIL 5 NIL�ł �ł
�łłł �łłłłł �łłł
Algorytm Floyda-Warshalla - przykład
0 1 -3 2 -4 NIL 3 4 5 1
�ł�ł �ł �ł
�ł �ł
3 0 -4 1 -1�ł �ł 4 NIL 4 2 1
�ł�ł �ł �ł
�ł�ł �ł �ł
D(5) = 7 4 0 5 3 "(5) = 4 3 NIL 2 1
�ł�ł �ł �ł
2 -1 -5 0 -2�ł �ł 4 3 4 NIL 1
�ł �ł
�ł8 5 1 6 0 �ł �ł
4 3 4 5 NIL�ł
�łłł �ł łł
Np.:
Koszt ścieżki z 1 do 3: -3.
Ścieżka: 1->5->4->3
Drzewa rozpinające
Drzewa rozpinające
Drzewem rozpinającym grafu G nazywamy drzewo, które zawiera
wszystkie wierzchołki grafu G, zaś zbiór krawędzi drzewa jest podzbiorem
zbioru krawędzi grafu.
Minimalnym drzewem rozpinającym nazywamy drzewo rozpinające, dla
którego suma wag krawędzi jest najmniejsza z możliwych.
Drzewa rozpinające  c.d.
Zastosowania drzew rozpinających:
Znajdywanie optymalnych połączeń dla sieci telefonicznych,
wodociągów, energetycznych, komunikacyjnych etc.
Rozwiązywanie problemu komiwojażera
Do wyznaczania minimalnego drzewa rozpinającego służą algorytmy:
Kruskala
Prima
Algorytm Kruskala
Oznaczenia:
G = (V, E)  graf spójny nieskierowany
V(G)  zbiór wierzchołków
w: E R  funkcja wagowa, gdzie w(u,v) e" 0 dla każdej krawędzi grafu
A  zbiór będący podzbiorem drzewa minimalnego
m  liczba krawędzi
Algorytm Kruskala  c.d.
Algorytm Kruskala  skrócony opis
1. Dla każdego wierzchołka grafu tworzone jest drzewo jednostkowe
(zawierające tylko i wyłącznie dany wierzchołek).
2. Wszystkie krawędzie są sortowane niemalejąco względem wag.
3. W każdej iteracji do rozwiązania dodawana jest krawędz

o najmniejszej możliwej wadze, pod warunkiem, że nowy wierzchołek
nie był już wcześniej dodany do drzewa.
Sprawdzenie to odbywa się w instrukcji:
DRZEWO(u)`"DRZEWO(v)
Złożoność obliczeniowa: O(mlogm)
Algorytm Kruskala  c.d.
Kruskal(G, w)
A �!"
for każdy wierzcholek v "V[G]
do STWORZ _ DRZEWO _ 1-WIERZCHOLKOWE(v)
posortuj krawędzie z E niemalejaco względem wag w
for każda krawędz
(u,v)" E, w kolejnosci nie malejących wag
do if DRZEWO(u) `" DRZEWO(v)
then A �! A*"{(u,v)}
ZA

CZENIE _ DRZEW (u,v)
return A
Algorytm Kruskala  przykład
1)
b 8 c 7 d
a i e
h 1 g 2 f
11
14
11
14
11
14
9
9
4
2
2
4
4
6
6
8
0
0
7
7
1
1
9
9
4
4
2
2
4
4
6
6
8
8
0
0
7
7
1
1
Algorytm Kruskala  przykład c.d.
11
14
11
14
11
14
11
14
9
9
4
4
2
2
4
4
6
6
8
8
0
0
7
7
1
1
9
9
4
4
2
2
4
4
6
6
8
8
0
0
7
7
1
1
Algorytm Kruskala  przykład c.d.
10)
b 8 c 7 d
a i e
h 1 g 2 f
11
14
11
14
11
14
11
14
9
9
4
4
2
2
4
4
6
6
8
8
0
0
7
7
1
1
9
9
4
4
2
2
4
4
6
6
8
8
0
0
7
7
1
1
Algorytm Kruskala  przykład c.d.
Suma wag krawędzi dla minimalnego
drzewa rozpinającego wynosi 37.
11
14
11
14
9
4
2
4
6
8
0
7
1
9
4
2
4
6
8
0
7
1
Algorytm Prima
Oznaczenia:
G = (V, E)  graf spójny nieskierowany
w: E R  funkcja wagowa, gdzie w(u,v) e" 0 dla każdej krawędzi grafu
V(G)  zbiór wierzchołków
r  wierzchołek startowy, korzeń
Q  kolejka priorytetowa (kluczem key[v] dla każdego wierzchołka v jest
minimalna waga spośród krawędzi łączących v z wierzchołkami
drzewa)
(V-Q)  zbiór zawierający wierzchołki budowanego drzewa
[v]  ojciec wierzchołka v
Adj [u]  sąsiedzi wierzchołka u
m  liczba krawędzi
n  liczba wierzchołków
Algorytm Prima  c.d.
Algorytm Prima  skrócony opis
1. Inicjowanie kolejki priorytetowej (kluczem wierzchołka początkowego
r jest 0, pozostałych ", korzeń r nie ma ojca, więc (r)=NIL)
2. W procedurze MIN(Q) zwracany jest wierzchołek o najmniejszej
wartości klucza key[i] oraz usuwany jest ze zbioru Q.
3. Następnie aktualizowane są wartości pół key i , dla każdego
wierzchołka v spoza drzewa, który sąsiaduje z u.
Złożoność obliczeniowa: O(mlogn)
Algorytm Prima  c.d.
Prim(G, w, r)
Q �! V[G]
for każdy u "Q
do key[u] �!"
key[r] �! 0
Ą[r] �! NIL
while Q `""
do u �! MIN(Q)
for każdy v " Adj[u]
do if v "Q i w(u,v) < key[v]
then Ą[v] �! u
key[v] �! w(u,v)
Algorytm Prima  przykład
11
14
11
14
11
14
11
14
9
9
4
4
2
2
4
4
6
6
8
8
0
0
7
7
1
1
9
9
4
4
2
2
4
4
6
6
8
8
0
0
7
7
1
1
Algorytm Prima  przykład c.d.
11
14
11
14
11
14
11
14
9
9
4
4
2
2
4
4
6
6
8
8
0
0
7
7
1
1
9
9
4
4
2
2
4
4
6
6
8
8
0
0
7
7
1
1
Algorytm Prima  przykład c.d.
Suma wag krawędzi dla minimalnego
drzewa rozpinającego wynosi 37.
11
14
9
4
2
4
6
8
0
7
1
Algorytmy przepływowe
Algorytmy przepływowe
Każdą krawędz
skierowaną w grafie można interpretować jako kanał,
którym coś płynie (woda w rurociągu, prąd w przewodzie& ).
Każdy kanał ma ustaloną przepustowość, wyznaczającą maksymalną
szybkość, z jaką następuje przepływ w tym kanale.
Musi być spełniona własność zachowania przepływu  szybkość
wpływania do wierzchołka musi być taka sama jak szybkość
wypływania.
Algorytmy przepływowe c.d.
Sieci z wieloma z
ródłami i
ujściami
W celu ułatwienia problemu
wprowadza się superz
ródło
oraz superujście
"
"
"
"
"
Metoda Forda-Fulkersona
Najczęściej spotykanym problemem jest problem maksymalnego
przepływu.
Metoda Forda-Fulkersona rozwiązuje ten problem.
Użyte pojęcia:
f(u,v)  wielkości przepływu między węzłami u i v
ścieżka powiększająca  jest to ścieżka ze z
ródła do ujścia, po której
możemy przesłać większy przepływ
Metoda Forda-Fulkersona c.d.
Ford- Fulkerson(G, s,t)
inicjowanie f na 0
whileistniejesciezka powiekszajaca p
do powieksz przeplyw f wzdluz p
return f
Metoda Forda-Fulkersona c.d.
Praktyczny algorytm Forda-Fulkersona może wyglądać następująco:
Ford- Fulkerson(G, s,t)
for kazda krawedz (u,v)" E[G]
do f [u,v] �! 0
f [v,u] �! 0
whileistniejesciezka p z s dot
do cf ( p) �! min{cf (u,v) : (u,v) jest na p}
for kazda krawedz (u,v) na p
do f [u,v] �! f [u,v]+ cf ( p)
f [v,u] �!- f [u,v]
Maksymalny przepływ określa całkowity wypływ z wierzchołka końcowego.
3
Złożoność obliczeniowa - OV )
(
Metoda Forda-Fulkersona c.d.
W metodzie Forda-Fulkersona w każdej iteracji znajdujemy dowolną
ścieżkę powiększającą p i zwiększamy przepływ f wzdłuż p o
cf ( p)
przepustowość residualną . W następującej implementacji tej
metody obliczamy maksymalny przepływ w grafie G=(V,E), aktualizując
przepływ netto f[u,v] między każdą parą wierzchołków u,v połączonych
krawędzią w G.
Przepustowość residualną obliczamy ze wzoru:
cf (u,v) = c(u,v) - f (u,v)
Metoda Forda-Fulkersona - przykład
Maksymalny przepływ wynosi 2.
Kolorowanie grafu
Kolorowanie grafu
Kolorowanie grafu to przyporządkowanie wierzchołkom grafu liczb
naturalnych w taki sposób, aby końce żadnej krawędzi nie miały
przypisanej tej samej liczby (koloru).
Optymalnym pokolorowaniem grafu nazywamy pokolorowanie
zawierające najmniejszą możliwą liczbę kolorów.
Liczbą chromatyczną grafu G nazywamy liczbę �(G) równą minimalnej
liczbie kolorów wystarczającej do prawidłowego pokolorowania
wierzchołków grafu G.
Problem znalezienia optymalnego pokolorowania a także znalezienia
liczby chromatycznej jest NP zupełny.
Kolorowanie grafu - zastosowania
Ustalanie planów i harmonogramów zajęć
Przypisywanie częstotliwości w telefonach komórkowych
Ustalanie wartości wpisów w rejestrach komputera
Rozpoznawanie wzorców
Analiza danych w biologii i archeologii
Kolorowanie grafu  c.d.
Do kolorowania grafu służą następujące algorytmy:
Algorytm zachłanny
Algorytm DSATUR
Algorytm MAXIS
Algorytm zachłanny
Algorytm zachłanny - przechodząc kolejno wszystkie wierzchołki
grafu, kolorujemy każdy z nich najmniejszym możliwym kolorem, tzn.
takim, który dotychczas nie został użyty dla żadnego z sąsiadów
rozważanego wierzchołka.
G = (V, E)  graf
c(u)  funkcja kolorująca, przypisująca kolor do wierzchołka
Adj[u]  sąsiedztwo wierzchołka u
n  liczba wierzchołków
Greedy Algorithm(G)
while V `""
do wybierz wierzcholek u "V
u �! c(u), c(u) `" c(v) "v " Adj[u]
Złożoność obliczeniowa:
V �! V \{u}
O(m2)
Algorytm zachłanny  przykład
1) 2) 3)
3 3 3
2 4 2 4 2 4
1 5 1 5 1 5
6)
5)
4)
3
3
3
2 4
2 4
2 4
1 5
1 5
1 5
Algorytmy DSATUR i MAXIS
Algorytm DSATUR działa podobnie jak algorytm zachłanny ale
kolejność rozpatrywania wierzchołków grafu wyznaczana jest
dynamicznie w zależności od liczby kolorów, które mogą być użyte do
pomalowania poszczególnych wierzchołków. Najpierw kolorowane są
te wierzchołki, dla których jest najmniej możliwości.
Algorytm MAXIS opiera się na algorytmie znajdującym największy
zbiór niezależny wśród wierzchołków danego grafu (żadne dwa
wierzchołki takiego zbioru nie sąsiadują ze sobą).
Algorytm MAXIS  c.d.
G = (V, E)  graf
MIS(U)  funkcja wyznaczająca najliczniejszy zbiór niezależny
MIN(U)  funkcja zwracająca wierzchołek o minimalnym stopniu
c(u)  funkcja kolorująca
procedura MIS(U )
Maxis(G)
U ' �! U
U �! V[G]
W �!"
k �! 0
while U ' `""
while U `""
do u �! MIN(U ')
W �! W *"{u}
do k �! k +1
U ' �!U '\{u}\{v "U ': (u,v)" E}
W �! MIS(U )
return W
for każdy u "W
do c(u) �! k
U �! U \W
Algorytm MAXIS  przykład
2)
1
6 2
5 3
4
Kolorowanie grafu  c.d.
Kolorowanie grafów ma wiele odmian, m.in.:
Kolorowanie krawędzi  jest to przyporządkowywanie krawędziom liczb
naturalnych symbolizujących kolory
Listowe kolorowanie  kolorowanie wierzchołków, przy czym każdy wierzchołek
posiada odpowiadającą mu listę kolorów
Całkowite kolorowanie  kolorowanie wierzchołków oraz krawędzi
Harmoniczne kolorowanie  kolorowanie wierzchołków, gdzie każda para
kolorów użyta jest co najwyżej raz w stosunku do sąsiadującej pary
wierzchołków
Kompletne kolorowanie - kolorowanie wierzchołków, gdzie każda para kolorów
użyta jest co najmniej raz w stosunku do sąsiadującej pary wierzchołków
Dokładne kolorowanie - kolorowanie wierzchołków, gdzie każda para kolorów
użyta jest dokładnie raz w stosunku do sąsiadującej pary wierzchołków
Literatura
1. Thomas H. Cormen, Charles E. Leiserson  Wprowadzenie do
algorytmów
2. http://en.wikipedia.org/wiki/Main_Page - Wikipedia, the free
encyclopedia
3. http://www.algorytm.cad.pl - Algorytmy i struktury danych
4. http://mat.gsia.cmu.edu/COLOR/general/ccreview/node2.html -
Sample applications of graph coloring
5. http://www.cs.ualberta.ca/~joe/Coloring/Colorsrc/manual.html - Graph
coloring
6. J. Sikorski  Matematyka dyskretna  wykłady
7. A. Drozdek i D. Simons  Struktury danych w języku C
8. L.Banachowski, K. Diks i W. Rytter  Algorytmy i struktury danych