ΠΠ½ΠΎΠ³ΠΈΠ΅ Π·Π°Π΄Π°ΡΠΈ, Ρ ΠΊΠΎΡΠΎΡΡΠΌΠΈ ΠΏΡΠΈΡ
ΠΎΠ΄ΠΈΡΡΡ ΠΈΠΌΠ΅ΡΡ Π΄Π΅Π»ΠΎ Π² ΠΏΠΎΠ²ΡΠ΅Π΄Π½Π΅Π²Π½ΠΎΠΉ ΠΏΡΠ°ΠΊΡΠΈΠΊΠ΅, ΡΠ²Π»ΡΡΡΡΡ ΠΌΠ½ΠΎΠ³ΠΎΠ²Π°ΡΠΈΠ°Π½ΡΠ½ΡΠΌΠΈ. Π‘ΡΠ΅Π΄ΠΈ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΡΡ
Π²Π°ΡΠΈΠ°Π½ΡΠΎΠ² Π² ΡΡΠ»ΠΎΠ²ΠΈΡΡ
ΡΡΠ½ΠΎΡΠ½ΡΡ
ΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΠΉ ΠΏΡΠΈΡ
ΠΎΠ΄ΠΈΡΡΡ ΠΎΡΡΡΠΊΠΈΠ²Π°ΡΡ Π½Π°ΠΈΠ»ΡΡΡΠΈΠ΅, Π² Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠΌ ΡΠΌΡΡΠ»Π΅ ΠΏΡΠΈ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½ΠΈΡΡ
, Π½Π°Π»Π°Π³Π°Π΅ΠΌΡΡ
Π½Π° ΠΏΡΠΈΡΠΎΠ΄Π½ΡΠ΅, ΡΠΊΠΎΠ½ΠΎΠΌΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΈ ΡΠ΅Ρ
Π½ΠΎΠ»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΈΠ΅ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΠΈ. Π ΡΠ²ΡΠ·ΠΈ Ρ ΡΡΠΈΠΌ Π²ΠΎΠ·Π½ΠΈΠΊΠ»Π° Π½Π΅ΠΎΠ±Ρ
ΠΎΠ΄ΠΈΠΌΠΎΡΡΡ ΠΏΡΠΈΠΌΠ΅Π½ΡΡΡ Π΄Π»Ρ Π°Π½Π°Π»ΠΈΠ·Π° ΠΈ ΡΠΈΠ½ΡΠ΅Π·Π° ΡΠΊΠΎΠ½ΠΎΠΌΠΈΡΠ΅ΡΠΊΠΈΡ
ΡΠΈΡΡΠ°ΡΠΈΠΉ ΠΈ ΡΠΈΡΡΠ΅ΠΌ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ ΠΈ ΡΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΡ ΡΠ΅Ρ
Π½ΠΈΠΊΡ.
ΠΠ°ΠΊ Π² ΡΠ°ΠΌΠΎΠΉ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠ΅, ΡΠ°ΠΊ ΠΈ Π² Π΅Π΅ ΠΏΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡΡ
ΡΠΈΡΠΎΠΊΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡΡΡ Π³ΡΠ°ΡΡ. Π’Π΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ² Π΄Π°ΡΡ ΠΈΡΠΊΠ»ΡΡΠΈΡΠ΅Π»ΡΠ½ΠΎ ΡΠ΄ΠΎΠ±Π½ΡΠΉ Π°ΠΏΠΏΠ°ΡΠ°Ρ Π΄Π»Ρ ΠΌΠΎΠ΄Π΅Π»ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΡΡΡΡΠΊΡΡΡΠ½ΡΡ
ΡΠ²ΠΎΠΉΡΡΠ² ΡΠ°Π·Π»ΠΈΡΠ½ΡΡ
ΡΠΈΡΡΠ΅ΠΌ ΠΈ ΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΠΉ ΠΌΠ΅ΠΆΠ΄Ρ ΠΎΠ±ΡΠ΅ΠΊΡΠ°ΠΌΠΈ ΡΠ°Π·Π½ΠΎΠΉ ΠΏΡΠΈΡΠΎΠ΄Ρ, Π² ΡΠΎΠΌ ΡΠΈΡΠ»Π΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ½ΡΡ
ΠΌΠΎΠ΄Π΅Π»Π΅ΠΉ.
Π’Π΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ² — ΡΠ°Π·Π΄Π΅Π» Π΄ΠΈΡΠΊΡΠ΅ΡΠ½ΠΎΠΉ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠΈ, ΠΎΡΠΎΠ±Π΅Π½Π½ΠΎΡΡΡΡ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΡΠ²Π»ΡΠ΅ΡΡΡ Π³Π΅ΠΎΠΌΠ΅ΡΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΏΠΎΠ΄Ρ
ΠΎΠ΄ ΠΊ ΠΈΠ·ΡΡΠ΅Π½ΠΈΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ². ΠΠ΅ΡΠ²ΡΠ΅ Π·Π°Π΄Π°ΡΠΈ ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² Π±ΡΠ»ΠΈ ΡΠ²ΡΠ·Π°Π½Ρ Ρ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ΠΌ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΡ
ΡΠ°Π·Π²Π»Π΅ΠΊΠ°ΡΠ΅Π»ΡΠ½ΡΡ
Π·Π°Π΄Π°Ρ ΠΈ Π³ΠΎΠ»ΠΎΠ²ΠΎΠ»ΠΎΠΌΠΎΠΊ (Π·Π°Π΄Π°ΡΠ° ΠΎ ΠΡΠ½ΠΈΠ½Π³ΡΠ±Π΅ΡΠ³ΡΠΊΠΈΡ
ΠΌΠΎΡΡΠ°Ρ
, Π·Π°Π΄Π°ΡΠ° ΠΎ ΡΠ°ΡΡΡΠ°Π½ΠΎΠ²ΠΊΠ΅ ΡΠ΅ΡΠ·Π΅ΠΉ Π½Π° ΡΠ°Ρ
ΠΌΠ°ΡΠ½ΠΎΠΉ Π΄ΠΎΡΠΊΠ΅, Π·Π°Π΄Π°ΡΠΈ ΠΎ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΊΠ°Ρ
, Π·Π°Π΄Π°ΡΠ° ΠΎ ΠΊΡΡΠ³ΠΎΡΠ²Π΅ΡΠ½ΠΎΠΌ ΠΏΡΡΠ΅ΡΠ΅ΡΡΠ²ΠΈΠΈ ΠΈ Π΄Ρ.). Π ΠΎΠ±ΡΠ΅ΠΌ ΡΠΌΡΡΠ»Π΅ Π³ΡΠ°Ρ (ΡΠ΅ΡΡ) G = (V, E) ΡΠΎΡΡΠΎΠΈΡ ΠΈΠ· ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ³ΠΎ, Π½Π΅ΠΏΡΡΡΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° m Π²Π΅ΡΡΠΈΠ½ (m ≤ 1) ΠΈ ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° n Π½Π΅ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½ΡΡ
ΠΏΠ°Ρ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² [u, v] (n ≥ 0), Π½Π°Π·ΡΠ²Π°Π΅ΠΌΡΡ
ΡΡΠ±ΡΠ°ΠΌΠΈ Π³ΡΠ°ΡΠ° G. Π ΡΡΡΠΎΠ³ΠΎΠΌ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠΈ Π³ΡΠ°ΡΠΎΠΌ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠ°ΠΊΠ°Ρ ΠΏΠ°ΡΠ° ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ² G = {R, V}, Π³Π΄Π΅ V Π΅ΡΡΡ ΠΏΠΎΠ΄ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π»ΡΠ±ΠΎΠ³ΠΎ ΡΡΡΡΠ½ΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π°, Π° R — ΠΏΠΎΠ΄ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ VxV. Π’Π΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ² Π½Π°Ρ
ΠΎΠ΄ΠΈΡ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π² Π³Π΅ΠΎΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΎΠ½Π½ΡΡ
ΡΠΈΡΡΠ΅ΠΌΠ°Ρ
(ΠΠΠ‘). Π‘ΡΡΠ΅ΡΡΠ²ΡΡΡΠΈΠ΅ ΠΈΠ»ΠΈ Π²Π½ΠΎΠ²Ρ ΠΏΡΠΎΠ΅ΠΊΡΠΈΡΡΠ΅ΠΌΡΠ΅ Π΄ΠΎΠΌΠ°, ΡΠΎΠΎΡΡΠΆΠ΅Π½ΠΈΡ, ΠΊΠ²Π°ΡΡΠ°Π»Ρ ΠΈ Ρ. ΠΏ. ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°ΡΡΡΡ ΠΊΠ°ΠΊ Π²Π΅ΡΡΠΈΠ½Ρ, Π° ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡΠΈΠ΅ ΠΈΡ
Π΄ΠΎΡΠΎΠ³ΠΈ, ΠΈΠ½ΠΆΠ΅Π½Π΅ΡΠ½ΡΠ΅ ΡΠ΅ΡΠΈ, Π»ΠΈΠ½ΠΈΠΈ ΡΠ»Π΅ΠΊΡΡΠΎΠΏΠ΅ΡΠ΅Π΄Π°Ρ ΠΈ Ρ. ΠΏ. — ΠΊΠ°ΠΊ ΡΡΠ±ΡΠ°. ΠΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΡΠ°Π·Π»ΠΈΡΠ½ΡΡ
Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΠΉ, ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΠΌΡΡ
Π½Π° ΡΠ°ΠΊΠΎΠΌ Π³ΡΠ°ΡΠ΅, ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π½Π°ΠΉΡΠΈ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΉ ΠΎΠ±ΡΠ΅Π·Π΄Π½ΠΎΠΉ ΠΏΡΡΡ ΠΈΠ»ΠΈ Π±Π»ΠΈΠΆΠ°ΠΉΡΠΈΠΉ ΠΏΡΠΎΠ΄ΡΠΊΡΠΎΠ²ΡΠΉ ΠΌΠ°Π³Π°Π·ΠΈΠ½, ΡΠΏΠ»Π°Π½ΠΈΡΠΎΠ²Π°ΡΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΠΌΠ°ΡΡΡΡΡ.
ΠΡΠ°ΡΡ ΠΌΠΎΠ³ΡΡ Π±ΡΡΡ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½Ρ Π² ΠΠΠ ΠΌΠ°ΡΡΠΈΡΠ΅ΠΉ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ, ΠΈΠ½ΡΠΈΠ΄Π΅Π½ΡΠ½ΠΎΡΡΠΈ ΠΈΠ»ΠΈ ΠΌΠ°ΡΡΠΈΡΠ΅ΠΉ Π²Π΅ΡΠΎΠ². Π‘ΡΡΠ΅ΡΡΠ²ΡΡΡ ΡΠ°ΠΊΠΈΠ΅ ΠΌΠΎΠ΄Π΅Π»ΠΈ Π·Π°Π΄Π°Ρ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ: ΠΌΠΎΠ΄Π΅Π»Ρ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ ΡΡΠΈΠ»ΠΈΠΉ (ΠΈΠ½Π²Π΅ΡΡΠΈΡΠΈΠΉ), ΠΌΠΎΠ΄Π΅Π»Ρ Π·Π°ΠΌΠ΅Π½Ρ ΠΎΠ±ΠΎΡΡΠ΄ΠΎΠ²Π°Π½ΠΈΡ, ΠΏΠΎΠΈΡΠΊ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π³ΠΎ ΠΏΡΡΠΈ Π½Π° Π³ΡΠ°ΡΠ΅, Π·Π°Π΄Π°ΡΠΈ ΠΊΠ°Π»Π΅Π½Π΄Π°ΡΠ½ΠΎΠ³ΠΎ ΠΏΠ»Π°Π½ΠΈΡΠΎΠ²Π°Π½ΠΈΡ, ΠΏΠΎΠΈΡΠΊ ΠΊΡΠΈΡΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΏΡΡΠΈ, Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΠ΅ ΡΠ°Π½Π½ΠΈΡ
ΠΈ ΠΏΠΎΠ·Π΄Π½ΠΈΡ
ΡΡΠΎΠΊΠΎΠ² Π½Π°ΡΡΡΠΏΠ»Π΅Π½ΠΈΡ ΡΠΎΠ±ΡΡΠΈΠΉ.
Π¦Π΅Π»Ρ ΠΊΡΡΡΠΎΠ²ΠΎΠΉ ΡΠ°Π±ΠΎΡΡ — ΡΠ΅ΡΠΈΡΡ Π·Π°Π΄Π°ΡΡ ΠΎ ΠΆΠ°Π΄Π½ΠΎΠΌ «Π°Π»Π³ΠΎΡΠΈΡΠΌΠ΅», ΠΏΠΎΡΠ²ΡΡΠ΅Π½Π½ΠΎΠΉ Π½Π°Ρ
ΠΎΠΆΠ΄Π΅Π½ΠΈΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΉ ΡΡΠΌΠΌΡ Π΄Π»ΠΈΠ½ ΠΌΠ΅ΠΆΠ΄Ρ Π΅Π³ΠΎ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ ΠΡΠΈΠΌΠ°ΠΡΠ°ΡΠΊΠ°Π»Π° ΡΡΠ΅Π΄ΡΡΠ²Π°ΠΌΠΈ SWI-Prolog.