8
Podstawowe algorytmy teorii
grafów
s t
G n
n - 1
G
v (r(v), p(v)) r(v)
v p(v) v
e = (vi, vj)
r(vi) = r(vj) vi vj e
 G = (V, E)
G
|V | - 1
G = (V, E) G
e1
e1, e2, . . . , ek E\{e1, e2, . . . , ek}
ek+1
" e1, e2, . . . , ek, ek+1
" ek+1
|V | - 1
îÅ‚ Å‚Å‚
" 1 " 10 8 3
ïÅ‚ śł
1 " 13 10 6 4
ïÅ‚ śł
ïÅ‚
" 13 " 15 " 11śł
ïÅ‚ śł
W =
ïÅ‚
10 10 15 " 9 "śł
ïÅ‚ śł
ðÅ‚ ûÅ‚
8 6 " 9 " 7
3 4 11 " 7 "
 G G
G G
G
G
C1, C2, . . . , Cm
E(G) = E(C1) *" E(C2) *" · · · *" E(Cm) .
v0e1, v1e2, . . . , env0
n
w(ei)
i=1
G
v0 W0 = v0
Wi = v0e1v1e2 . . . eivi ei+1
E - {e1, e2, . . . , ei}
" ei+1 vi
" ei+1 Gi = G - {e1, . . . , ei}
e w(e)
w(e)
G
 G" G

w(e)
e"E(G")-E(G)
G"
v " V (G) G
G
G
S V (G)
É(G - S) |S|.