Loading article…
グラフ理論と順序理論において、比較可能性グラフは、部分順序で互いに比較可能な要素のペアを接続する無向グラフです。比較可能性グラフは、推移的に向き付けられるグラフ、部分順序付け可能なグラフ、包含グラフ[ 1 ]、および因子グラフ[ 2 ]とも呼ばれています。非比較可能性グラフ は、部分順序で互いに比較できない要素のペアを接続する無向グラフです。
厳密な半順序集合( 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フリー、および 順列⊂台形⊂共比較⊂ATフリー。
共比較グラフのクラスは、共比較グラフの補グラフが比較グラフであり、その逆もまた然りという意味で、自己相補的である。
区間グラフとは、弦グラフであり、かつ共比較補グラフを持つグラフのことです。つまり、任意の区間グラフの補グラフは比較グラフであり、比較関係は区間順序と呼ばれます。 [ 10 ]
共比較グラフは文字列グラフのサブクラスであり、すべての共比較グラフの補グラフは文字列グラフである。[ 11 ]
すべての完全グラフは比較グラフであり、全順序の比較グラフです。完全グラフのすべての非巡回方向付けは推移的です。すべての二部グラフも比較グラフです。二部グラフのエッジを二分割の一方の側から他方の側に方向付けると、推移的な方向付けが得られ、高さ 2 の部分順序に対応します。Seymour (2006)が指摘するように、完全でも二部グラフでもないすべての比較グラフは、歪んだ分割を持ちます。
順列グラフは、区間の集合上の包含グラフです。[ 12 ]したがって、順列グラフは比較グラフの別のサブクラスです。
自明に完全なグラフは、根付き木の比較可能性グラフである。[ 13 ]コグラフは、直並列部分順序の比較可能性グラフとして特徴付けられる。したがって、コグラフも比較可能性グラフである。[ 14 ]
閾値グラフは、比較可能性グラフのもう一つの特殊な形態である。
すべての比較可能グラフは完全である。比較可能グラフの完全性はミルスキーの定理であり、その補グラフの完全性はディルワースの定理である。これらの事実は、完全グラフ定理と合わせて、ミルスキーの定理からディルワースの定理を証明するために、またはその逆のために使用できる。[ 15 ]より具体的には、比較可能グラフは完全順序付け可能なグラフであり、完全グラフのサブクラスである。グラフの推移的向き付けの位相順序付けに対する貪欲彩色アルゴリズムは、それらを最適に彩色する。[ 16 ]
グラフの推移的向き付けが存在する場合、それは線形時間で見つけることができます。[ 17 ]ただし、これを行うアルゴリズムは任意のグラフのエッジに向き付けを割り当てるため、グラフが比較グラフであるかどうかをテストするタスクを完了するには、結果として得られる向き付けが推移的であるかどうかをテストする必要があります。この問題は、行列乗算と同等の複雑さであることが証明されています。
比較グラフ（および共比較グラフ）は完全グラフであるため、グラフ彩色や独立集合問題など、より一般的なグラフクラスでは難しい多くの問題が、これらのグラフでは多項式時間で解くことができる。