グラフ理論と順序理論において、比較可能性グラフとは、互いに比較可能な要素のペアを半順序で結ぶ無向グラフである。比較可能性グラフは、推移的有向グラフ、部分順序可能グラフ、包含グラフ[1]、および因子グラフ[2]とも呼ばれる。 非比較可能性グラフとは、互いに比較不可能な要素のペアを半順序で結ぶ無向グラフである。

定義と特徴

ポセットのハッセ図（左）とその比較可能性グラフ（右）
比較可能性グラフの禁制誘導部分グラフの一つ。このグラフの一般化閉路a–b–d–f–d–c–e–c–b–aは奇数の長さ（9）を持ちますが、三角弦を持ちません。

任意の厳密な半順序集合 ( S , <)に対して、( S , <)の比較可能性グラフは、頂点がSの要素、辺がu < vとなる要素のペア{ u , v }であるグラフ( S , ⊥)です。つまり、半順序集合に対して、有向非巡回グラフを取り、推移閉包を適用し、向きを削除します。

同様に、比較可能性グラフとは推移的な向きを持つグラフであり、[3]グラフのエッジに方向を割り当てて（つまりグラフの向きを指定して）、結果として得られる有向グラフの隣接関係が推移的になるようにします。つまり、有向エッジ( x、y )と( y、z )が存在する場合は常に、エッジ( x、z )が存在する必要があります。

任意の有限半順序は、xに対応する集合がyに対応する集合の部分集合である場合に、半順序においてx < yとなるような集合の族として表すことができる。このようにして、比較可能性グラフは集合族の包含グラフと同等であることが示される。包含グラフとは、族内の各集合を頂点とし、2つの集合の間には、一方が他方の部分集合である場合に、必ず辺が存在するグラフのことである。[4]あるいは、半順序を整数 の族で表すことができ、xに対応する整数がyに対応する整数の約数である場合に、 x < yとなる。この構成のため、比較可能性グラフは因子グラフとも呼ばれる。[2]

比較可能性グラフは、奇数長の一般化閉路（下記参照）ごとに、閉路内で距離2にある2つの頂点を結ぶ辺（x、y）が見つかるグラフとして特徴付けられる。このような辺は三角弦と呼ばれる。この文脈では、一般化閉路とは、グラフの各辺を各方向に最大1回しか使わない閉じた歩行として定義される。 [5]比較可能性グラフは、禁制誘導部分グラフのリストによっても特徴付けられる。[6]

共比較グラフ

ポセット（左）の共比較グラフ（右）

共比較グラフは、比較グラフの補グラフです。つまり、比較グラフG = ( V , E )が与えられたとき、その共比較グラフG̅ = ( V , E̅ )は同じ頂点集合を持ちますが、辺集合は相補的です。つまり、2つの頂点がG̅において隣接するのは、 Gにおいて隣接していない場合に限られます。

共比較可能性グラフは、まさに2本の平行線の間の連続曲線の交差グラフ、またはそれと同等の、2本の平行線上の区間の交差グラフです。[7]グラフが共比較可能性グラフであるためには、その補グラフが推移的な方向性を持つ必要があります。

共比較可能性グラフは、完全グラフの重要なサブクラスを形成し、この特性を、比較可能性グラフとその補グラフの両方が完全であるという事実から継承している（それぞれディルワースの定理とミルスキーの定理による）。[8]

すべての共比較可能性グラフは小惑星型三重自由（AT自由）である。[9]これにより、それらは区間⊂順列⊂台形⊂共比較可能性⊂AT自由という階層構造に位置づけられる。

共比較可能性グラフのクラスは、共比較可能性グラフの補グラフが比較可能性グラフであり、その逆もまた同様であるという意味で自己相補的です。

区間グラフはまさに弦グラフであり、共比較可能性補グラフを持つグラフである。つまり、任意の区間グラフの補グラフは比較可能性グラフであり、比較可能性関係は区間順序と呼ばれる。 [10]

共比較グラフは文字列グラフのサブクラスであり、すべての比較グラフの補グラフは文字列グラフである。[11]

他のグラフファミリーとの関係

すべての完全グラフは比較可能性グラフであり、これは全順序の比較可能性グラフである。完全グラフのすべての非巡回的配向は推移的である。すべての二部グラフもまた比較可能性グラフである。二部グラフの辺を二分割の一方から他方へ配向すると、推移的配向が得られ、これは高さ2の半順序に対応する。Seymour (2006) が指摘しているように、完全でも二部でもないすべての比較可能性グラフは、歪んだ分割を持つ。

順列グラフは区間集合上の包含グラフである。[12]したがって、順列グラフは比較可能性グラフの別のサブクラスである。

自明に完全なグラフは、根付き木の比較可能性グラフである。[13] コグラフは、直列-並列半順序の比較可能性グラフとして特徴付けることができるため、コグラフも比較可能性グラフである。[14]

しきい値グラフは、比較グラフの別の特殊な種類です。

すべての比較可能性グラフは完璧である。比較可能性グラフの完璧性はミルスキーの定理であり、その補グラフの完璧性はディルワースの定理である。これらの事実は、完璧グラフ定理とともに、ミルスキーの定理からディルワースの定理を証明するために使用でき、その逆も同様である。[15]より具体的には、比較可能性グラフは完全に順序付け可能なグラフであり、完璧グラフのサブクラスである。グラフの推移的方向の位相的順序付けのための貪欲彩色アルゴリズムは、それらを最適に彩色する。 [16]

アルゴリズム

グラフの推移的な向きは、もし存在するなら、線形時間で見つけることができます。[17]しかし、そのためのアルゴリズムは、あらゆるグラフのエッジに向きを割り当てます。そのため、グラフが比較可能グラフであるかどうかをテストするタスクを完了するには、結果として得られる向きが推移的であるかどうかをテストする必要があります。これは、複雑さの点で行列の乗算と同等であることが証明できる問題です。

比較可能性グラフ（および共比較可能性グラフ）は完全であるため、グラフの色付けや独立集合問題など、より一般的なグラフのクラスでは難しい多くの問題は、これらのグラフでは多項式時間で解決できます。

参照

注記

  1. ^ Golumbic (1980)、p. 105; Brandstädt、Le & Spinrad (1999)、p. 94.
  2. ^ ab Chartrand et al. (2001).
  3. ^ Ghouila-Houri (1962); Brandstädt, Le & Spinrad (1999)、定理1.4.1、p. 12を参照。半順序から生じる方向付けは非巡回的であるが、この特徴付けの条件として非巡回性を含める必要はない。
  4. ^ ウルティア (1989);トロッター (1992); Brandstädt、Le & Spinrad (1999)、セクション 6.3、94 ～ 96 ページ。
  5. ^ Ghouila-Houri (1962)およびGilmore & Hoffman (1964). Brandstädt, Le & Spinrad (1999)の定理6.1.1, p. 91も参照。
  6. ^ ガライ (1967);トロッター (1992); Brandstädt、Le & Spinrad (1999)、p. 91とp. 112.
  7. ^ ゴルンビッチ、ロテム、ウルティア (1983)
  8. ^ Golumbic（1980）、定理5.34と5.35、p.133。
  9. ^ ゴルムビック、マーティン・チャールズ；モンマ、クライド・L.；トロッター、ウィリアム・T.・ジュニア（1984）「許容グラフ」、離散応用数学、9（2）：157-170、doi：10.1016/0166-218X（84）90016-7
  10. ^ 区間グラフ補集合の推移的有向性はGhouila-Houri (1962)によって証明された。区間グラフの特徴づけはGilmore & Hoffman (1964)による。Golumbic (1980)、prop. 1.3、pp. 15–16も参照。
  11. ^ ゴルンビッチ、ロテム、ウルティア (1983) およびロヴァーシュ (1983)。 Fox & Pach (2012) も参照してください。
  12. ^ ドゥシュニクとミラー (1941)。 Brandstädt、Le & Spinrad (1999)、定理 6.3.1、p. 95.
  13. ^ Brandstädt、Le & Spinrad (1999)、定理 6.6.1、p. 99.
  14. ^ Brandstädt、Le & Spinrad (1999)、当然のこと 6.4.1、p. 96;ユング (1978)。
  15. ^ Golumbic（1980）、定理5.34と5.35、p.133。
  16. ^ マフレー（2003年）。
  17. ^ McConnell & Spinrad (1997); Brandstädt, Le & Spinrad (1999)、p. 91を参照。

参考文献

  • Brandstädt, Andreas ; Le, Van Bang ; Spinrad, Jeremy (1999) 『グラフクラス：概説』、SIAM Monographs on Discrete Mathematics and Applications、ISBN 0-89871-432-X。
  • Chartrand, Gary ; Muntean, Raluca ; Saenpholphat, Varaporn ; Zhang, Ping (2001)、「どのグラフが因子グラフか？」 Proceedings of the Thirty-Second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001)、Congressus Numerantium、151 : 189–200、MR  1887439
  • ダシュニク, ベン; ミラー, EW (1941)、「半順序集合」、アメリカ数学誌、63 (3)、ジョンズ・ホプキンス大学出版局: 600– 610、doi :10.2307/2371374、hdl : 10338.dmlcz/100377、JSTOR  2371374、MR  0004862。
  • Fox, Jacob; Pach, Jànos (2012)、「文字列グラフと比較不可能グラフ」(PDF)、Advances in Mathematics、230 (3): 1381– 1401、doi : 10.1016/j.aim.2012.03.011。
  • Galrai、Tibor (1967)、「Transitiv orientierbare Graphen」、Acta Math。アカド。科学。フン。、18 ( 1–2 ): 25–66、土井:10.1007/BF02020961、MR  0221974、S2CID  119485995。
  • Ghouila-Houri、Alain (1962)、「Caractérisation desgraphes non orientés dont on peut orienter les arrêtes de manière à obtenir legraphe d'une relationship d'ordre」、Les Comptes rendus de l'Académie des Sciences、254 : 1370–1371、MR  0172275。
  • ギルモア, PC; ホフマン, AJ (1964)、「比較可能性グラフと区間グラフの特徴づけ」、カナダ数学ジャーナル、16 : 539– 548、doi : 10.4153/CJM-1964-055-5、MR  0175811。
  • ゴルンビック、マーティン・チャールズ（1980）、アルゴリズムグラフ理論と完全グラフ、アカデミックプレス、ISBN 0-12-289260-7。
  • Golumbic, M.; Rotem, D.; Urrutia, J. (1983)、「比較可能性グラフと交差グラフ」、離散数学、43 (1): 37– 46、doi : 10.1016/0012-365X(83)90019-5。
  • ユング, HA (1978)、「ポセットのクラスとそれに対応する比較可能性グラフについて」、組合せ理論ジャーナル、シリーズB、24 (2): 125– 133、doi : 10.1016/0095-8956(78)90013-8、MR  0491356。
  • ロヴァース, L. (1983)、「完全グラフ」、グラフ理論選集、第2巻、ロンドン：アカデミック・プレス、pp.  55– 87。
  • マフレー、フレデリック（2003）「完全グラフの色彩について」、リード、ブルース・A.、セールス、クラウディア・L.（編）、アルゴリズムと組合せ論の最近の進歩、CMSブックス・イン・マスマティクス、第11巻、シュプリンガー・フェアラーク、pp.  65– 84、doi :10.1007/0-387-22444-0_3、ISBN 978-1-4684-9268-2。
  • McConnell, RM; Spinrad, J. (1997)、「線形時間推移的指向」、第8回ACM-SIAM離散アルゴリズムシンポジウム、pp.  19– 25。
  • シーモア、ポール（2006）「強完全グラフ予想の証明はいかにして発見されたか」（PDF）、ガゼット・デ・マテマティシャン（109）：69-83、MR  2245898。
  • トロッター、ウィリアム・T.（1992）「組合せ論と半順序集合—次元理論」ジョンズ・ホプキンス大学出版局。
  • ウルティア、ホルヘ（1989）「部分順序とユークリッド幾何学」、リヴァル、I.（編）『アルゴリズムと秩序』、クルーワー・アカデミック・パブリッシャーズ、pp.  327– 436、doi :10.1007/978-94-009-2639-4、ISBN 978-94-010-7691-3。