【国家一般職・令和４年度・Ｎｏ．１８】一筆書き要素を含んだ経路問題（荷物の配達）【行政・大卒区分】
国家一般職、令和４年度、No.18の問題です。
いわゆる経路問題で『配達できる荷物の最大個数』が問われています。
経路問題については、『一筆書き問題の考え方』を応用することによって効率的に問題を解くことができます。
奇点・偶点とは
問題を解く前の前提知識として『奇点』・『偶点』というものを解説します。
上図に示すとおり、『奇点』とは『ある１点に奇数本の直線が入り込んでいる地点』であり、『偶点』とは『ある１点に偶数本の直線が入り込んでいる地点』となります。
単純な一筆書き問題の場合、『図形の中に偶点のみしかない』場合と『奇点が２つある場合』には必ず一筆書きができることになります。
今回の問題における『奇点』の意味
問題の主旨から今回は全体を一筆書きできないことは明らかですが、『奇点』の位置を把握しておくことは重要です。
なぜなら、今回の出発・到着地点が『A』であることから、『奇点』においてはそこにつながる道路のうち『一本は絶対に通れない』ことになるからです。
例として『B』地点においては『C』に向かう道路と『D』に向かう道路のどちらかは必ず『通らない道路』になるということが分かります。
Ｂ〜Ｇ間の道路は必ず通る
『B』地点での２択についてもう少し検討してみましょう。
選択肢の１つとなる『Ｂ〜Ｇ間』には合計で９１個の荷物が配置されています。
いま『Ｂ〜Ａ〜Ｈ』の道路を必ず通ることは明らかですから、この道路における荷物の個数『１５個』を全体の個数『１９４個』からマイナスすると『１７９個』となり、『Ｂ〜Ｇ間の荷物９１個』はその半数を超えています。
したがって、『Ｂ〜Ｇ間』の道路についても必ず通ることは明らかであり、逆に『Ｂ〜Ｄ間』の道路は絶対に通らないことが確定します。
あらためて全体を眺めてみる
『Ｂ〜Ｄ間』を通らないものとして全体をもう一度ながめてみると、『Ｈ』『Ｉ』『Ｇ』を通って１周して戻ってくるルートが浮かび上がってきます。
そうなると奇点である『Ｈ』地点における通らない道路の２択では、単純に『Ｉ』地点までに荷物の個数が多い方を通過することになり、『Ｈ→Ｄ→Ｉ』と通過することが確定します。
Ｇ地点（奇点）から残りの経路を絞っていく
残りは『Ｉ』地点から『Ｇ』地点までの経路ということになりますが、『Ｇ』地点が『奇点』であることから、『Ｇ〜Ｋ』『Ｇ〜Ｆ』のどちらかの道路は通らないことになります。
ここで、荷物の個数が多い『Ｇ〜Ｆ』の道路を通ったと仮定して残りの経路を考えてみると、一例として『Ｉ→Ｅ→Ｆ→Ｊ→Ｉ→Ｆ→Ｇ』と通過することによって、残りの全ての道路を通ることができることが分かります。
選択肢の検討
上記のような経路によって配達できる荷物の個数が最大となることが分かりました。
問題で問われていたのはこの場合に配達する荷物の個数ですので、全体の個数『１９４個』から使用しなかった道路の荷物数を引いて、答えは『１６９個』となります。（正解肢４番）
YouTube講義
コメント