グラフの変形操作における単純性の保存

スポンサーリンク

概要

論文の詳細を見る
ラベル付きグラフ上の半順序関係である、カットサイズ順序、枝長和順序、交叉操作順序の三つは同値であることが知られている。グラフGがこの半順序関係においてG'に先行するとき、GをG'に変形する交叉操作の列が存在するが、仮にGとG'の両方が単純グラフだとしても、中間に単純でないグラフが現れる可能性がある。このことは、Hakimiによる名高い次数不変変換においても同様に起こる問題である。本稿では、このような場合に単純グラフのみを介して、変形しうるか否かという問題を取り扱う。結果、Hakimiの次数不変変換については、常に単純グラフによる変形が可能であることを示した。しかし一方で、上記の半順序関係に基づく変形の場合は、例え交叉操作以外の操作も許容したとしても、与えられた操作の種類が有限だとすると、その半順序関係にありながら単純グラフのみを介しての変換ができないグラフの組が必ず存在することを証明した。
一般社団法人情報処理学会の論文
2004-11-05

著者

関連論文

もっと見る

スポンサーリンク