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