§３．ゴミ収集を効率よくする清掃車のコース決め

---

　近年、ゴミ問題が大きな社会問題になってきている。毎日、各家庭等から出されるゴミの総量は膨大なものであり、その処理において様々な環境汚染を引き起こしている。また、ゴミの不法投棄も後をたたず、海岸や野山にも多くのゴミが目立つ。
　一方、都市におけるゴミの収集も非常に時間と労力がかかり、清掃に携わる人たちの苦労もはかりしれないものがある。
　ここでは、道路わきに各家庭からだされたゴミを、ゴミ清掃車が短時間にできるだけ多く収集できるようにするにはどうすればよいかという課題に対して、主に清掃車のコ−ス決めに焦点を絞って、グラフ理論を利用して考察していこうと思う。

　その前に、この課題を考える上でのいくつかの便利で重要な定理を学んでおくことにしよう。

　1736年、グラフ理論の父と呼ばれている偉大なスイスの数学者オイラ−は、当時まだ解けていなかった“ケ−ニッヒスベルグの橋の問題”と呼ばれる問題を解決した。
　ケ−ニッヒスベルグは現在、ロシアのカリ−ニングラ−ドと呼ばれる都市であり、18世紀初頭、この町の中を流れるプレ−ゲル川には、図12-1に示すように、４つの区域Ａ,Ｂ,Ｃ,Ｄを結ぶ７つの橋がかかっていた。町の人々は家を出発して全ての橋をちょうど１回渡って再び家に戻るコ−スを見つけ出すことを試みながら散歩を楽しんだといわれている。
　この問題に対し、望むコ−スが存在しないことを証明したのがオイラ−である。さらに、彼はこの問題を解いただけでなく、同じような問題の一般的解法も発見したのである。彼のこの証明をのせた論文は、グラフ理論的概念を用いた最初の論文であったといわれている。

　図12-1の４つの区域Ａ,Ｂ,Ｃ,Ｄを点で表わし、２点に対応する２区域がいくつかの橋で結ばれているならば、それと同数の線で２点を結ぶと、図12-2に示した多重グラフができる。
　したがって、“ケ−ニッヒスベルグの橋の問題”は、図12-2の多重グラフを一筆で描き(紙から鉛筆を離すことなく、かつ、同じ線上を再び通ることなく描き)、描き初めの地点と描き終わりの地点を一致させることができるかという問題と同一視できる。
　先に述べたように、図12-2は一筆で描くことはできない。
　一筆で描くことのできるグラフを図13にいくつか示しておく。�@�Aは一筆で描け、かつ、描き初めの地点と描き終わりの地点を一致させることのできるグラフであり、�B�Cは一筆で描けるが、描き初めの地点と描き終わりの地点が異なるグラフである。

図13

　※点以外で線同士が交差している部分では描く向きを変えないものとする。

　図13のグラフを見て、すでに気づいた人がいるかもしれないが、�@�Aのようなオイラ−回路を持つグラフ(オイラ−グラフ)、�B�Cのようなオイラ−小径を持つグラフそれぞれには、重要かつ有用な特徴があるのです。すなわち、

　ここでさらに、そのグラフがオイラ−回路を持つことが分かっても、実際にどのような順序で点および線をたどっていけばその回路を発見できるのかが問題となる。

　例えば、図13の�@はオイラ−グラフであるが、図14の�@のような順で描いていっても、一筆で描くことはできない。
　しかし、図14の�Aのような順で描いていけば、５以降きちんと描く順番が付けられる。　

図14

すなわち大事なことは、

　このオイラ−回路の見つけ方は、Fleuryによって考案されたものである。

　ここで、始めの『ゴミ収集を効率よくする清掃車のコ−ス決め』問題に戻ってみよう。この問題は、様々な条件を変えることで、いくつかのグラフ理論の問題として考えることができる。条件のいくつかとしては、次のようなものが考えられる。

　今、図11の道路はすべて両方向通行可能であるが、幅が狭いため、清掃車が通過するとき、道の両側のゴミを一度に持っていくものとする。効率よく清掃するには、一度清掃した道路を再び通ることなく清掃できればよい。そこで、定理３・１を利用すると、図11のグラフは奇点を１０個持つからオイラ−回路もオイラ−小径も持たない。したがって、１台の清掃車で、一度清掃した道を再び通ることなく全ての道を清掃することはできない。
　そこで、何台かの清掃車を一度に使うことを考えてみよう。奇点を２個だけもつグラフの場合、定理３・１で述べたように、オイラ−小径を持ち、しかもその小径の始点と終点は奇点になる。図11のグラフは奇点を10個持っているから、いくつかの小径に分割し、その一つ一つの小径を１台の清掃車が担当すれば、一度清掃した道を再び通ることなく全ての道を効率的に清掃できる。
　10個の奇点を小径の始点及び終点と考えるとよさそうなので、図11のグラフは、最小で10÷２＝５本の小径に分割できるのではないかと考えられる。
　　　　　　　　　　　　　　　　　　

　効率的という言葉は、ここでは非常にあいまいであり、今の場合、同じ道を再び通らないことを効率的という言葉で表わしている。しかし、まだまだ細かな条件を付けると、様々な問題が作れ、それぞれに異なった解答が考えられる。
　たとえば、単に同じ道を通らないという条件に加え、さらに５台の各清掃車の清掃距離をできるだけ均等にした方が、同時に清掃を始めると短時間で清掃が終了する。この場合さらに問題が難しくなる。
　また、清掃車が１台しかない場合、できるだけ走行距離が短くて済むようにするにはどういうコ−スで走ればよいかという問題も考えられる。この場合は、２度以上通るコ−スの距離を最小にするコ−スを考えなければならない。

　定理の紹介の前に、いくつかの必須用語について説明をしておきます。
図16の�Aのような有向グラフの点 v から出ていく有向線の本数を、点 v の出次数と呼び、od v で表します。また、点 v に入ってくる有向線の本数を入次数と呼び、id v であらわします。
　図16の�Aの有向グラフにおいては、od v ＝２　，　id v ＝３　である。

　※証明については、本ホームページの参考文献を参照されたし。

　定理３・３を使うと、図16の�Aは点 u を始点とし、点 v を終点とするオイラ−小径を持つことがわかる。

　ここで、再び図11の問題に戻ってみよう。図11に示している全ての道路が両方向一車線づつあり、清掃車が進行方向左側のゴミだけを収集していくものとすると、同じ車線を再び通ることなく１台の清掃車で道路わきの全てのゴミを収集できる。なぜなら、図11のグラフの全ての線を、向きが逆の２本の有向線で置き換え、有向グラフを作ると、各点の内次数と外次数が等しくなるからである。

　※証明については、本ホームページの参考文献を参照されたし。

　定理３・４を使うと、図17のグラフは、各点の内次数と外次数の差の総計が12であるから、12÷2＝6 本の小径に分割できる。
　では、実際にはどのようにして６本の小径に分割すればよいのだろうか。
　グラフの点の中で、特に、内次数と外次数の異なる点に注目してください。もし全ての点の内次数と外次数が等しければ、定理３・３で述べたようにオイラ−回路が存在し、その見つけ方も前に述べている。
　したがって、内次数の方が多い点から外次数の方が多い点に向かって有向線を加え、全ての点の外次数と内次数を一致させる。そのとき、加えた有向線の本数は、その引き方から、各点の内次数と外次数の差の総計の半分になることがわかるでしょう。例えば、図17のグラフでは有向線を適切に６本加えれば、オイラ−回路を持つ有向グラフになります。
　そこで、その有向グラフのオイラ−回路を求め、その回路から、先に加えた６本の有向線を取り除けば、始めの有向グラフを６本の小径に分割できる。

　これらグラフや有向グラフの中に、オイラ−回路やオイラ−小径を見つける一連の問題は、古くから郵便配達問題と呼ばれ研究されてきた。その結果、上で述べたもの以外にも、多くの定理やアルゴリズムが発見されている。

　中高校生のためのグラフ理論　Top Menu　へ