Mathematics
Examination
Test
Archives
【2】 ゴミの収集と域内処理といった廃棄物行政は非常に重要な行政サービスのひとつである.家庭ゴミの収集経路の設定に際して,次の問いに答えよ.
図1
図2
図3
(1) 都市では,ゴミ収集車から排出される温室効果ガスを最小にするために,最短経路でゴミ収集車を運行する.都市の中心部は図1にあるように,南北に本,東西に本の格子状の道となっている.ゴミ収集は,点を出発点として,点に達する.このときゴミ収集の最短経路は全部で通りある.そのうち,重要な観光スポットにあるゴミ集積所を必ず通って収集するとき,最短経路は全部で通りある.
(2) 都市の道は図2のように複雑であり,必ずしも最短経路でのゴミ収集ができるわけではない.このため,都市では,次のにしたがって,点から点へのゴミ収集の経路を設定する.
最短経路でなくても良い.
点と点は途中で通過することはできず,それ以外の点は複数回通過できない.
通過しない点があっても良い.
都市のゴミ収集の経路について,次の問いに答えよ.
(a) 都市の道は,図2のように点を結んでいる.このとき,点から点へのゴミ収集の経路は通りある.そのうち,点の各点をすべて通過するゴミ収集の経路は通りある.
(b) 都市に点を結ぶ新たな道が完成し,図3のようになった.このとき,点から点へのゴミ収集の経路は通りある.そのうち,点の各点をすべて通るゴミ収集の経路は通りある.