著者

穴沢 務

出版者

公益社団法人日本オペレーションズ・リサーチ学会

雑誌

オペレーションズ・リサーチ : 経営の科学 (ISSN:00303674)

巻号頁・発行日

vol.47, no.3, pp.189-190, 2002-03-01

---

本論文では,節集合がVの単純グラフGと「要求」の集合{r_>υω<|υ,ω∈V}が与えられたとき,Huが提示した最適要求木問題の目的関数に似た関数を最小化するハミルトン閉路を求める問題を考察する.そして,Gが完全かつ{r_>υω<}がモンジュ性と関係の深い逆スープニック性を満たすとき,ある特殊なハミルトン閉路C^*(それは陽に定義可能)が最適解であることを示す.興味深いことに,このC^*は(逆でない)スープニック性を伴う対称巡回セールスマン問題の最適解でもある.さらに本論文では,リング型ネットワークの構築において逆スープニック性を自然に仮定できる場合があることと,その場合はC^*が最適なリング型ネットワークとなることを示す.