令和2年度 III-10

解説

この問題で問われていること

制御フローグラフで、支配関係を用いてバック辺(ループの戻り辺)を判別する問題。

解き方

① バック辺(m,n)=終点nが始点mを支配する辺(入口からmへ行くどの経路も必ずnを通る)。ループの戻り辺でも、nを通らずにmへ行ける道があればバック辺ではない
② (3,4): 3へは4→5→3でしか行けない → 4が3を支配。(7,6): 7へは6からしか行けない → OK。(10,9): 10へは8→10で9を通らずに行ける → バック辺ではない
③ (3,4)と(7,6)の①

正解が正しい理由

バック辺は、辺(m,n)で、終点nが始点mを支配する(入口から、mへ到達するすべての経路がnを通る)辺である。辺は、(1,2)、(2,4)、(2,6)、(3,4)、(4,5)、(5,3)、(5,8)、(6,7)、(7,6)、(6,8)、(8,9)、(8,10)、(9,10)、(10,9)、(10,11)。ループ3→4→5→3では、節点3への経路は5経由のみ、5への経路は4経由のみなので、4が3を支配し、(3,4)がバック辺。ループ6→7→6では、7への経路は6経由のみなので、6が7を支配し、(7,6)がバック辺。一方、(10,9)は、節点10へは、8から直接(8,10)でも到達でき、9を通らない経路があるため、9は10を支配しない。したがって(10,9)はバック辺ではない。バック辺は(3,4)と(7,6)で、①が正しい。

各選択肢について

• ① (3,4)と(7,6)は、いずれも支配関係を満たすバック辺で、すべてのバック辺を含んでいる。これが正答。
• ② (4,5)と(6,7)は、ループの順方向の辺で、バック辺ではない。
• ③ (2,4)、(2,6)、(8,9)は、ループへの入口の辺で、バック辺ではない。
• ④ (3,4)、(7,6)は正しいが、(10,9)は、9が10を支配しないため、バック辺ではない。
• ⑤ (4,5)と(6,7)はバック辺ではなく、(10,9)もバック辺ではない。

覚えるべきポイント

バック辺=終点が始点を支配する辺(自然ループの戻り辺)。ループの入口が複数ある(非可約な)部分では、深さ優先の戻り辺であっても、バック辺にはならない。