木上二重コンベックスグラフと二部サークルグラフの等価性

スポンサーリンク

概要

論文の詳細を見る
二部グラフG=(A,B,E)について,Bの各要素bに対しA(b)={a∈A|辺(a,b)が存在}なる集合を考える.全てのbについてA(b)の要素が連続して現れるようにAの要素を一列に並べることができるとき,Gは頂点集合Aの上でコンベックスであるという.また,以下のような木Tが存在するとき,すなわちTの辺とAの各要素をA(b)に対応した辺が木Tの上で道を構成するように一対一対応させることができるとき,木上コンベックスという.AとBを入れ換えても同じ性質が成り立つとき,そのようなグラフをそれぞれ二重コンベックス,木上二重コンベックスという.本論文では,コンベックスグラフ,二重コンベックスグラフ,木上コンベックスグラフ,木上二重コンベックスグラフの4つのコンベックスグラフのクラス間に成立する包含関係を示す.さらに,その4種類のコンベックスグラフのクラスと二部サークルグラフとの間に成り立つ包含関係も示す.
社団法人電子情報通信学会の論文
1994-01-26

著者

関連論文

もっと見る

スポンサーリンク