交差数（グラフ理論）

数学の分野であるグラフ理論において、グラフの交差数とは、 を有限集合の交差グラフとして表現したときの要素の最小数である。このような表現では、各頂点は集合として表現され、2つの頂点は、それらの集合に共通要素がある場合には必ず辺で接続される。同様に、交差数はのすべての辺をカバーするのに必要なクリークの最小数である。^{[1] [2]}${\displaystyle G=(V,E)}$${\displaystyle G}$${\displaystyle G}$

グラフのすべての辺を覆うクリークの集合は、クリーク辺被覆^[3]または辺クリーク被覆^[4]、あるいは単にクリーク被覆と呼ばれることもあるが、最後の用語は曖昧である。クリーク被覆は、グラフのすべての頂点を覆うクリークの集合であることもある。^[5]「被覆」の代わりに「被覆」が使われることもある。^[6]交差点数と呼ばれるのと同様に、これらのクリークの最小数は、Rコンテンツ^{[7] 、} 辺クリーク被覆数^[4]、あるいはクリーク被覆数[ ^8]と呼ばれてきた。交差点数を計算する問題は、交差点数問題^[9] 、交差点グラフ基底問題^[10] 、クリークによる被覆^[10]、辺クリーク被覆問題^[9]、キーワード競合問題^[2]と呼ばれてきた。

頂点と辺を持つすべてのグラフの交差数は最大 です。交差数を計算または近似することはNP 困難ですが、固定パラメータで扱いやすい です。 ${\displaystyle n}$${\displaystyle m}$${\displaystyle \min(m,n^{2}/4)}$

を任意の集合族とし、内の集合が繰り返されることを許す。の交差グラフは、内の各集合に対して頂点を持ち、 2 つの集合の間には空でない交差を持つ辺を持つ無向グラフである。すべてのグラフは、このようにして交差グラフとして表すことができる。^[11]グラフの交差数とは、内の集合の和集合が要素を持つようなこのタイプの表現が存在する最小の数である。^{[1]与えられた要素数を持つグラフの交差表現を見つける問題は、}交差グラフ基底問題として知られている。^[10]${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle k}$${\displaystyle {\mathcal {F}}}$${\displaystyle k}$

グラフの交差数の別の定義は、グラフの辺をすべて覆う（グラフの完全部分グラフ）内のクリークの最小数である、というものである。^{[1] [12]}この性質を持つクリークの集合はクリーク辺被覆または辺クリーク被覆と呼ばれ、このため交差数は辺クリーク被覆数と呼ばれることもある。^[4]${\displaystyle G}$${\displaystyle G}$ ${\displaystyle G}$${\displaystyle G}$

交差点の数と辺クリーク被覆数の等号は簡単に証明できる。一方向では、 が集合の族の交差点グラフであり、その和集合が であるものとする。すると、任意の要素 について、を含む集合に対応するの頂点の部分集合はクリークを形成する。この部分集合内の任意の 2 つの頂点は隣接している。なぜなら、それらの集合には を含む空でない交差点があるからである。さらに、 のすべての辺はこれらのクリークのいずれかに含まれる。辺が要素 を含む集合の空でない交差点から来ている場合、その辺は のクリークに含まれる。したがって、 の辺は の要素ごとに 1 つずつクリークで被覆することができる。^[12]${\displaystyle G}$${\displaystyle {\mathcal {F}}}$${\displaystyle U}$${\displaystyle k}$${\displaystyle x\in U}$${\displaystyle G}$${\displaystyle x}$${\displaystyle x}$${\displaystyle G}$${\displaystyle y}$${\displaystyle y}$${\displaystyle G}$${\displaystyle k}$${\displaystyle U}$

逆に、グラフがクリークで覆われる場合、グラフの各頂点は、頂点 を含むクリークの部分集合によって表すことができます。これらの部分集合のうち 2 つ、つまり 2 つの頂点とに対して、交差内に両方を含むクリークがある場合に限り、交差内に空でない交差があり、また、被覆クリークの 1 つに含まれる辺がある場合に限ります。 ^[12]${\displaystyle G}$${\displaystyle k}$${\displaystyle v}$${\displaystyle G}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle uv}$

グラフを集合の抽象的な交差グラフとして表現すると、同じグラフのより具体的な幾何学的交差表現を構築するために使用できます。特に、グラフの交差数が の場合、そのグラフは- 次元単位超球面の交差グラフとして表現できます（その球面性は最大 です）。^{[4] [13]}${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

クリークカバーは、グラフの隣接ラベル付け方式の一種として使用できます。この方式では、各頂点に、クリークごとに 1 ビットのバイナリ値 (クリークに属していない場合は 0、属している場合は 1) でラベル付けします。2 つの頂点が隣接しているのは、ラベルのビットごとの論理積が 0 以外の場合のみです。ラベルの長さがグラフの交差数です。この方法は、IBM の E. Kellerman によって、キーワードのセットにラベルを付けて競合するキーワードをすばやく検出するために、交差数の初期のアプリケーションで使用されました。このため、交差数を計算する問題はキーワード競合問題とも呼ばれています。^{[14] [15]}同様に、計算幾何学では、交差数に基づく表現が可視性グラフのコンパクトな表現と考えられてきましたが、この表現ではほぼ 2 乗の数のクリークを必要とする幾何学的入力が存在します。^[16]

別の種類のアプリケーションは、共有リソースの複数のユーザーをタイムスロットにスケジュールする問題から生まれます。このとき、互換性のない要求が同じタイムスロットにスケジュールされることはなく、互換性のある要求のすべてのペアに少なくとも 1 つのタイムスロットが一緒に割り当てられる必要があります。互換性のグラフの交差数は、このようなスケジュールに必要なタイムスロットの最小数を示します。^[2]非常に長い命令語を持つコンピューターのコンパイラーの設計では、互換性のない操作のグラフの小さなクリーク カバーを使用して、それらの非互換性を少数の人工リソースで表すことができます。これにより、リソース ベースのスケジューリング手法を使用して、操作を命令スロットに割り当てることができます。^[17]

シェパードとベッタは、ネットワークの交差数は、最大独立集合を計算する問題の整数計画法で必要な制約の最小数に等しいと指摘している。この数には、頂点ごとに 0-1 の変数があり、クリークカバーの各クリークでは変数の合計が最大 1 になるという制約がある。彼らは、特定の光ファイバー通信ネットワークのパスの交差グラフでは、これらの交差数は小さく、ネットワーク上で帯域幅を割り当てる特定の最適化問題を解くのが比較的簡単であると主張している。^[3]

統計学とデータ可視化では、統計的に区別できない変数のペアを表すグラフのエッジクリークカバーは、各クリークに文字やその他の視覚的なマーカーを割り当て、どの変数が区別できないかをグラフィカルに表現することで、複数のペア比較を視覚化するのに役立つコンパクトな文字表示を作成するために使用されます。^{[18] [19]}

動物種間の捕食者と被食者の関係を記述する食物網の解析において、競争グラフまたはニッチ重複グラフは、頂点が種を表し、辺が同じ獲物をめぐって競合する種のペアを表す無向グラフです。これらは、捕食者と被食者の関係を表す有向非巡回グラフから、捕食者と被食者の関係グラフが辺と を持つような獲物種が存在する場合は常に競争グラフに辺を描くことによって導出できます。すべての競争グラフには少なくとも 1 つの孤立した頂点があり、任意のグラフの競争数は、競争グラフにするために追加できる孤立した頂点の最小数を表します。生物学的には、競争グラフの一部が観察される場合、競争数は、それを説明するために必要な、観察されていない獲物種の最小数を表します。競争数は、最大で交差点の数に等しくなります。つまり、辺クリーク被覆内の各クリークに獲物種を追加することで、任意の無向グラフを競争グラフに変換できます。しかし、この関係は正確ではない。なぜなら、捕食種が他の種の獲物になる可能性もあるからだ。頂点を持つグラフでは、最大でそれらの頂点が複数の他の種の獲物になる可能性があるため、競争数は少なくとも交差点の数から引いた数になる。^[20]${\displaystyle uv}$${\displaystyle w}$${\displaystyle u\to w}$${\displaystyle v\to w}$${\displaystyle n}$${\displaystyle n-2}$${\displaystyle n-2}$

エッジクリーク被覆は、タンパク質間の相互作用のみを記述するタンパク質間相互作用ネットワークから、相互作用するタンパク質のシステムであるタンパク質複合体の存在を推測するためにも使用されている。 ^[21]より一般的には、ギヨームとラタピは、あらゆる種類の複雑なネットワークについて、ネットワークを、その頂点をクリーク被覆内のクリークに接続する二部グラフに置き換えると、ネットワークの構造が強調されると主張している。^[22]

自明なことに、辺を持つグラフの交差数は最大 である。各辺はそれ自体が 頂点クリークである。このようなクリークは 個あり、それらが一緒にすべての辺をカバーします。^[23]また、頂点を持つすべてのグラフの交差数は最大 個であることも事実です。さらに強いことは、すべての -頂点グラフの辺は最大 個のクリークでカバーすることができ、そのクリークはすべて単一の辺または三角形のいずれかである。このカバーを見つけるアルゴリズムは単純です。任意の 2 つの隣接する頂点を削除し、残りのグラフを帰納的にカバーします。削除した 2 つの頂点を復元し、共有する隣接頂点への辺を三角形でカバーし、共有しない隣接頂点への辺を 頂点クリークとして残します。帰納的カバーには最大 個のクリークがあり、削除した 2 つの頂点は最大 個のクリークに寄与し、他のすべての頂点が共有しない隣接頂点であり、2 つの頂点間の辺をクリークとして使用する必要がある場合に最大になります。これら 2 つの量を加算すると、クリークの合計が得られます。^{[2] [12]}これは、三角形のないグラフには最大で 個の辺があるというマンテルの定理を一般化したもので、三角形のないグラフでは、唯一の最適なクリーク辺被覆は辺ごとに1つのクリークを持つため、交差数は辺の数に等しい。^[2]${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle n}$${\displaystyle \lfloor n^{2}/4\rfloor }$${\displaystyle n}$${\displaystyle \lfloor n^{2}/4\rfloor }$${\displaystyle \lfloor (n-2)^{2}/4\rfloor }$${\displaystyle n-1}$${\displaystyle \lfloor n^{2}/4\rfloor }$${\displaystyle \lfloor n^{2}/4\rfloor }$

辺の数が より確実に大きい場合、さらに厳しい境界が可能です。が与えられたグラフ において辺で接続されていない頂点のペアの数であり、が となる唯一の整数であるとします。このとき、 の交差数は最大 です。^{[2] [24]}疎グラフの補グラフの交差数は小さくなります。つまり、任意の-頂点グラフの交差数は最大 です。ここで、は自然対数の底であり、は の補グラフの最大次数です。^[6]${\displaystyle {\tfrac {n^{2}}{4}}}$${\displaystyle p}$${\displaystyle G}$${\displaystyle t}$${\displaystyle (t-1)t\leq p<t(t+1)}$${\displaystyle G}$${\displaystyle p+t}$${\displaystyle n}$${\displaystyle G}$${\displaystyle 2e^{2}(d+1)^{2}\ln n}$${\displaystyle e}$${\displaystyle d}$${\displaystyle G}$

クローフリーグラフの構造に関する詳細な結果から、連結された- 頂点のクローフリーグラフに少なくとも 3 つの独立した頂点がある場合、その交差数は最大 であることがわかります。大きな独立集合を持たなくても、すべてのクローフリーグラフに当てはまるかどうかは、未解決の問題です。^[8]クローフリーグラフの重要なサブクラスは、他のグラフの辺と接触する辺のペアを表すグラフである線グラフです。線グラフの最適なクリーク被覆は、 2 つまたは 3 つの次数 2 の頂点を持つの各三角形に対して 1 つのクリーク、および次数が少なくとも 2 でこれらの三角形のいずれかの次数 2 の頂点ではない各頂点に対して 1 つのクリークで形成されます。交差数は、これら 2 種類のクリークの数です。^[7]${\displaystyle n}$${\displaystyle n}$${\displaystyle G}$${\displaystyle L(G)}$${\displaystyle G}$

ランダムグラフのエルデシュ・レーニ・ギルバートモデルでは、ラベル付き頂点上のすべてのグラフが等しくあり得る（または、各辺が他の辺とは独立して確率 で存在または存在しない）場合、 -頂点ランダムグラフの交差数は高い確率で辺の数の係数だけ小さくなります。これらのグラフでは、最大のクリークは（高い確率で）対数個の頂点しか持たないため、すべての辺をカバーするにはこれだけの数のクリークが必要であることがわかります。境界の難しい部分は、多くの辺をカバーするのに十分な対数サイズのクリークを見つけることができ、残りの残りの辺を2頂点クリークでカバーできることを証明することです。^{[25] [26]}${\displaystyle n}$${\displaystyle {\tfrac {1}{2}}}$${\displaystyle n}$$${\displaystyle \Theta \left({\frac {n^{2}}{\log ^{2}n}}\right),}$$${\displaystyle \log^{2}n}$

交差数に関する初期の研究の多くは、完全なサブグラフや完全なマッチングをより大きな完全グラフから削除することによって形成されるグラフなど、さまざまな特定のグラフ上で交差数を計算することを目的としていました。^[27]

与えられたグラフの交差数が与えられた数以下であるかどうかをテストすることはNP完全である。^{[10] [7] [15]したがって、与えられたグラフの交差数を計算することもNP困難である。逆に、交差数の困難さは、}分割されたグラフの正方形を認識することがNP完全であることを証明するために使用されている。^[28]${\displaystyle G}$${\displaystyle k}$

しかし、交差点の数を計算する問題は、固定パラメータで扱いやすい、つまり、 の多項式に交差点の数の大きいが計算可能な関数を掛けた時間で解くことができる。^{[5] [29]}これは、グラフに最大で個の異なる閉近傍があること(同じクリークの集合に属する 2 つの頂点は同じ近傍を持つ) と、閉近傍ごとに 1 つの頂点を選択して形成されるグラフの交差点の数が元のグラフと同じであることを観察することで示せる。^{[5] [30]}したがって、多項式時間で、入力を最大で個の頂点と辺を持つより小さなカーネルに縮小できる。このカーネルの辺のサブセットに指数時間の動的計画法検索手順を適用すると、では二重指数である時間 が得られる。^{[5] [29] への}二重指数依存性は、多項式階層が崩壊しない限り、多項式サイズのカーネル化によって単一指数依存性に縮小することはできない。 ^[31]また、指数時間仮説が正しい場合は、カーネル化が使用されているかどうかに関係なく、二重指数依存性が必要である。^[29]木幅が制限されたグラフでは、グラフの木分解に対する動的計画法によって、交差数を線形時間で見つけることができますが、^{[32] [21]}有限集合の縮小規則に基づくより単純なアルゴリズムは機能しません。^[32]${\displaystyle n}$${\displaystyle k}$${\displaystyle 2^{k}}$${\textstyle 2^{k}}$${\displaystyle O(4^{k})}$ ${\displaystyle 2^{O(4^{k})}+n^{O(1)}}$${\displaystyle k}$${\displaystyle k}$

この問題は、ある定数 に対して、よりも良い近似比で多項式時間で近似することはできない。 ^[33]また、最良の近似比は、自明な近似比よりも多対数係数だけ優れていることが知られている。^[5]この分野の研究者は、ヒューリスティックの計算効率についても調査したが、ヒューリスティックが生成する解の品質は保証されておらず、実際のネットワーク上での挙動も調査した。^{[5] [34]}${\displaystyle n^{c}}$${\displaystyle c}$${\displaystyle O(n^{2})}$

グラフの特定の特殊なクラスでは、より効率的なアルゴリズムが知られています。区間グラフの交差数は常に最大クリークの数に等しく、これは多項式時間で計算できます。^{[35] [36]}より一般的には、弦グラフでは、グラフの消去順序（各頂点とその後の隣接頂点がクリークを形成する順序）で頂点を考慮し、各頂点について、に接続する辺の少なくとも1つが以前のクリークで覆われていない場合は常に、およびその後の隣接頂点に対してクリークを形成するアルゴリズムによって交差数を計算できます。 ^[36]円弧グラフでは、線形時間で交差数を見つけることも可能です。^[37]しかし、これらのグラフには被覆に選択できるクリークが多項式数しかないにもかかわらず、クリークの数が少ないだけでは問題を容易にするのに十分ではありません。多項式数のクリークを持つグラフの族が存在し、その交差数はNP困難のままです。^[9]交差数は、最大次数が5のグラフでは多項式時間で見つけることができますが、最大次数が6のグラフではNP困難です。^{[38] [39]}平面グラフでは、交差数を正確に計算することはNP困難のままですが、ベイカーの手法に基づく多項式時間の近似スキームがあります。^[21]${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$

• 二部次元、グラフのすべての辺をカバーするために必要な二部クリークの最小数
• 境界グラフ、特殊な形式のクリーク辺被覆を特徴とするグラフの一種
• クリーク被覆、グラフのすべての頂点を覆う少数のクリークを見つけるNP困難な問題

• ワイスシュタイン、エリック W.、「交差数」、MathWorld