導入
グラフ理論では、区間グラフは実数直線の区間の集合の交差グラフです。区間グラフの各頂点はセットの区間を表し、対応する 2 つの区間が交差するときにエッジが 2 つの頂点を接続します。
正式な定義
させて
- $$ {I_1, I_2, \ldots, I_n \subset\R} $$
間隔。すると、対応する区間グラフは次のようになります。
- $$ { V = \{I_1, I_2, \ldots, I_n\} } $$
そして
- $$ { \{I_\alpha, I_\beta\} \in E \iff I_\alpha \cap I_\beta \neq \emptyset. } $$
プロパティ
区間グラフはコーダルグラフであるため、完全なグラフになります。それらの相補的なグラフは比較可能グラフであり、比較可能関係は正確に区間順序です。
適切な区間グラフとは、区間表現が他の区間内に含まれない区間グラフである。単位区間グラフは、各区間の長さが 1 である区間表現を持つ区間グラフです。これら 2 つのクラスは実際には同等であることが示されています。
アプリケーション
間隔グラフは 、オペレーションズ リサーチにおけるリソース割り当ての問題をモデル化するために使用されます。各間隔は、特定の時間におけるリソースの割り当てを表します。最大の安定したグラフの検索は、競合なしで達成できるリソースの最適な割り当てに対応します。
間隔グラフを表す一連の間隔を見つけることは、連続する DNA 配列を組み立てる方法にもなりえます。
効率的な区間グラフ認識アルゴリズム
指定されたグラフG = ( V , E )が区間グラフであるかどうかの判断は、包含ノードを考慮しながら連続するGの最大クリークの順序を探すことによって、時間計算量O ( | V | + | E | )で行うことができます。 。正式には、グラフG は、最大クリークが存在する場合に限り、区間グラフになります。
Booth と Lueker による、グラフが線形時間の区間グラフであるかどうかを判断するための元のアルゴリズムは、複雑なPQ ツリーに基づいていますが、Habib らは、グラフが次のとおりであるという事実を利用して、問題をより簡単に解決する方法を示しました。は、その補完グラフのみが比較グラフである場合、区間グラフです。