完全に順序付け可能なグラフ

グラフ理論において、完全に順序付け可能なグラフとは、そのグラフの頂点を、その順序付けを用いた貪欲彩色アルゴリズムによって、与えられたグラフのすべての誘導部分グラフが最適に彩色されるような順序付けが可能なグラフのことである。完全に順序付け可能なグラフは、完全グラフの特殊なケースであり、弦グラフ、比較可能性グラフ、距離遺伝グラフなどが含まれる。しかし、グラフが完全に順序付け可能かどうかをテストすることはNP完全である。

意味

貪欲彩色アルゴリズムは、グラフGの頂点の与えられた順序に適用されると、グラフの頂点を順に検討し、各頂点に最初の使用可能な色、つまり近傍で使用される色のセットの最小除外値を割り当てます。頂点の順序が異なると、このアルゴリズムが使用する色の数も異なる場合があります。最適な彩色につながる順序は常に存在します。たとえば、頂点を色でソートすることにより最適な彩色から決定される順序がこれに該当しますが、それを見つけるのは難しい場合があります。完全に順序付け可能なグラフは、グラフ自体だけでなく、その誘導された部分グラフのすべてに対して貪欲アルゴリズムに最適な順序付けが存在するグラフとして定義されます。

より正式には、グラフGが完全に順序付け可能であるとは、 Gの頂点の順序 π が存在し、かつGのすべての誘導部分グラフが、その部分グラフの頂点によって誘導される π の部分列を用いた貪欲アルゴリズムによって最適に彩色される場合を言う。順序 π がこの性質を持つのは、abcdが誘導経路となる4つの頂点 a 、 b 、 c 、 d が存在せず、かつ順序付けにおいてaがbの前に現れ、かつc がd の後に現れる場合である。[ 1 ]

計算の複雑さ

完全に順序付け可能なグラフはNP完全である。[ 2 ]しかし、特定の順序付けがグラフの完全な順序付けであるかどうかをテストすることは容易である。したがって、グラフが既に完全に順序付け可能であることが分かっている場合でも、グラフの完全な順序付けを見つけることはNP困難である。

完全に順序付け可能なグラフはすべて完全グラフである。[ 1 ]

弦グラフは完全に順序付け可能であり、弦グラフの完全な順序付けは、グラフの完全な消去順序付けを逆にすることで実現できる。したがって、完全な順序付けに貪欲彩色を適用することで、弦グラフを最適に彩色するための効率的なアルゴリズムが得られる。比較可能性グラフもまた完全に順序付け可能であり、グラフの推移的向きの位相的順序付けによって完全な順序付けが与えられる。 [ 1 ]許容グラフの補グラフは完全に順序付け可能である。[ 3 ]

完全に順序付け可能なグラフの別のクラスは、グラフGによって与えられ、 Gの5頂点のすべての部分集合において、5頂点のうち少なくとも1つは、他の5頂点の閉近傍の部分集合（または等しい）である閉近傍を持つ。同様に、これらは、集合包含によって順序付けられた閉近傍の半順序が最大で幅4であるグラフである。5頂点サイクルグラフの近傍半順序は幅5であるため、4は完全な順序付け可能性を保証する最大幅である。弦グラフと同様に（そしてより一般的には完全に順序付け可能なグラフとは異なり）、幅4のグラフは多項式時間で認識可能である。[ 4 ]

弦グラフの完全な消去順序と完全な順序の中間の概念は、半完全な消去順序である。消去順序では、中央の頂点が3つのうち最初に消去される3頂点誘導パスは存在せず、半完全な消去順序では、中央の2つの頂点のうち1つが最初に消去される4頂点誘導パスは存在しない。したがって、この順序の逆は完全な順序の要件を満たすため、半完全な消去順序を持つグラフは完全に順序付け可能である。[ 5 ]特に、弦グラフの完全な消去順序を見つけるために使用される同じ辞書式幅優先探索アルゴリズムは、距離遺伝グラフの半完全な消去順序を見つけるために使用でき、したがって距離遺伝グラフも完全に順序付け可能である。 [ 6 ]

すべての頂点順序が完全順序となるグラフはコグラフです。コグラフは4頂点誘導パスを持たないグラフであるため、完全順序におけるパス順序の要件に違反することはありません。

完全に順序付け可能なグラフには、他にもいくつかのクラスが知られている。[ 7 ]

注記

  1. ^ a b cフヴァータル (1984) ;マフレー (2003)。
  2. ^ミッデンドルフとファイファー (1990) ;マフレー (2003)。
  3. ^ゴルムビック、モンマ、トロッター（1984）。
  4. ^パーヤン (1983) ;フェルスナー、ラガヴァン、スピンラッド (2003 )
  5. ^ Hoàng & Reed (1989) ; Brandstädt, Le & Spinrad (1999)、70ページと82ページ。
  6. ^ Brandstädt、Le & Spinrad (1999)、定理 5.2.4、p. 71.
  7. ^フヴァータルら。 (1987) ;ホアン＆リード (1989) ;ホアンら。 (1992) ;マフレー (2003) ; Brandstädt、Le & Spinrad (1999)、81–86 ページ。

参考文献

「 https://en.wikipedia.org/w/index.php?title=Perfectly_orderable_graph&oldid=1234815183」より取得