区間グラフ

グラフ理論において、区間グラフは、実数直線上の区間の集合から形成される無向グラフであり、各区間に頂点があり、区間が交差する頂点間に辺がある。区間の 交差グラフである。

区間グラフは、弦グラフと完全グラフです。これらは線形時間で認識でき、これらのグラフの最適なグラフカラーリングまたは最大クリークは線形時間で見つけることができます。区間グラフには、すべての適切な区間グラフ、つまり単位区間の集合から同じ方法で定義されたグラフが含まれます。

これらのグラフは、食物網をモデル化したり、重複しない時間に実行されるタスクのサブセットを選択する必要があるスケジュールの問題を研究したりするために使用されています。その他の用途には、DNAマッピングにおける連続したサブシーケンスの組み立てや、時間的推論などがあります。

区間グラフは、区間の族から形成される 無向グラフGである。

${\displaystyle S_{i},\quad i=0,1,2,\dots }$

各区間S _iに1つの頂点v _{i を}作成し、対応する2つの集合が空でない交差を持つ場合は常に2つの頂点v _iとv _{j を}辺で接続する。つまり、 Gの辺集合は

${\displaystyle E(G)=\{(v_{i},v_{j})\mid S_{i}\cap S_{j}\neq \emptyset \}.}$

区間の 交差グラフです。

グラフ内の3 つの独立した頂点は、各 2 つの頂点に対して、その 2 つを含むが 3 つ目の頂点の隣接点がないパスが存在する場合、アステロイド トリプル (AT)を形成します。アステロイド トリプルがない場合、グラフは AT フリーです。区間グラフの最も初期の特徴付けは次のようになります。

• グラフが区間グラフであるためには、それが弦グラフであり、かつATフリーでなければならない。^[1]

その他の特徴:

• グラフが区間グラフであるためには、そのグラフの最大クリークを、そのクリークのうちの2つに属する各頂点が、順序付けにおいてそれらのクリークの間にあるすべてのクリークにも属するように順序付けできる必要がある。つまり、 である任意の に対して、であるときはいつでもとなる。^[2]${\displaystyle M_{1},M_{2},\dots ,M_{k}}$${\displaystyle v\in M_{i}\cap M_{k}}$${\displaystyle i<k}$${\displaystyle v\in M_{j}}$${\displaystyle i<j<k}$
• グラフが区間グラフであるとは、サイクルグラフを 誘導部分グラフとして含まず、比較可能性グラフの補グラフである場合に限ります。^[3]${\displaystyle C_{4}}$

区間グラフとその変種の様々な特徴付けが記述されている。^[4]

与えられたグラフが区間グラフであるかどうかの判定は、頂点の包含に関して連続する最大クリークの順序を求めることによって時間内に行うことができる。この問題に対する既知のアルゴリズムの多くはこのように動作するが、クリークを使わずに線形時間で区間グラフを認識することも可能である。^[5]${\displaystyle G=(V,E)}$${\displaystyle O(|V|+|E|)}$${\displaystyle G}$

Booth & Lueker (1976) のオリジナルの線形時間認識アルゴリズムは複雑なPQ ツリーデータ構造に基づいていますが、Habib ら (2000) は、グラフが区間グラフである場合に限り、それが弦グラフであり、その補グラフが比較可能性グラフであるという事実に基づいて、辞書式幅優先探索を使用して、より単純に問題を解決する方法を示しました。^[6] 6 スイープ LexBFS アルゴリズムを使用する同様のアプローチは、Corneil、Olariu、Stewart (2009) で説明されています。

区間グラフをATフリー弦グラフとして特徴付けると^[1]、区間グラフは強く弦グラフであり、したがって完全グラフである。その補グラフは比較可能性グラフのクラスに属し、^[3]比較可能性関係はまさに区間順序である。^[7]

グラフが区間グラフとなるのは、それが弦グラフであり、その補グラフが比較可能性グラフである場合に限るという事実から、グラフとその補グラフが両方とも区間グラフとなるのは、グラフが分割グラフであり、かつ順列グラフである場合に限るということになります。

2 つの区間が互いに素であるか入れ子になっている区間表現を持つ区間グラフは、自明に完全なグラフです。

グラフの箱型性は、区間グラフの場合に限り、最大で 1 です。任意のグラフの箱型性とは、区間グラフの辺集合の交差が であるような、同じ頂点集合上の区間グラフの最小数です。 ${\displaystyle G}$${\displaystyle G}$

円弧の交差グラフは、区間グラフを含むグラフのクラスである円弧グラフを形成します。台形グラフは、すべての平行辺が同じ 2 本の平行線上にある台形の交差であり、区間グラフの一般化でもあります。

連結された三角形のない区間グラフはまさにキャタピラーツリーである。^[8]

適切な区間グラフとは、区間表現においてどの区間も他の区間を適切に含まない区間グラフである。単位区間グラフとは、各区間の長さが単位である区間表現を持つ区間グラフである。区間が繰り返されない単位区間表現は、必ず適切な区間表現となる。すべての適切な区間表現が単位区間表現であるわけではないが、すべての適切な区間グラフは単位区間グラフであり、その逆もまた同様である。^[9]すべての適切な区間グラフはクローフリーグラフである。逆に、適切な区間グラフはクローフリー区間グラフそのものである。しかし、区間グラフではないクローフリーグラフも存在する。^[10]

ある区間が他の区間よりも多く含まれない表現がある場合、その区間グラフは -適切であると呼ばれます。この概念は、適切な区間グラフの考え方を拡張したもので、0-適切な区間グラフは適切な区間グラフです。^[11] ある区間が他の区間よりも多く含まれない表現がある場合、その区間グラフは -不適切であると呼ばれます。この概念は、適切な区間グラフの考え方を拡張したもので、0-不適切区間グラフは適切な区間グラフです。^[12] ある区間グラフは、区間の長さの連鎖が互いに入れ子になっていない場合、 -入れ子になっています。これは適切な区間グラフの一般化であり、1-入れ子の区間グラフはまさに適切な区間グラフです。^[13]${\displaystyle q}$${\displaystyle q}$${\displaystyle p}$${\displaystyle p}$${\displaystyle k}$${\displaystyle k+1}$

区間グラフの数学的理論は、 RANDコーポレーションの数学科の研究者による応用を視野に入れて開発された。この研究者には、ピーター・C・フィッシュバーンなどの若手研究者や、アラン・C・タッカーやジョエル・E・コーエンなどの学生、そしてデルバート・ファルカーソンや（常連客の）ヴィクター・クレーなどの指導者が含まれていた。^{[14]コーエンは、区間グラフを}個体群生物学、特に食物網の数学的モデルに適用した。^[15]

区間グラフは、オペレーションズ・リサーチやスケジューリング理論における資源割り当て問題を表すために使用されます。これらのアプリケーションでは、各区間は特定の期間の資源（分散コンピューティングシステムの処理装置や授業の部屋など）の要求を表します。グラフの最大重み独立集合問題は、競合せずに満たすことができる要求の最良のサブセットを見つける問題を表します。^[16]詳細については、 区間スケジューリングを参照してください。

区間グラフの最適なグラフカラーリングは、可能な限り少ないリソースですべてのリクエストをカバーするリソースの割り当てを表します。これは、区間を左端点でソートして色付けする貪欲カラーリングアルゴリズムによって多項式時間で見つけることができます。^[17]

その他の応用としては、遺伝学、バイオインフォマティクス、コンピュータサイエンスなどがある。区間グラフを表す区間集合を見つけることは、DNAマッピングにおいて連続した部分列を組み立てる方法としても利用できる。^[18]区間グラフは時間的推論においても重要な役割を果たしている。^[19]

が任意のグラフである場合、の区間完備化は を部分グラフとして 含む同じ頂点集合上の区間グラフである。区間完備化のパラメータ化されたバージョン（k 個の追加辺を持つ区間スーパーグラフを見つける）は固定パラメータで扱いやすく、さらにパラメータ化された指数時間未満で解ける。^{[20] [21]}${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$

区間グラフのパス幅は、その最大クリークのサイズより1小さい（または、その彩色数より1小さい）値であり、任意のグラフのパス幅は、その区間グラフをサブグラフとして含む最小のパス幅と同じである。^[22]${\displaystyle G}$${\displaystyle G}$

ラベルなし頂点上の連結区間グラフの数は、次の通りである: ^[23]${\displaystyle n}$${\displaystyle n=1,2,3,\dots }$

1、1、2、5、15、56、250、1328、8069、54962、410330、3317302、...（OEISの配列A005976）

連結性を仮定しない場合、その数はさらに大きくなる。必ずしも連結しているわけではないラベルのない頂点上の区間グラフの数は次のようになる。 ^[24]${\displaystyle n}$

1、2、4、10、27、92、369、1807、10344、67659、491347、3894446、...（OEISの配列A005975）

これらの数は指数関数的増加よりも速いことを示しています。ラベルのない頂点上の区間グラフの数は少なくとも です。^{[25]この急速な増加率のため、区間グラフは}双子幅が制限されていません。^[26]${\displaystyle 3n}$${\displaystyle n!/3^{3n}}$

• 「区間グラフ」、グラフクラスとその包含に関する情報システム
• ワイスシュタイン、エリック W.、「区間グラフ」、MathWorld