- 著者
-
後藤 敏
大附 辰夫
- 出版者
- The Institute of Electronics, Information and Communication Engineers
- 雑誌
- 電子情報通信学会論文誌 A (ISSN:03736091)
- 巻号頁・発行日
- vol.J57-A, no.11, pp.810-817, 1974-11-25
グラフの特定の2節点間のパスの長さ,あるいはカットセットの値の最大・最小を求めることは,それ自体でも意味ある問題であるが,各種の問題の部分問題として現れるので極めて重要である.従来,解法としてラベリング法に基づくグラフ的手法と線形計画法で代表される代数的手法がよく用いられているが,二つの手法が全く独立な立場から論ぜられており,両者のギャップを縮めるための研究はあまりなされていない.本文ではこれらの問題をグラフの基本カットセット行列あるいは基本閉路行列によって表されるキルヒホッフの法則を用いて線形計画法で定式化し,シンプレックス法による解法と1対1に対応した新しいグラフ的手法を導き,これらの問題が統一的に扱えることを示した.更に,シンプレックス法における基底・枢軸変換・双対性・退化などの概念がすべてグラフ理論と対応づけられることが明らかになった.又,本文で提案した方法はパス,カットセットの最大・最小問題の一般解を求めることができるため,実用的価値が高いと思われる.