G
G = (V, E)
u v u, v " V (u, v) G
V
V V1 V2 . . . V�
Vi
G[V1] G[V2] . . . G[V�] G
� = �(G) G
�(G) = 1 G
�(G) > 1
G
G = (V, E)
V V1 V2 V1
V2
G � �
�-1
� > G � > 1
2
�-1
� =
2
G � G � =
�(G) �
� - � + 1
� - � � .
2
G Gc
G �(G) = �(G) - 1
G e
�(G - e) > �(G).
G = (V, E) e u v
e G
 �(G - e) = �(G) + 1
u v G - e
e G
G
G
G = (V, E) e " E
e G
v G
E(G) E1 E2
v G[E1] G[E2]
G v
�(G - v) > �(G)
k > 0 G
v
�(G - v) = k.
e G
G � e
G = (V, E) �(G)
G e " E G
�(G) = �(G - e) + �(G � e).
G �(G) = 0 G
�(G) = 1
K4
�(Kn) n
�(Kn) = nn-2.
(t1, t2, . . . , tn-2) 1 ti n
V = [n] = {1, 2, . . . , n} s1
T Kn
s1 t1 T s1 s2
1 T - s1 s2
t2 tn-2
v T dT (v) - 1
(t1, t2, . . . , tn-2)
T (t1, t2, . . . , tn-2)
s1 V (t1, . . . , tn-2)
s1 t1 s2 V \ {s1}
(t2, . . . , tn-2) s2 t2 n - 2
s1t2, s2t2, . . . , sn-2tn-2 .
V \ {s1, s2, . . . , sn-2}
T
(5, 3, 1, 7, 1, 7)
4 7
5
1 2 8 11 10
3 6 9 12
v
v w
w w
 Numer[x] �! 1 Numer[y] �! 0 y = x Drzewo �! "

�! " x Kolejki
Kolejka
Kolejki v
w v
Numer[w] = 0 w
w w Kolejki vw
Drzewa
Numer[w] = 0 w

vw " Drzewo
/
v w
v
v �! x i �! 0 Drzewo �! " �! "
i �! i + 1 Numer(v) �! i
v
v
v
vw
w
w
Numer(w) vw Drzewo
v �! w
w Numer(w) <
Numer(v) vw
v
uv Drzewo Numer(u) <
Numer(v)
u u
v v �! u
x
x