Π€ΠΈΠ³ΡΡΠ° F Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π³Π΅ΠΎΠΌΠ΅ΡΡΠΈΡΠ΅ΡΠΊΠΎΠΉ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠ΅ΠΉ Π³ΡΠ°ΡΠ° G (V, E), Π΅ΡΠ»ΠΈ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ Π²Π·Π°ΠΈΠΌΠ½ΠΎ ΠΎΠ΄Π½ΠΎΠ·Π½Π°ΡΠ½ΠΎΠ΅ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρ ΡΠΎΡΠΊΠ°ΠΌΠΈ ΡΠΈΠ³ΡΡΡ F ΠΈ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ Π³ΡΠ°ΡΠ°, ΠΌΠ΅ΠΆΠ΄Ρ ΠΊΡΠΈΠ²ΡΠΌΠΈ ΡΠΈΠ³ΡΡΡ ΠΈ ΡΠ΅Π±ΡΠ°ΠΌΠΈ, ΡΠ°ΠΊΠΎΠ΅, ΡΡΠΎ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠ΅ ΠΊΡΠΈΠ²ΡΠ΅ ΠΈ ΡΠ΅Π±ΡΠ° ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠ΅ ΡΠΎΡΠΊΠΈ ΠΈ Π²Π΅ΡΡΠΈΠ½Ρ.
ΠΡΠ°Π²ΠΈΠ»ΡΠ½Π°Ρ ΡΠΊΠ»Π°Π΄ΠΊΠ° — ΡΡΠΎ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ Π³ΡΠ°ΡΠ°, ΠΏΡΠΈ ΠΊΠΎΡΠΎΡΠΎΠΉ ΡΠ°Π·Π½ΡΠΌ Π²Π΅ΡΡΠΈΠ½Π°ΠΌ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡ ΡΠ°Π·Π½ΡΠ΅ ΡΠΎΡΠΊΠΈ, Π° ΠΊΡΠΈΠ²ΡΠ΅, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠ΅ ΡΠ΅Π±ΡΠ°ΠΌ, Π½Π΅ ΠΏΡΠΎΡ
ΠΎΠ΄ΡΡ ΡΠ΅ΡΠ΅Π· ΡΠΎΡΠΊΠΈ (ΠΈΡΠΊΠ»ΡΡΠ°Ρ ΠΊΠΎΠ½ΡΠ΅Π²ΡΠ΅) ΠΈ Π½Π΅ ΠΏΠ΅ΡΠ΅ ΡΡΠ΅ΠΊΠ°ΡΡΡΡ.
Π’Π΅ΠΎΡΠ΅ΠΌΠ°: ΠΊΠ°ΠΆΠ΄ΡΠΉ ΠΊΠΎΠ½Π΅ΡΠ½ΡΠΉ Π³ΡΠ°Ρ Π΄ΠΎΠΏΡΡΠΊΠ°Π΅Ρ ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΡΡ ΡΠΊΠ»Π°Π΄ΠΊΡ Π² ΡΡΠ΅Ρ
ΠΌΠ΅ΡΠ½ΠΎΠΌ ΠΏΡΠΎΡΡΡΠ°Π½ΡΡΠ²Π΅.
ΠΡΠ°Ρ Π½Π°Π·ΡΠ²Π°Π΅Ρ ΠΏΠ»Π°Π½Π°ΡΠ½ΡΠΌ, Π΅ΡΠ»ΠΈ ΠΎΠ½ Π΄ΠΎΠΏΡΡΠΊΠ°Π΅Ρ ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΡΡ ΡΠΊΠ»Π°Π΄ΠΊΡ Π½Π° ΠΏΠ»ΠΎΡΠΊΠΎΡΡΠΈ.
Π’Π΅ΠΎΡΠ΅ΠΌΠ° (Π΄ΠΎΠΊΠ°Π·Π°Π½ΠΎ Π² ΡΠΎΠΏΠΎΠ»ΠΎΠ³ΠΈΠΈ): Π³ΡΠ°Ρ ΠΏΠ»Π°Π½Π°ΡΠ΅Π½, Π΅ΡΠ»ΠΈ ΠΎΠ½ Π½Π΅ ΠΈΠΌΠ΅Π΅Ρ ΠΏΠΎΠ΄Π³ΡΠ°ΡΠΎΠ², ΠΈΠ·ΠΎΠΌΠΎΡΡΠ½ΡΡ
Π³ΡΠ°ΡΠ°ΠΌ K5 ΠΈ K3,3.
ΠΠ°ΡΡΡΡΡΡ, ΡΠ΅ΠΏΠΈ, ΡΠΈΠΊΠ»Ρ
ΠΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ
ΠΠ°ΡΡΡΡΡΠΎΠΌ Π² Π³ΡΠ°ΡΠ΅ G (V, E) Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠ΅ΡΠ΅Π΄ΡΡΡΠ°ΡΡΡ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ Π²Π΅ΡΡΠΈΠ½ ΠΈ ΡΠ΅Π±Π΅Ρ v1, e1, v2, e2, …, vk, ek, vk+1, Π² ΠΊΠΎΡΠΎΡΠΎΠΉ Π»ΡΠ±ΡΠ΅ Π΄Π²Π° ΡΠΎΡΠ΅Π΄Π½ΠΈΡ
ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° ΠΈΠ½ΡΠΈΠ΄Π΅Π½ΡΠ½Ρ.
ΠΡΠΎ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΏΠΎΠ΄Ρ
ΠΎΠ΄ΠΈΡ ΡΠ°ΠΊΠΆΠ΅ Π΄Π»Ρ ΠΏΡΠ΅Π²Π΄ΠΎ-, ΠΌΡΠ»ΡΡΠΈΠΈ ΠΎΡΠ³ΡΠ°ΡΠΎΠ². ΠΠ»Ρ «ΠΎΠ±ΡΡΠ½ΠΎΠ³ΠΎ» Π³ΡΠ°ΡΠ° Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΠΎ ΡΠΊΠ°Π·Π°ΡΡ ΡΠΎΠ»ΡΠΊΠΎ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ Π²Π΅ΡΡΠΈΠ½ ΠΈΠ»ΠΈ ΡΠΎΠ»ΡΠΊΠΎ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ ΡΠ΅Π±Π΅Ρ.
ΠΡΠ»ΠΈ v1=vk+1, ΡΠΎ ΠΌΠ°ΡΡΡΡΡ Π·Π°ΠΌΠΊΠ½ΡΡ, ΠΈΠ½Π°ΡΠ΅ ΠΎΡΠΊΡΡΡ.
ΠΡΠ»ΠΈ Π²ΡΠ΅ ΡΠ΅Π±ΡΠ° ΡΠ°Π·Π»ΠΈΡΠ½Ρ, ΡΠΎ ΠΌΠ°ΡΡΡΡΡ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠ΅ΠΏΡΡ. ΠΡΠ»ΠΈ Π²ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ ΡΠ΅ΠΏΠΈ ΡΠ°Π·Π»ΠΈΡΠ½Ρ, ΡΠΎ ΡΠ΅ΠΏΡ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΡΠΎΡΡΠΎΠΉ.
ΠΠ°ΠΌΠΊΠ½ΡΡΠ°Ρ ΡΠ΅ΠΏΡ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠΈΠΊΠ»ΠΎΠΌ; Π·Π°ΠΌΠΊΠ½ΡΡΠ°Ρ ΠΏΡΠΎΡΡΠ°Ρ ΡΠ΅ΠΏΡ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΡΠΎΡΡΡΠΌ ΡΠΈΠΊΠ»ΠΎΠΌ.
Π§ΠΈΡΠ»ΠΎ ΡΠΈΠΊΠ»ΠΎΠ² Π² Π³ΡΠ°ΡΠ΅ G ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ°Π΅ΡΡΡ z (G) (ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΈΠ½Π²Π°ΡΠΈΠ°Π½ΡΠΎΠΌ). ΠΡΠ°Ρ Π±Π΅Π· ΡΠΈΠΊΠ»ΠΎΠ² Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π°ΡΠΈΠΊΠ»ΠΈΡΠ΅ΡΠΊΠΈΠΌ.
ΠΠ»Ρ ΠΎΡΠ³ΡΠ°ΡΠΎΠ² ΡΠ΅ΠΏΡ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΡΡΠ΅ΠΌ, Π° ΡΠΈΠΊΠ» — ΠΊΠΎΠ½ΡΡΡΠΎΠΌ.
ΠΡΠΈΠΌΠ΅Ρ Π Π³ΡΠ°ΡΠ΅, Π΄ΠΈΠ°Π³ΡΠ°ΠΌΠΌΠ° ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΠΏΡΠΈΠ²Π΅Π΄Π΅Π½Π° Π½Π° ΡΠΈΡ. 3.10:
- 1. v1, v3,v1,v4 — ΠΌΠ°ΡΡΡΡΡ, Π½ΠΎ Π½Π΅ ΡΠ΅ΠΏΡ;
- 2. v1, v3, v5, v2, v3, v4 — ΡΠ΅ΠΏΡ, Π½ΠΎ Π½Π΅ ΠΏΡΠΎΡΡΠ°Ρ ΡΠ΅ΠΏΡ;
- 3. v1, v4, v3, v2, v5 — ΠΏΡΠΎΡΡΠ°Ρ ΡΠ΅ΠΏΡ;
- 4. v1, v3, v5, v2, v3, v4, v1- ΡΠΈΠΊΠ», Π½ΠΎ Π½Π΅ ΠΏΡΠΎΡΡΠΎΠΉ ΡΠΈΠΊΠ»;
- 5. v1, v3,v4 — ΠΏΡΠΎΡΡΠΎΠΉ ΡΠΈΠΊΠ».
Π ΠΈΡ. 3.10 ΠΠ°ΡΡΡΡΡΡ, ΡΠ΅ΠΏΠΈ, ΡΠΈΠΊΠ»Ρ
ΠΠ²Π΅ Π²Π΅ΡΡΠΈΠ½Ρ Π³ΡΠ°ΡΠ° Π½Π°Π·ΡΠ²Π°ΡΡΡΡ ΡΠ²ΡΠ·Π°Π½Π½ΡΠΌΠΈ, Π΅ΡΠ»ΠΈ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΠΌΠ°ΡΡΡΡΡ, ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡΠΈΠΉ ΡΡΠΈ Π²Π΅ΡΡΠΈΠ½Ρ. ΠΡΠ°Ρ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠ²ΡΠ·Π½ΡΠΌ, Π΅ΡΠ»ΠΈ Π»ΡΠ±Π°Ρ ΠΏΠ°ΡΠ° Π΅Π³ΠΎ Π²Π΅ΡΡΠΈΠ½ ΡΠ²ΡΠ·Π°Π½Π½Π°.
ΠΡΠ°Ρ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π΄Π΅ΡΠ΅Π²ΠΎΠΌ, Π΅ΡΠ»ΠΈ ΠΎΠ½ ΡΠ²ΡΠ·Π΅Π½ ΠΈ Π½Π΅ ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ ΡΠΈΠΊΠ»ΠΎΠ².