4 Wyklad Grafy

" G = (V, E)
V = {v1, v2, . . . , vn}
E = {e1, e2, . . . , em}
e
(u, v)
"
{u, v}
{u, v} = {v, u} {u, v} {v, u}

(u, v) (v, u)
(u, v) = (v, u)
"
" n
m
Przykłady grafów o rozmiarze n = 6 i m = 8
graf nieskierowany: graf skierowany:
v5
v5
5
v6
v6
v3 v3
8
3
9 9
3
3
v4 v4
8
8
4
v1
4 v1
4
4
5
5
3
v2
v2
n � n
i j (i, j)
{i, j}
(i, j)
"
(i, i)
O(n2)
m � 3
m
O(m)
Przykłady struktur grafowych
[5]
5
[3]
[6]
8
3 9
8
[4]
Lista krawędzi
4
[1]
4
5
[2]
A B W
Macierz wag
(1)
[1] [2] 5
[1] [2] [3] [4] [5] [6]
(2)
[1] [3] 3
[1]
5 3 4 8 9
(3)
[1] [4] 4
[2]
5 " 4 " 8
(4)
[1] [5] 8
[3]
3 " " 5 "
(5)
[1] [6] 9
[4]
4 4 " " " (6)
[2] [4] 4
[5]
(7)
[2] [6] 8
8 " 5 " "
[6]
(8)
[3] [5] 5
9 8 " " "
n
i
i
(i, j)
i j
O(n + m)
n m
O(n + m)
[5]
[6]
[3]
Przykłady struktur grafowych (c.d.)
3
3
9
[4]
4
[1]
8
4
5
Pęk wyjściowy
3
[2]
Połączone listy sąsiadów
B W
[2] 5 [3] 3 [4] 4 [6] 9
[1] [1]
1
(1)
[2] 5
[1] 3 [6] -8
[2] [2]
5
(2)
[3] 3
[1] 3
[3] [3]
7
(3)
[4] 4
[4] [2] 4 [4]
8
(4)
[6] 9
[5] [5] -1
[6] [6] -1
(5)
[1] 3
(6)
[6] -8
(7)
[1] 3
(8)
[2] 4
v1 vk G
{{v1, v2}, {v2, v3}, . . . , {vk-1, vk}}
{v1, v2, . . . , vk-1, vk}
v1 = vk
s t
G = (V , E ) G = (V, E) n d" n m d" m
V ą" V E ą" E G
G
m = n - 1
T
T = (V , ET )
T
G = (V, E) V = V
nn-2
Przykłady dróg z wierzchołka v5 do v6
v5
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Przykłady dróg z wierzchołka v5 do v6
Droga D1 {v5,v3,v1,v2,v6}
v5
Waga D1: 5+3+5+8 = 21
5
v6
v3
8
6
3
v4
8
v1
4
4
5
v2
Przykłady dróg z wierzchołka v5 do v6
Droga D1 {v5,v3,v1,v2,v6}
v5
Waga D1: 5+3+5+8 = 21
5
v6
v3
8
6
3
Droga D2 {v5,v1,v4,v6}
v4
8
v1
Waga D2: 8+4+6 = 18
4
4
5
v2
Przykłady drzew MST
Drzewo MST1
v5
Waga MST1: 3+8+4+4+6 = 25
5
v6
v3
8
6
3
v4
8
v1
4
4
5
v2
Przykłady drzew MST
Drzewo MST1
v5
Waga MST1: 3+8+4+4+6 = 25
5
v6
v3
8
Drzewo MST2
6
3
Waga MST2: 5+3+5+8+6 = 27
v4
8
v1
4
4
5
v2
C n
C[i] = i i = 1, 2, . . . , n
(u, v)
u v
u v
u v C[u] = C[v]
C[v] = C[u]
u v
(u, v)
u v
u C[v] = C[u]
u v
C[i] = C[v] C[i] == C[u]
(u, v)
C[u] == C[v]
C
C[u] == C[v] O(1)
n - 2
n/2
O(n)
O(m log m)
p n - 1
m
O(m log m + pm)
m >> n
O(log m) p
O(p(log m + m)) = O(pm),
n d" p d" m
O(m log m)
Algorytm KRUSKALA
v5
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm KRUSKALA
v5
1. (v1,v3) 3
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm KRUSKALA
v5
1. (v1,v3) 3
2. (v2,v4) 4
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm KRUSKALA
v5
1. (v1,v3) 3
2. (v2,v4) 4
5
v6
v3 3. (v1,v4) 4
8
9
3
v4
8
v1
4
4
5
v2
Algorytm KRUSKALA
v5
1. (v1,v3) 3
2. (v2,v4) 4
5
v6
v3 3. (v1,v4) 4
8
4. (v1,v2) cykl
9
3
v4
8
v1
4
4
5
v2
Algorytm KRUSKALA
v5
1. (v1,v3) 3
2. (v2,v4) 4
5
v6
v3 3. (v1,v4) 4
8
4. (v1,v2) cykl
9
3
v4
8
v1
4
4
5
v2
Algorytm KRUSKALA
v5
1. (v1,v3) 3
2. (v2,v4) 4
5
v6
v3 3. (v1,v4) 4
8
4. (v1,v2) cykl
9
5. (v3,v5) 5
3
v4
8
v1
4
4
5
v2
Algorytm KRUSKALA
v5
1. (v1,v3) 3
2. (v2,v4) 4
5
v6
v3 3. (v1,v4) 4
8
4. (v1,v2) cykl
9
5. (v3,v5) 5
3
v4
6. (v2,v6) 8
8
v1
4
4
5
v2
Algorytm KRUSKALA
v5
1. (v1,v3) 3
2. (v2,v4) 4
5
v6
v3 3. (v1,v4) 4
8
4. (v1,v2) cykl
9
5. (v3,v5) 5
3
v4
6. (v2,v6) 8
8
v1
4
waga MST: 24
4
5
v2
n - 1
O(m)
O(nm)
Q
O(m log n)
O(m + n log n)
Algorytm PRIMA
v5
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2) 8
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2) 8
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2) 8
5
2. (v2,v4) 4
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2) 8
5
2. (v2,v4) 4
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2) 8
5
2. (v2,v4) 4
v6
v3
8
3. (v1,v4) 4
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2) 8
5
2. (v2,v4) 4
v6
v3
8
3. (v1,v4) 4
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2) 8
5
2. (v2,v4) 4
v6
v3
8
3. (v1,v4) 4
4. (v1,v3) 3
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2) 8
5
2. (v2,v4) 4
v6
v3
8
3. (v1,v4) 4
4. (v1,v3) 3
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2) 8
5
2. (v2,v4) 4
v6
v3
8
3. (v1,v4) 4
4. (v1,v3) 3
9
3
5. (v3,v5) 5
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2) 8
5
2. (v2,v4) 4
v6
v3
8
3. (v1,v4) 4
4. (v1,v3) 3
9
3
5. (v3,v5) 5
v4
8
waga MST: 24
v1
4
4
5
v2
s
x
dsx
"
dss = 0
x"
x" dsy y
" " " "
dsx wx y {x", y} dsy = dsx + wx y
Algorytm DIJKSTRY
v5
2
4
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 " " " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 " " " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 " " " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 " " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 " " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 8 12
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 8 12
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 8 12
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 8 12
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 8 12
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 12
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 12
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 12
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3 Najkrótsza droga z v1 do v6:
{ v6}
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3 Najkrótsza droga z v1 do v6:
{ v5,v6}
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3 Najkrótsza droga z v1 do v6:
{ v5,v6}
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3 Najkrótsza droga z v1 do v6:
{ v3,v5,v6}
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3 Najkrótsza droga z v1 do v6:
{ v3,v5,v6}
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3 Najkrótsza droga z v1 do v6:
{ v1,v3,v5,v6}
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3 Najkrótsza droga z v1 do v6:
{ v1,v3,v5,v6}
v2
n
O(log n)
O(n)
O(n2)
O(m log n)
n
m
O(nm)
"
"
"
"
Algorytm BELLMANA-FORDA
Q = {v1}
v1 v2 v3 v4 v5 v6
v5
2
4
0 " " " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = { }
v1 v2 v3 v4 v5 v6
v5
2
4
0 " " " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v2,v3,v4,v5,v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 8 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v3,v4,v5,v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 8 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v3,v4,v5,v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 8 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v4,v5,v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 8 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v4,v5,v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 7 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v5,v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 7 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v5,v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 7 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 7 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 7 9
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = { }
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 7 9
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = { }
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 7 9
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
n
n
"
"
O(nm2)
Algorytm FORDA-FULKERSONA
v5
2
4
v6
v3
8
3
v4
7
4
v1
4
5
v2
Algorytm FORDA-FULKERSONA
v5
2
4
v6
v3
8
3
v4
7
4
v1
4
5
v2
Algorytm FORDA-FULKERSONA
v5
2
4
v6
v3
8
3
v4
7
4
v1
4
5
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
4
v6 F(v1,v2,v6) = 5
v3
8
3
v4
7
4
v1
4
5
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
4
v6 F(v1,v2,v6) = 5
v3
8
3
v4
2
4
v1
4
0
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
4
v6 F(v1,v2,v6) = 5
v3
8
3
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
4
v6 F(v1,v2,v6) = 5
v3
8
3
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
4
v6 F(v1,v2,v6) = 5
v3
8
3
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
4
v6 F(v1,v2,v6) = 5
v3
8
3
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
4
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
3
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
0
2
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
1
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
1
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
1
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
1
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
v4
0
2
v1
2
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
v4
2
v1
2
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
v4
2
v1
2
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
v4
2
v1
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
v4
v1
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
v4
v1
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
v4
v1
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
4
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
3
v4
Maks. przepływ = 9
7
4
v1
4
5
v2

Wyszukiwarka

Podobne podstrony:
grafy wykład
Sieci komputerowe wyklady dr Furtak
Wykład 05 Opadanie i fluidyzacja
WYKŁAD 1 Wprowadzenie do biotechnologii farmaceutycznej
mo3 wykladyJJ
ZARZĄDZANIE WARTOŚCIĄ PRZEDSIĘBIORSTWA Z DNIA 26 MARZEC 2011 WYKŁAD NR 3
Wyklad 2 PNOP 08 9 zaoczne
Wyklad studport 8
Kryptografia wyklad
Budownictwo Ogolne II zaoczne wyklad 13 ppoz
wyklad09
Sporzadzanie rachunku przepływów pienieżnych wykład 1 i 2
fcs wyklad 5

więcej podobnych podstron