PQ-木を用いたグラフの平面化アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
Lempel, Even, Cederbaum のグラフの平面性判定アルゴリズムに基づき, PQ-木と呼ばれるデータ構造を用いたグラフの平面化アルゴリズムと, それをランダムグラフに適用した結果を示す. このアルゴリズムでは, まず, グラフの節点にst-番号と呼ばれる番号をつけ, 番号1の節点から始めて, st-番号順に, 節点1個ずつとそれから出る枝を付加し, その都度, 平面描写を試みる. 平面描写できないときは, 最小限の枝を除去して平面描写可能にする. 得られた平面部分グラフに次の節点とそれから出る枝を付加する. この操作を最後の節点まで続け, すべての節点を含む平面部分グラフを得る. 上記の操作中, 平面化の対象となる部分グラフはPQ-木で表現され, その平面化のため必要最小限の枝の除去は, PQ-木の葉から始め, 順次, 根に向って最小除去葉数を計算することにより達成される. このアルゴリズムの計算複雑度は, Ο(n(e+n))以下である. ただし, nはグラフの節点数, eは枝数である. このアルゴリズムをランダムグラフに適用し, 平面化に関する統計的データを求めている. 適用例の範囲では, 平面化のための除去枝数は, st-番号を変えてもあまり変らず, その平均と標準偏差は, 比較的少ないst-番号の変化回数で推定可能である. また, グラフによっても, 除去枝数はさほど変らず, 得られる平面グラフの枝数は, もとのグラフの節点数と枝数から推定できる.
- 一般社団法人情報処理学会の論文
- 1981-01-15