IEICE Trans - 直並列グラフの最小木を求めるのに必要な比較の回数について

直並列グラフの最小木を求めるのに必要な比較の回数について

松下　浩明丸岡　章木村　正行

誌名
電子情報通信学会論文誌 D Vol.J65-D No.12 pp.1491-1498
発行日: 1982/12/25
Online ISSN:
DOI:
Print ISSN: 0913-5713
論文種別: 論文
専門分野:
キーワード:

本文: PDF(589.2KB)>>

あらまし:
グラフの各辺にコストと呼ばれる整数が割当てられているとき，そのグラフの最小木とはグラフを張る木（極大木）のうちで辺のコストの総和が最小の木のことである．本論文では，グラフの最小木を辺のコストの大小比較演算だけで求める問題を考察する．まず，グラフの最小木を求めるには少なくともn－b回の大小比較が必要なことを示す．ここでnはグラフの辺の個数であり，bはグラフのブロックの個数である．次に，グラフの各辺のコスト割当てがどのようであれ，n－b回の大小比較でグラフの最小木が決定できるための必要十分条件は，グラフが直並列グラフとなることであることを示す．これらのことより，直並列グラフからなるグラフのクラスと最小の比較回数で最小木が求まるグラフのクラスが一致することが分かる．