Π£ΡΡΡΡ Π½Π° ΠΏΠ΅ΡΠ²ΠΎΠΌ ΠΊΡΡΡΠ΅ Π² ΠΠ΅ΡΠΌΠ°Π½ΠΈΠΈ Π½Π° Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½ΠΈΠΈ “Data Science“, Π½Π°ΡΠ°Π» ΠΏΠΎΠ΄Π³ΠΎΡΠΎΠ²ΠΊΡ ΠΊ ΡΠΊΠ·Π°ΠΌΠ΅Π½Π°ΠΌ ΠΏΠΎ ΠΏΡΠ΅Π΄ΠΌΠ΅ΡΡ ΠΠ»Π³ΠΎΡΠΈΡΠΌΡ ΠΈ ΡΡΡΡΠΊΡΡΡΡ Π΄Π°Π½Π½ΡΡ
, ΠΏΠ΅ΡΠ²ΡΠ΅ ΠΏΡΠΎΠ±Π»Π΅ΠΌΡ Π²ΠΎΠ·Π½ΠΈΠΊΠ»ΠΈ Ρ ΡΠ΅ΠΌΠΎΠΉ Π³ΡΠ°ΡΠΎΠ². ΠΡΠ»ΠΈ Ρ ΠΠ°Ρ Π½Π°ΠΉΠ΄Π΅ΡΡΡ Π²ΡΠ΅ΠΌΡ, Ρ
ΠΎΡΠ΅Π» Π±Ρ ΠΏΡΠΎΠ²Π΅ΡΡΠΈ Π·Π°Π½ΡΡΠΈΠ΅ ΡΠ΅Π³ΠΎΠ΄Π½Ρ ΠΈΠ»ΠΈ Π·Π°Π²ΡΡΠ° ΠΠ° ΠΎΡΠΈΠ±ΠΊΠΈ Π² ΡΠ΅ΡΠΌΠΈΠ½ΠΎΠ»ΠΎΠ³ΠΈΠΈ ΠΈΠ·Π²ΠΈΠ½ΡΡΡΡ, ΠΏΠ΅ΡΠ΅Π²ΠΎΠ΄ΠΈΠ» Π΄ΠΎΡΠ»ΠΎΠ²Π½ΠΎ. ΠΡΠΆΠ½Π° ΠΏΠΎΠΌΠΎΡΡ Ρ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ΠΌ Π·Π°Π΄Π°Ρ: 1. a) Π Π΅Π°Π»ΠΈΠ·ΡΠΉΡΠ΅ ΠΊΠ»Π°ΡΡ DirectedGraph. Π£Π·Π»Π°ΠΌΠΈ Π³ΡΠ°ΡΠ° Π΄ΠΎΠ»ΠΆΠ½Ρ Π±ΡΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΡΠΈΠΏΠ° integer. ΠΠ½Π΅Π΄ΡΠΈΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ ΠΊΠΎΠ½ΡΡΡΡΠΊΡΠΎΡΡ ΠΈ ΠΌΠ΅ΡΠΎΠ΄Ρ. - public DirectedGraph() Π΄Π»Ρ ΡΠΎΠ·Π΄Π°Π½ΠΈΡ ΠΏΡΡΡΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ°, - public DirectedGraph(Integer n) Π΄Π»Ρ ΡΠΎΠ·Π΄Π°Π½ΠΈΡ Π³ΡΠ°ΡΠ° Ρ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ 1, . . . , n Π±Π΅Π· ΠΊΡΠ°Π΅Π², - public void addVertex(Integer i) Π΄Π»Ρ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΡ Π²Π΅ΡΡΠΈΠ½Ρ ? i, - public void addEdge(Integer i, Integer j) Π΄Π»Ρ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΡ ΡΠ΅Π±ΡΠ° ( ? i, j), - public void deleteEdge(Integer i, Integer j) Π΄Π»Ρ ΡΠ΄Π°Π»Π΅Π½ΠΈΡ ΡΠ΅Π±ΡΠ° (i, j). b) Π Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°ΡΡ ΠΊΠ»Π°ΡΡ DfsAlgos, ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠΈΠΉ ΠΌΠ΅ΡΠΎΠ΄ public LinkedList topSort(DirectedGraph g) ΠΡΠΎΡ ΠΌΠ΅ΡΠΎΠ΄ Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² Π²ΡΠ²ΠΎΠ΄Π΅ ΡΠΎΠΏΠΎΠ»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π΄Π»Ρ ? g c ΠΏΠΎΠΌΠΎΡΡΡ Dfs, Π΅ΡΠ»ΠΈ g ΡΠ²Π»ΡΠ΅ΡΡΡ Π°ΡΠΈΠΊΠ»ΠΈΡΠ΅ΡΠΊΠΈΠΌ. Π ΠΏΡΠΎΡΠΈΠ²Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ return null. c) ΠΠΎΠ±Π°Π²ΡΡΠ΅ Π² ΡΠ²ΠΎΠΉ ΠΊΠ»Π°ΡΡ DfsAlgos.ΠΌΠ΅ΡΠΎΠ΄ ? public LinkedList detectCycle(DirectedGraph g) . ΠΡΠΎΡ ΠΌΠ΅ΡΠΎΠ΄ Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² ΡΠΎΠΌ, ΡΡΠΎΠ±Ρ Π½Π°ΠΉΡΠΈ ΠΈ Π²ΡΠ²Π΅ΡΡΠΈ ΡΠΈΠΊΠ» Π΄Π»Ρ ? g Ρ ΠΏΠΎΠΌΠΎΡΡΡ Dfs ΠΈ Π²ΡΠ²Π΅ΡΡΠΈ Π΅Π³ΠΎ Π² Π²ΠΈΠ΄Π΅ ΡΠΏΠΈΡΠΊΠ° ΡΠ·Π»ΠΎΠ². ΠΡΠ»ΠΈ g ΡΠ²Π»ΡΠ΅ΡΡΡ Π°ΡΠΈΠΊΠ»ΠΈΡΠ΅ΡΠΊΠΈΠΌ, ΡΠΎ Π²ΡΠ²ΠΎΠ΄ΠΈΡΡΡ null. 2. a) Π Π½Π΅Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½Π½ΠΎΠΌ Π³ΡΠ°ΡΠ΅ G ΠΌΡ Ρ
ΠΎΡΠΈΠΌ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ Π²ΡΠ΅ ΡΠ·Π»Ρ, Π΄ΠΎΡΡΠΈΠΆΠΈΠΌΡΠ΅ ΠΈΠ· s .ΠΠ»Ρ ΡΠΎΠ³ΠΎ ΡΡΠΎΠ±Ρ ΡΠΎΡ
ΡΠ°Π½ΠΈΡΡ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ Π§ΡΠΎΠ±Ρ ΡΡΠΊΠΎΠ½ΠΎΠΌΠΈΡΡ Π½Π° ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΏΠΎΠΈΡΠΊΠ° Π² ΡΠΈΡΠΈΠ½Ρ(Bfs), ΠΌΡ Ρ
ΠΎΡΠ΅Π»ΠΈ Π±Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΡΠΆΠ΅ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΠΈΡΠΊΠ° Π² Π³Π»ΡΠ±ΠΈΠ½Ρ (Dfs). Π£ΠΊΠ°ΠΆΠΈΡΠ΅, ΠΊΠ°ΠΊ G ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ Π² ΠΏΠΎΠ΄Ρ
ΠΎΠ΄ΡΡΠΈΠΉ Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½Π½ΡΠΉ Π³ΡΠ°Ρ G0 ΡΠ°ΠΊ, ΡΡΠΎ ΠΏΠΎΠΈΡΠΊ Π² Π³Π»ΡΠ±ΠΈΠ½Ρ ?(Dfs) Π½Π° G0 ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΡ ΠΊ ΠΆΠ΅Π»Π°Π΅ΠΌΠΎΠΌΡ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ. ? Π±) ΠΠ°Π½ Π½Π΅Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½Π½ΡΠΉ Π·Π²Π΅Π·Π΄ΡΠ°ΡΡΠΉ Π³ΡΠ°Ρ Ρ n ΡΠ·Π»Π°ΠΌΠΈ. ΠΡΠΎ Π΄Π΅ΡΠ΅Π²ΠΎ Ρ ΡΠΎΠ²Π½ΠΎ n- 1 ΡΠ΅Π±ΡΠ°ΠΌΠΈ, Π³Π΄Π΅ ΡΠ·Π΅Π» “u“ ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½ ΡΠ΅Π±ΡΠΎΠΌ ΡΠΎ Π²ΡΠ΅ΠΌΠΈ ΡΠ·Π»Π°ΠΌΠΈ Π² V \ {u}. ΠΠΏΠΈΡΠΈΡΠ΅, ΠΊΠ°ΠΊ ΠΌΠΎΠΆΠ½ΠΎ Π½Π°ΠΏΡΠ°Π²ΠΈΡΡ ΡΠ΅Π±ΡΠ° Π² G ΡΠ°ΠΊ, ΡΡΠΎΠ±Ρ ΡΠΈΡΠ»ΠΎ ΠΏΠ°Ρ ΡΠ²ΡΠ·Π°Π½Π½ΡΡ
ΡΠ·Π»ΠΎΠ² Π±ΡΠ»ΠΎ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ. ΠΏΠ°ΡΠ° ΡΠ·Π»ΠΎΠ² (u, v) ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½Π°, Π΅ΡΠ»ΠΈ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½Π½ΡΠΉ ΠΏΡΡΡ ΠΈΠ· u Π² v. “ΠΠ΅ΡΠ΅Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½ΠΈΠ΅“ Π½Π΅Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½Π½ΠΎΠ³ΠΎ ΡΠ΅Π±ΡΠ° {u, v} - ΡΡΠΎ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡ, Π² ΠΊΠΎΡΠΎΡΠΎΠΉ {u, v} Π·Π°ΠΌΠ΅Π½ΡΠ΅ΡΡΡ Π»ΠΈΠ±ΠΎ Π½Π° (u, v), Π»ΠΈΠ±ΠΎ Π½Π° (v, u). 3. ΠΡ ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°Π΅ΠΌ Π½Π°Π±ΠΎΡΡ I ΠΏΠ°Ρ Π½Π°ΡΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΈ ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ³ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ (a, b), ΠΊΠΎΡΠΎΡΡΠ΅ ΠΌΠΎΠ³ΡΡ Π±ΡΡΡ ΠΏΠΎΠ»ΡΡΠ΅Π½Ρ Ρ ΠΏΠΎΠΌΠΎΡΡΡ ΠΏΠΎΠΈΡΠΊΠ° Π² Π³Π»ΡΠ±ΠΈΠ½Ρ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, Π΅ΡΠ»ΠΈ (a, b) ? I, ΡΠΎ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΡΠ·Π΅Π» Π² G, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ? ΠΏΠΎΠΈΡΠΊ Π² Π³Π»ΡΠ±ΠΈΠ½Ρ Π΄Π°Π» Π½Π°ΡΠ°Π»ΡΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ a ΠΈ ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ b. a) ΠΡΡΡΡ I = {(i, 2n - i + 1) | 1 <= i <= n}. Π‘ΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ Π»ΠΈ Π³ΡΠ°Ρ Ρ n ΡΠ·Π»Π°ΠΌΠΈ, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Π½Π°Π±ΠΎΡ Π½Π°ΡΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΈ ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ³ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ, ΡΠ³Π΅Π½Π΅ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ ΠΏΠΎΠΈΡΠΊΠΎΠΌ Π² Π³Π»ΡΠ±ΠΈΠ½Ρ, Π²ΡΠ΅Π³Π΄Π° ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΠ΅Ρ I, Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎ ΠΎΡ ΡΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Ρ ΡΠΏΠΈΡΠΊΠΈ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ ΠΈ Π² ΠΊΠ°ΠΊΠΎΠΌ ΠΏΠΎΡΡΠ΄ΠΊΠ΅ ΠΏΠΎΡΠ΅ΡΠ°ΡΡΡΡ ΡΠ·Π»Ρ Π² DFS(). b) ΠΡΡΡΡ I = {(i, 2n - i + 1) | 1 <= i <= n} ΠΈ I'= {(2i - 1, 2i) | 1 <= i <= n}. ΠΡΡΡ Π»ΠΈ Π³ΡΠ°Ρ, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Π³Π»ΡΠ±ΠΈΠ½Π½ΡΠΉ ΠΏΠΎΠΈΡΠΊ Π΄ΠΎΡΡΠΈΠ³Π½Π΅Ρ I ΠΈ I' ΠΠ° ΠΎΡΠΈΠ±ΠΊΠΈ Π² ΡΠ΅ΡΠΌΠΈΠ½ΠΎΠ»ΠΎΠ³ΠΈΠΈ ΠΈΠ·Π²ΠΈΠ½ΡΡΡΡ, ΠΏΠ΅ΡΠ΅Π²ΠΎΠ΄ΠΈΠ» Π΄ΠΎΡΠ»ΠΎΠ²Π½ΠΎ. Π£ΡΡΡΡ Π½Π° ΠΏΠ΅ΡΠ²ΠΎΠΌ ΠΊΡΡΡΠ΅ Π² ΠΠ΅ΡΠΌΠ°Π½ΠΈΠΈ Π½Π° Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½ΠΈΠΈ “Data Science“, Π½Π°ΡΠ°Π» ΠΏΠΎΠ΄Π³ΠΎΡΠΎΠ²ΠΊΡ ΠΊ ΡΠΊΠ·Π°ΠΌΠ΅Π½Π°ΠΌ ΠΏΠΎ ΠΏΡΠ΅Π΄ΠΌΠ΅ΡΡ ΠΠ»Π³ΠΎΡΠΈΡΠΌΡ ΠΈ ΡΡΡΡΠΊΡΡΡΡ Π΄Π°Π½Π½ΡΡ
, ΠΏΠ΅ΡΠ²ΡΠ΅ ΠΏΡΠΎΠ±Π»Π΅ΠΌΡ Π²ΠΎΠ·Π½ΠΈΠΊΠ»ΠΈ Ρ ΡΠ΅ΠΌΠΎΠΉ Π³ΡΠ°ΡΠΎΠ². ΠΡΠ»ΠΈ Ρ ΠΠ°Ρ Π½Π°ΠΉΠ΄Π΅ΡΡΡ Π²ΡΠ΅ΠΌΡ, Ρ
ΠΎΡΠ΅Π» Π±Ρ ΠΏΡΠΎΠ²Π΅ΡΡΠΈ Π·Π°Π½ΡΡΠΈΠ΅ ΡΠ΅Π³ΠΎΠ΄Π½Ρ ΠΈΠ»ΠΈ Π·Π°Π²ΡΡΠ°. ΠΡΠΆΠ½Π° ΠΏΠΎΠΌΠΎΡΡ Ρ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ΠΌ Π·Π°Π΄Π°Ρ: 1. a) Π Π΅Π°Π»ΠΈΠ·ΡΠΉΡΠ΅ ΠΊΠ»Π°ΡΡ DirectedGraph. Π£Π·Π»Π°ΠΌΠΈ Π³ΡΠ°ΡΠ° Π΄ΠΎΠ»ΠΆΠ½Ρ Π±ΡΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΡΠΈΠΏΠ° integer. ΠΠ½Π΅Π΄ΡΠΈΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ ΠΊΠΎΠ½ΡΡΡΡΠΊΡΠΎΡΡ ΠΈ ΠΌΠ΅ΡΠΎΠ΄Ρ. - public DirectedGraph() Π΄Π»Ρ ΡΠΎΠ·Π΄Π°Π½ΠΈΡ ΠΏΡΡΡΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ°, - public DirectedGraph(Integer n) Π΄Π»Ρ ΡΠΎΠ·Π΄Π°Π½ΠΈΡ Π³ΡΠ°ΡΠ° Ρ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ 1, . . . , n Π±Π΅Π· ΠΊΡΠ°Π΅Π², - public void addVertex(Integer i) Π΄Π»Ρ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΡ Π²Π΅ΡΡΠΈΠ½Ρ ? i, - public void addEdge(Integer i, Integer j) Π΄Π»Ρ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΡ ΡΠ΅Π±ΡΠ° ( ? i, j), - public void deleteEdge(Integer i, Integer j) Π΄Π»Ρ ΡΠ΄Π°Π»Π΅Π½ΠΈΡ ΡΠ΅Π±ΡΠ° (i, j). b) Π Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°ΡΡ ΠΊΠ»Π°ΡΡ DfsAlgos, ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠΈΠΉ ΠΌΠ΅ΡΠΎΠ΄ public LinkedList topSort(DirectedGraph g) ΠΡΠΎΡ ΠΌΠ΅ΡΠΎΠ΄ Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² Π²ΡΠ²ΠΎΠ΄Π΅ ΡΠΎΠΏΠΎΠ»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π΄Π»Ρ ? g c ΠΏΠΎΠΌΠΎΡΡΡ Dfs, Π΅ΡΠ»ΠΈ g ΡΠ²Π»ΡΠ΅ΡΡΡ Π°ΡΠΈΠΊΠ»ΠΈΡΠ΅ΡΠΊΠΈΠΌ. Π ΠΏΡΠΎΡΠΈΠ²Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ return null. c) ΠΠΎΠ±Π°Π²ΡΡΠ΅ Π² ΡΠ²ΠΎΠΉ ΠΊΠ»Π°ΡΡ DfsAlgos.ΠΌΠ΅ΡΠΎΠ΄ ? public LinkedList detectCycle(DirectedGraph g) . ΠΡΠΎΡ ΠΌΠ΅ΡΠΎΠ΄ Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² ΡΠΎΠΌ, ΡΡΠΎΠ±Ρ Π½Π°ΠΉΡΠΈ ΠΈ Π²ΡΠ²Π΅ΡΡΠΈ ΡΠΈΠΊΠ» Π΄Π»Ρ ? g Ρ ΠΏΠΎΠΌΠΎΡΡΡ Dfs ΠΈ Π²ΡΠ²Π΅ΡΡΠΈ Π΅Π³ΠΎ Π² Π²ΠΈΠ΄Π΅ ΡΠΏΠΈΡΠΊΠ° ΡΠ·Π»ΠΎΠ². ΠΡΠ»ΠΈ g ΡΠ²Π»ΡΠ΅ΡΡΡ Π°ΡΠΈΠΊΠ»ΠΈΡΠ΅ΡΠΊΠΈΠΌ, ΡΠΎ Π²ΡΠ²ΠΎΠ΄ΠΈΡΡΡ null. 2. a) Π Π½Π΅Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½Π½ΠΎΠΌ Π³ΡΠ°ΡΠ΅ G ΠΌΡ Ρ
ΠΎΡΠΈΠΌ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ Π²ΡΠ΅ ΡΠ·Π»Ρ, Π΄ΠΎΡΡΠΈΠΆΠΈΠΌΡΠ΅ ΠΈΠ· s .ΠΠ»Ρ ΡΠΎΠ³ΠΎ ΡΡΠΎΠ±Ρ ΡΠΎΡ
ΡΠ°Π½ΠΈΡΡ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ Π§ΡΠΎΠ±Ρ ΡΡΠΊΠΎΠ½ΠΎΠΌΠΈΡΡ Π½Π° ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΏΠΎΠΈΡΠΊΠ° Π² ΡΠΈΡΠΈΠ½Ρ(Bfs), ΠΌΡ Ρ
ΠΎΡΠ΅Π»ΠΈ Π±Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΡΠΆΠ΅ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΠΈΡΠΊΠ° Π² Π³Π»ΡΠ±ΠΈΠ½Ρ (Dfs). Π£ΠΊΠ°ΠΆΠΈΡΠ΅, ΠΊΠ°ΠΊ G ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ Π² ΠΏΠΎΠ΄Ρ
ΠΎΠ΄ΡΡΠΈΠΉ Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½Π½ΡΠΉ Π³ΡΠ°Ρ G0 ΡΠ°ΠΊ, ΡΡΠΎ ΠΏΠΎΠΈΡΠΊ Π² Π³Π»ΡΠ±ΠΈΠ½Ρ ?(Dfs) Π½Π° G0 ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΡ ΠΊ ΠΆΠ΅Π»Π°Π΅ΠΌΠΎΠΌΡ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ. ? Π±) ΠΠ°Π½ Π½Π΅Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½Π½ΡΠΉ Π·Π²Π΅Π·Π΄ΡΠ°ΡΡΠΉ Π³ΡΠ°Ρ Ρ n ΡΠ·Π»Π°ΠΌΠΈ. ΠΡΠΎ Π΄Π΅ΡΠ΅Π²ΠΎ Ρ ΡΠΎΠ²Π½ΠΎ n- 1 ΡΠ΅Π±ΡΠ°ΠΌΠΈ, Π³Π΄Π΅ ΡΠ·Π΅Π» “u“ ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½ ΡΠ΅Π±ΡΠΎΠΌ ΡΠΎ Π²ΡΠ΅ΠΌΠΈ ΡΠ·Π»Π°ΠΌΠΈ Π² V \ {u}. ΠΠΏΠΈΡΠΈΡΠ΅, ΠΊΠ°ΠΊ ΠΌΠΎΠΆΠ½ΠΎ Π½Π°ΠΏΡΠ°Π²ΠΈΡΡ ΡΠ΅Π±ΡΠ° Π² G ΡΠ°ΠΊ, ΡΡΠΎΠ±Ρ ΡΠΈΡΠ»ΠΎ ΠΏΠ°Ρ ΡΠ²ΡΠ·Π°Π½Π½ΡΡ
ΡΠ·Π»ΠΎΠ² Π±ΡΠ»ΠΎ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ. ΠΏΠ°ΡΠ° ΡΠ·Π»ΠΎΠ² (u, v) ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½Π°, Π΅ΡΠ»ΠΈ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½Π½ΡΠΉ ΠΏΡΡΡ ΠΈΠ· u Π² v. “ΠΠ΅ΡΠ΅Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½ΠΈΠ΅“ Π½Π΅Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½Π½ΠΎΠ³ΠΎ ΡΠ΅Π±ΡΠ° {u, v} - ΡΡΠΎ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡ, Π² ΠΊΠΎΡΠΎΡΠΎΠΉ {u, v} Π·Π°ΠΌΠ΅Π½ΡΠ΅ΡΡΡ Π»ΠΈΠ±ΠΎ Π½Π° (u, v), Π»ΠΈΠ±ΠΎ Π½Π° (v, u). 3. ΠΡ ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°Π΅ΠΌ Π½Π°Π±ΠΎΡΡ I ΠΏΠ°Ρ Π½Π°ΡΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΈ ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ³ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ (a, b), ΠΊΠΎΡΠΎΡΡΠ΅ ΠΌΠΎΠ³ΡΡ Π±ΡΡΡ ΠΏΠΎΠ»ΡΡΠ΅Π½Ρ Ρ ΠΏΠΎΠΌΠΎΡΡΡ ΠΏΠΎΠΈΡΠΊΠ° Π² Π³Π»ΡΠ±ΠΈΠ½Ρ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, Π΅ΡΠ»ΠΈ (a, b) ? I, ΡΠΎ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΡΠ·Π΅Π» Π² G, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ? ΠΏΠΎΠΈΡΠΊ Π² Π³Π»ΡΠ±ΠΈΠ½Ρ Π΄Π°Π» Π½Π°ΡΠ°Π»ΡΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ a ΠΈ ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ b. a) ΠΡΡΡΡ I = {(i, 2n - i + 1) | 1 <= i <= n}. Π‘ΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ Π»ΠΈ Π³ΡΠ°Ρ Ρ n ΡΠ·Π»Π°ΠΌΠΈ, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Π½Π°Π±ΠΎΡ Π½Π°ΡΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΈ ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ³ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ, ΡΠ³Π΅Π½Π΅ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ ΠΏΠΎΠΈΡΠΊΠΎΠΌ Π² Π³Π»ΡΠ±ΠΈΠ½Ρ, Π²ΡΠ΅Π³Π΄Π° ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΠ΅Ρ I, Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎ ΠΎΡ ΡΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Ρ ΡΠΏΠΈΡΠΊΠΈ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ ΠΈ Π² ΠΊΠ°ΠΊΠΎΠΌ ΠΏΠΎΡΡΠ΄ΠΊΠ΅ ΠΏΠΎΡΠ΅ΡΠ°ΡΡΡΡ ΡΠ·Π»Ρ Π² DFS(). b) ΠΡΡΡΡ I = {(i, 2n - i + 1) | 1 <= i <= n} ΠΈ I'= {(2i - 1, 2i) | 1 <= i <= n}. ΠΡΡΡ Π»ΠΈ Π³ΡΠ°Ρ, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Π³Π»ΡΠ±ΠΈΠ½Π½ΡΠΉ ΠΏΠΎΠΈΡΠΊ Π΄ΠΎΡΡΠΈΠ³Π½Π΅Ρ I ΠΈ I'.