ң ө ң ө. ң 1736 , ө . ң ғ ә ө . 1936 . ұ.
қ 1. V V ң ң ұ ұ E қ қ . : G = (V, E).
ө ғ қ .
қ 2. E ң ұ ққ, ғғ () , ң қ . ғ ғғ, E ң ң ғ .
1. ғғ . 2. ғғ .
қ 3. (a, a) ұ ұқ , ғ (a, b) ұ , қ (ғ) .
қ 4. ұ ұқ ə қ ғғ ( ғ ), ұқ , ұқ .
қ 5. Қ қ ғқ ө .
қ 6. қ ө қғ , .
қ 7. өң ə (deg v) ө қ . ғ ұқ ə .
ұ 1. p ө , q қ , () ү ң .
ə. өң ə ғ, ққ қң . қ өң ə ққ, ұ қ ə қ ө (ұқ қ ).
қ 8. ң өң V = { v 1, v 2, , v p }. v i ə v j ө ғ a ij = 1, ғ a ij = 0( ү 2,3,..) A = || a ij || . ұ ғ a ii ң ə v i ө ұқ ң.
3.
қ 9. G 1 = (V 1, E 1) ə G 2 = (V 2, E 2) ( ) . φ 1: V 1 → V 2 ə φ 2: E 1 → E 2 ө ə G 1 ң u ə v ө ү _(N_x9__ φ 2(u, v) = (φ 1(u), φ 1 (v)) ң , ұ .
|
|
4.
қ 10 (ұқ ə қ ң ғ).
G 1 = (V 1, E 1) ə G 2 = (V 2, E 2) ү ө ə φ 1: VG 1 = (V 1, E 1) ə G 2 = (V 2, E 2) ү ө ə φ 1: V 1 → V 2 , (u, v)∈ E 1 ⇔ (φ (u), φ (v)) ∈ E 2 , ұ .
қ 11. V 1⊆ V ə E 1⊆ E , G 1 = (V 1, E 1) G = (V, E) ң .
қ 12.G = (V,E) ң ө қ ұ . ғ n ң ұғ .
қ 13. Қ қ .
қ 14. ө қ қ .
ұ 2. G =(V,E) P - v 1 ө v 2(v 1≠ v 2) ө . P v 1 ө v2 (v1 ≠ v2) ө , қ ғ .
ə. қ . ң қ v ө ұ қ. ң ө P = v0C0vC1vC2vn . P 2= C 0 v , қ . ə қ қ қ ң ө ғ . қ .
қ 15. v 0= vn , ұқ .
қ 16. Қ қ ұқ .
қ 17. ө қ ұқ қ .
қ 18. өң ғ . Ə ө ө қ ғғ . ң ұғ ө ң.
vi ө vj ө , vi → vj қ . ұ қ
1) , ө vi → vj ⇒ vj → vi,
2) , ө (vi → vj) &(vj → vk) ⇒ (vi → vk),
3) , ө ∀ i (vi → vi).
қғ → қ ғ қ . қ ққ ə ң ө қ. ө ң ғ . , G = (V, E) i=1
1) Vi = V: 2) i ≠ j ⇒ V i ∩ V j =∅. G = (V, E) ң ғ G i = (V i, E i) ғ, ғ ғ .
|
|
5. ғ 젠 6. Қғ
ң . ө . v u ө қ. ң . u ө . қ q ө ә q ө қ ә қғ , q ө ң ғ ө қ . ғ ө , қ қ. ұ ә ү ү ә құ .
ғ ң қ. ө . :
ө қң FLAG
Қғ өң ө қ ү - ST
өң ө - Y
өң ө T
7. ң ә ң
8. ң 9. өң
ү қ
. Әңғ ғғ қ ө қ. ө ң қ ө ң . ұ ү ү ә құ .
ғ ғ ң қ. ө . :
ө қң FLAG
ө қ - ORDER
ң ө X
ң ң ө Y
10. ң ә ң
11. 12. өң
ү қ
. ә қғ ө .
. қ ғғ G құ , қ ә ө ө ң . өң ә ө қғ .
. қғ . . ң ө, қ қғ . Қ (ө ө) қ. Қғ қ ө қғ, ө . ғ ғ . өң ө ң ә .
13. ң 14. ңң
ә ң қ
|
|
қ . ң ә ө қ , қ . ң ө қ . қ қ қ .
15. қ ң
қ . қ ғғ . қ қ , . ә қ .
, ң ө қ. ң k ң қ. ңғ ө ғ қғ қ. қғ ө , ұ ө ә қғ . k+1 ң .
, ғ ө қ , қ ө ғ қғ ғ .
ң қ ө ә ңғ ө ү қғ . ғ ә ғ . қ .
16. қ 17. ғ ө,
. ң
ұ ә.