最適ネットワーク合成問題

藤重研究室 高橋園子

与えられたすべての点対間の流量条件を満たすような無向フローネットワークのうちで，容量総和が最小となるものを見出す問題は，従来より研究されており，R.E.GomoryとT.C.Hu により結果が得られている．本論文では，この問題にさらに次のような要求条件を付け加えた問題について考察する．まず，容量総和最小の条件の下で正の容量をもつ枝の数を最小化する問題について考察する．次に，同じ条件の下で容量の最大値を最小化する問題について考察し，この問題をLPによって定式化し，ある特殊な場合における最適なネットワーク合成法を与える．