グラフ上の複数拠点を多重に連結する辺素なシュタイナー木対の存在に関する基礎的考察

DOI Web Site 参考文献3件

書誌事項

タイトル別名
  • A Basic Study on the Existence of the Pairs of Edge-Disjoint Steiner Tree Connecting Multiple Terminals on Graphs
  • From the perspective of road network multiplicity evaluation
  • 道路網の多重性評価の観点から

説明

<p>本研究は、道路網の多重性を辺素なシュタイナー木対を軸として考察したものである。まず、辺素なシュタイナー木対のグラフでは、拠点数tとサイクル数lとの間に、l≧t－1の関係があることを導き、次に、拠点次数と拠点間の辺素な経路数の条件の下で、拠点を２個ずつサイクルで連結し、全拠点をこのサイクルの連鎖で連結することによって、辺素なシュタイナー木対を構成しうることを明らかにした。そして、グラフGに辺素なシュタイナー木対が存在すれば、e－v≧t－2（e:辺数、v:節点数）が成り立つことを明らかにし、例題を用いてこのことを確認した。この条件式を用いれば、所与のグラフに拠点をt 個 設けた場合に、それらの拠点を連結する辺素なシュタイナー木対が存在するか否か、あるいは所与のグラフにおいて辺素なシュタイナー木対で連結しうる最大拠点数tmax を知ることができ、拠点配置に基いた道路網の多重性を分析することが可能になる。</p>

収録刊行物

  • 都市計画論文集

    都市計画論文集 59 (3), 1668-1674, 2024

    公益社団法人 日本都市計画学会

参考文献 (3)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ