サボテングラフ

グラフ理論では、サボテン（サボテンの木と呼ばれることもある）は、任意の2 つの単純閉路が最大で 1 つの頂点を共有する連結グラフです。同様に、すべての辺が最大で 1 つの単純閉路に属する連結グラフ、または（非自明なサボテンの場合）すべてのブロック（カット頂点のない最大サブグラフ）が辺または閉路である連結グラフです。

サボテンは外平面グラフです。すべての疑似木はサボテンです。非自明なグラフがサボテンとなるのは、すべてのブロックが単純なサイクルまたは単一のエッジ である場合のみです。

各要素がサボテンであるグラフの族は、グラフマイナー演算の下で下向きに閉じている。このグラフ族は、完全グラフK ₄から辺を1つ削除して形成される4頂点ダイヤモンドグラフである単一の禁制マイナーグラフによって特徴付けられる。^[1]

三角サボテンは、各サイクルの長さが 3 で、各辺がサイクルに属する特殊なタイプのサボテン グラフです。たとえば、単一の共有頂点で結合された三角形のコレクションから形成されるグラフである友情グラフは、三角サボテンです。三角サボテンは、サボテン グラフであるだけでなく、ブロック グラフや局所線形グラフでもあります。

三角形のサボテンは、頂点が一つでも取り除かれても連結されたままになるという性質を持っています。与えられた数の頂点に対して、この性質を持つ辺は最も少なくなります。頂点の数が奇数の木はどれも、辺を追加することで三角形のサボテンに拡張でき、頂点が取り除かれた後も連結されたままになるという性質を持つ最小限の拡張になります。^[2]

マトロイドパリティ問題のアルゴリズムを使用すると、任意のグラフ内の最大の三角サボテンを多項式時間で見つけることができます。三角サボテングラフは平面グラフであるため、最大の三角サボテンは、平面化における重要な部分問題である最大平面部分グラフの近似として使用できます。近似アルゴリズムとして、この方法は近似比が4/9で、最大平面部分グラフ問題で最もよく知られています。^[3]

最大の三角形サボテンを見つけるアルゴリズムは、この最大のサボテンに含まれる三角形の数を特徴付けるロヴァースとプラマーの定理に関連している。^[4] ロヴァースとプラマーは、与えられたグラフの頂点と辺を部分集合に分割するペアを考察する。このとき、グラフのすべての三角形は、頂点分割の単一クラスに 2 つの頂点を持つか、辺分割の単一クラスに 3 つの辺すべてを持つという性質を持つ。彼らは、この性質を持つ分割のペアを有効と呼ぶ。すると、最大の三角形サボテンに含まれる三角形の数は、有効な分割のペアとの最大数に等しくなる。 ${\displaystyle {\mathcal {P}}=\{V_{1},V_{2},\dots ,V_{k}\}}$${\displaystyle {\mathcal {Q}}=\{E_{1},E_{2},\dots ,E_{m}\}}$

${\displaystyle \sum _{i=1}^{m}{\frac {(u_{i}-1)}{2}}+nk,}$、

ここで、は指定されたグラフ内の頂点の数であり、は辺クラス が満たす頂点クラスの数です。 ${\displaystyle n}$${\displaystyle u_{i}}$${\displaystyle E_{i}}$

すべての平面グラフ には、少なくとも三角形の面の一部を含むサボテンサブグラフが含まれています。この結果は、上記の最小最大公式を使用せずに、最大平面サブグラフ問題に対する4/9近似アルゴリズムを直接分析することを意味します。^[5]${\displaystyle G}$${\displaystyle C\subseteq G}$${\displaystyle 1/6}$${\displaystyle G}$

三角形のサボテンに関する重要な予想は、アレクサンダー・ローザにちなんで名付けられたローザの予想であり、三角形のサボテンはすべて優美であるか、ほぼ優美であるというものである。 ^[6]より正確には

t ≡ 0, 1 mod 4 ブロックを持つすべての三角形サボテンは優美であり、t ≡ 2, 3 mod 4 を持つものはほぼ優美です。

一般的なグラフではNP困難な施設配置問題や、その他のグラフ問題も、サボテンでは多項式時間で解ける可能性がある。^{[7] [8]}

サボテンは外平面グラフの特殊なケースなので、グラフ上の多くの組み合わせ最適化問題は多項式時間で解くことができる可能性がある。^[9]

サボテンは有用な特性を持つ電気回路を表現します。サボテンの初期の応用はオペアンプの表現に関連していました。^{[10] [11] [12]}

サボテンは比較ゲノム学においても、異なるゲノムやゲノムの一部間の関係性を表現する方法として使われてきました。^[13]

サボテンが連結しており、各頂点が最大でも 2 つのブロックに属している場合、それはクリスマス カクタスと呼ばれます。すべての多面体グラフには、そのすべての頂点を含むクリスマス カクタス サブグラフがあります。この事実は、Leighton & Moitra (2010) による証明で重要な役割を果たしています。この証明では、すべての多面体グラフはユークリッド平面に貪欲埋め込みを持ち、貪欲転送によってすべての頂点ペア間でメッセージをルーティングできる頂点への座標の割り当てが可能であることを示しています。^[14]

位相グラフ理論では、セル埋め込みがすべて平面であるグラフは、各頂点が最大で1つのサイクルに属するという追加の特性を持つサボテングラフのサブファミリーです。これらのグラフには、ダイヤモンドグラフと5頂点の友情グラフという2つの禁制マイナーグラフがあります。^[15]

サボテンは最初、フランク・ハラリとジョージ・ユージン・ウーレンベックが、コディ・フシミによるこのグラフの研究に敬意を表してフシミの木という名前で研究されました。^{[16] [17]}同じハラリとウーレンベックの論文では、すべてのサイクルが三角形であるこのタイプのグラフに「サボテン」という名前が付けられていますが、現在ではあらゆる長さのサイクルを許可するのが標準となっています。

一方、フシミツリーという名前は、すべてのブロックが完全グラフであるグラフ（つまり、他のグラフのブロックの交差グラフ）を指すようになりました。この用法はフシミの研究とはほとんど関係がなく、より適切な用語であるブロックグラフがこのグループに使用されています。ただし、この曖昧さのため、このフレーズはサボテングラフを指すためにあまり使用されなくなりました。^[18]

• 電子回路の解析と設計におけるサボテングラフの応用