■ ＩＴＮｅｗｓＬｅｔｔｅｒ ■文教大学大学院■情報学研究科

半順序集合の上界グラフ
文教大学大学院情報学部研究科 教授

惠 羅 博†
Hiroshi Era

あらまし有限集合 V 上の半順序関係 ≤ によって定義される poset (半順序集合) P = P(V, ≤ ) を考える。２点 p ,q ∈V が「P において共通の上界を持つ」という V 上の２項関係は、poset P の構造の本質的な特性を表すものと考えられ、この２項関係を表すグラフを定義することによって、様々な形での研究が行われてきた。この関係に基づく poset のグループ分けに関する話題と、上界グラフの特徴や性質に関する研究について紹介する。
キーワード：グラフ理論、上界グラフ、反順序集合、反順序関係 、poset, upper bound graph
与えられたposet P = P(V, ≤ ) に対して、グラフG(P) =(V, E) を、pq∈E ⇔ ∃m∈V; p ≤ m & q ≤ m (p, q∈V)で定義し、P(V, ≤) の上界グラフ(upper bound graph)と呼ぶ。ある poset の上界グラフとなり得るグラフを（特に P を特定せず）単に上界グラフと呼ぶ。
これは、1982 年に F.R.McMorris と T. Zaslavsky [1] によって定義された。food-web などの生態系の研究で用いられたグラフの族として、competition graph, commonenemy graph などが知られているが、上界グラフはこれらの概念を poset 上へ一般化したものであり、より抽象的な概念に枠を拡げた中で問題を捉え直そうとしたものである。
最初に注意すべきことは、与えられた上界グラフ Gに対して、G = G(P) となる poset P は一意的ではないということである。実際、多くの異なる poset が一つの上界グラフを共有していることは簡単に判る。例えば、下図のグラフ G を上界グラフに持つ poset は、図のように P1, P2, Q1, Q2 の４つ存在し、同型の違いを除いては２つ存在する。したがって、１つの上界グラフと複数の poset からなる１グループが対応することになる。

pp

P1(P2)

qGrsqr(s)r(s)
Q1(Q2)s(r)
s(r)

qp

そこで、基本的な問題として、与えられた上界グラフ Gに対して、G = G(P) となる poset P はいくつ存在するのか？これに対する答えは一般的な形では未だ存在していな
い。G の構造に拠る所が大で、G の位数やサイズ、連結度などの量的な要因にはあまり依存しないから、それらの関数として一般的に公式化することはまず絶望である。しかし、与えられた G のクリーク(極大完全部分グラフ）の分布によって、個数の上限の評価が可能であることがK.Ogawa[5]によって示された。この論文で Ogawa は、共通の上界グラフを持つ poset の１グループ全体の構造の解析を試みている。
１つの上界グラフ G を共有する poset の族 Π(G) は、実は、それ自身 が poset になるという、再帰的とでも言える面白い構造を有している。poset P(V, ≤) を、関係 p ≤ q を満たす順序対 (p, q) の集合とみなせば、この族 Π(G)の要素（poset)の間に、集合としての包含関係による半順序関係⊆ が定義できる。この関係によって、 (Π, ⊆)は半順序集合となるのである。上の例でいえば、Π(G)={P1, P2, Q1,Q2}であり、この族は関係 P1⊆Q1, P2⊆Q2 をもつ poset である。
この半順序集合において隣接する２要素 P⊆Qに対して、P を Q に、また Q を P に移す互いに可逆な関係にある２つの変換を定義することができる。ひとつは、特定の条件のもとで P に１つの順序対 p ≤ q を付加する変換であり、もう１つは、特定の条件のもとで Q から１つの順序対 p ≤q を除去する変換である。再度上の例を参照すれば、例えば Q1=P1＋{q ≤ s}、逆に、P1=Q1-{q ≤ s } 等が成り立つ。
この２つの変換によって、poset の族 Π 全体の要素をすべて探索していくことができる。Ogawa[5]は、これらの変換操作に基づくΠ全体の構造とそのスケールの評価をしたのである。これらの変換に関しての研究は[6]に詳しい。

2007 年 6 月 26 日受付†〒253-8550 神奈川県茅ヶ崎市行谷 1100 era@shonan.bunkyo.ac.jp
Graduate School of Information and Communication, Bunkyo University
文教大学大学院情報学研究科

IT News Letter

Vol.3, No.2, pp.3-4 (2007)3

上界グラフ G の性質や特徴の方に焦点を当てた研究も多くなされている。このようなグラフの「特徴付け」は論文[1]ですでに示されており、その後、他の研究者（[2],[3]など）による特徴付けも試みられている。これらの特徴付
けは、主に、グラフのすべての辺をカバーするクリーク（極大完全部分グラフ）の族の存在と、それらの各クリークにおける simplicial vertex の存在に依存した命題が中心的役割を果たしている。ここで、グラフ G = (V, E) の simplicialvertex p∈V とは、p の近傍（p の隣接点全体の集合）N(p)が G の完全部分グラフとなるような点のことである。
上の例では、p,r,s が G の simplicial vertex である。一般に
poset P の極大元は G(P)において simplicial vertex になり、一方、G の各極大クリークは P において、それに含まれるsimplicial vertex を極大元とするイデアルを形成することが簡単に示される。したがって、上界グラフにおいては極大クリークの分布と simplicial vertex の存在が常に問題解決の鍵を握ることになる。
一方、これらとは異なった観点からの研究が、著者やIwai,Ogawa, Tsuchiya 等[4]によって近年なされた。これは、グラフの辺の縮約の操作によって、nova と呼ばれる特殊なグラフのクラスに変換可能であることを条件として特徴付けを試みたものであり、Bergstrand, Jones 等の研究（[3]）と軌を一にしている部分もある。一定の条件を満たし、両端がsimplicial vertex ではない辺に着目して、それらを縮約することによって nova となることが、上界グラフであるための必要十分条件であることを示した。従来のような、与えられたグラフのグローバルな構造に依存するものではなく、構成的、アルゴリズム的特徴付けであると言ってもよい。とはいえ、ここでの辺操作にあたっては、やはり simplicilavertex に着目していることに変わりはない。ここで、novaとは星グラフ K(1,n)の辺を２点以上もつ完全グラフに置き換えていく操作を適当回繰り返して得られるグラフのことである。
グラフの特殊なクラスに限定して上界グラフとなる条件を求める研究も多い。最近のものでは[7]がその典型といえる。ここでは、split graph, threshold graph, difference graphと呼ばれるグラフのそれぞれの場合について、上界グラフとなるための条件を決定している。元々、これらの各クラスに属するグラフの特徴付けは、forbidden subgraph を与えることによってなされていることが多い。一般に、性質 αを持つグラフのクラスを C(α) とするとき、G∈C(α) ⇔H∈Γ; H≪Gを満たすグラフの族 Γ が決定可能であるとき、Γ を C(α)の forbidden subgraph（禁止部分グラフ）の族と呼ぶ。ここで、 H≪G は H が G の誘導部分グラフであることを表す。[7] においても、これらのクラスの forbidden subgraphの族を利用して特徴付けをしているのであるが、面白いのは、poset 側での構造でそれをおこなっていることである。
実は、「任意のグラフ H に対して、H を誘導部分グラフとして含む上界グラフが存在する」という定理が存在している。したがって、本来、上界グラフの特徴付けに対しては、forbidden subgraph の概念は無効なのである。そこで、類似の概念を poset 側に移して特徴づけを試みているのである。
Q を poset P の subposet とする。これらの上界グラフの関係として、G(H)が G(P)の誘導部分グラフとなる条件を考えることによって Scott[8]は m-subposet の概念を考え出した。
4poset P(V, ≤) の subposet Q が m-subposet であるとは、∀p, q∈V' =V(Q) , ∃m∈V=V(P); p, q ≤ m (in P) ⇒∃m'∈V' = V(Q); p ,q ≤ m' (in Q)が満たされることである。定義から、G(Q)≪G(P) であるための必要十分条件は Q が P の m-subposet であることが自然に導かれる。 [7]では、この m-subposet の概念を用いて、次のような形のいくつかの命題を示しているが、詳細は[7]に譲り、ここでは雰囲気だけ読みとっていただこう。
Prop. G: connected split UB-graph ⇔ can(G) は P(2K2)を m-subposet として含まない。
ここで、can(G) は、Π(G) における極小元を表す。

［文 献］
1) F.R.McMorri and T.Zaslavsky, Bound graphs of a partiallyordered set, J. Combinatorics, Information & System
Sciences 7(1982), 134-138.
2) J.R.Lundgren and J.S.Maybee, A characterization of upperbound graphs, Congressus Numerantium 40 (1983), 189-1933) D.J.Bestrand and K.F.Jones, On upper bound graphs ofpartially ordered sets, Congressus Numerantium 66 (1988),
185-1934) H.Era,S-I Iwai, K.Ogawa, M.Tsuchiya, Note on construction
methods of upper bound graphs, International Journal ofGraphs and Combinatorics 1-No.2(2004), 103-108
5) K.Ogawa, On distances of posets with the same upper boundgraphs, Yokohama Mathematical Journal 47 (1999),231-2376) H.Era, K.Ogawa and M.Tsuchiya, On transformations ofposets which have the same bound graph, Discrete
Mathematics 235(2001), 215-220
7) H.Era, K.Ogawa, S.Tagusari, M.Tsuchiya, On upper boundgraphs with forbidden subposets, Electronic Notesin
Descrete Mathematics 22(2005), 107-111
8) D.D.Scott, Poset with interval upper bound graph, Order3(1986), 269-281

えら ひろし惠羅 博 1949 年生．1972 年 3 月東京都立大学理学部数学科卒業．1980 年 3 月東海大学大学院理学研究科博士課程単位取得後退学（数学専攻）．1985 年学位取得（理学博士,東海大学）.1986 年 4 月文教大学情報学部講師に着任．
現在，文教大学情報学部教授．2005 年 4 月より文教大学大学院情報学研究科教授兼任．情報学研究科では，「情報数学演習」を担当．専
門分野はグラフ理論．

文教大学大学院情報学研究科

IT News Letter

Vol.3, No.2 (2007)