講演情報
[149]グラフ上の複数拠点を多重に連結する辺素なシュタイナー木対の存在に関する基礎的考察道路網の多重性評価の観点から
○外井 哲志1、梶田 佳孝2、大枝 良直3 (1. 元九州大学大学院工学研究院、2. 東海大学建築都市学部土木工学科、3. 九州大学大学院工学研究院)
キーワード：
グラフ理論、道路網の多重性、シュタイナー木、複数拠点、辺素
本研究は、道路網の多重性を辺素なシュタイナー木対を軸として考察したものである。まず、辺素なシュタイナー木対のグラフでは、拠点数tとサイクル数ℓとの間に、ℓ≧t－1の関係があることを導き、次に、拠点次数と拠点間の辺素な経路数の条件の下で、拠点を２個ずつサイクルで連結し、全拠点をこのサイクルの連鎖で連結することによって、辺素なシュタイナー木対を構成しうることを明らかにした。そして、グラフGに辺素なシュタイナー木対が存在すれば、e－v≧t－2（e:辺数、v:節点数）が成り立つことを明らかにし、例題を用いてこのことを確認した。この条件式を用いれば、所与のグラフに拠点をt 個 設けた場合に、それらの拠点を連結する辺素なシュタイナー木対が存在するか否か、あるいは所与のグラフにおいて辺素なシュタイナー木対で連結しうる最大拠点数tmax を知ることができ、拠点配置に基いた道路網の多重性を分析することが可能になる。