サムネイル|338x338ピクセル|カクタスグラフの例 カクタスグラフ（もしくは単にカクタス、カクタス木）は任意の2つの単純閉路が2つ以上の共通頂点を持たない連結グラフである。別の言い方をすれば、全ての辺が高々1つの閉路にしか含まれない連結グラフや、（非自明だが）全てのブロック（切断点のない最大部分グラフ）が閉路または辺となる連結グラフであると言える。
特徴 カクタスは平面グラフであり、外平面グラフ（outerplanar graph）でもある。また、疑似木（pseudotree）はカクタスである。全てのブロックが単純閉路または辺のいずれかである場合にのみ、非単純グラフ（連結な多重グラフ）はカクタスである。
各連結成分がカクタスである族は、「グラフの細分に対して閉じている」といえる。つまり、任意のカクタスの任意の細分はカクタスである。このグラフの族は、たった一つの禁断マイナーで特徴付けられ、完全グラフK4から1辺のみを除去した4頂点ダイヤモンドグラフがカクタスの禁断グラフである。
三角カクタス サムネイル|フレンドシップグラフの例。フレンドシップグラフは常に三角カクタスである。 三角カクタスグラフは、カクタスグラフの特殊な例であり、全ての閉路が3つの辺からなるグラフである。例えば、1つの共通頂点で連結された3つの辺からなる閉路C3からなるフレンドシップグラフは、三角カクタスグラフである。
マトロイド・パリティ問題のアルゴリズムを用いることで、任意のグラフから、そのグラフに含まれる最大の三角カクタスを多項式時間見つける事が可能である。三角カクタスは平面グラフである。そのため、グラフの平面化の重要な部分問題として、最大の三角カクタスは最大の平面グラフの部分グラフの近似として用いられる。この近似アルゴリズムの近似度は4/9であり、最大の平面部分グラフを見つける問題の最良の近似である。
最大の三角カクタスを見つけるアルゴリズムは最大のカクタスに含まれるC3の数についてのロヴァースとプラマーの定理を組み合わせたアルゴリズムである。
ローザの予想 三角カクタスに関連する重要な予想に、アレクサンダー・ローザのローザの予想「三角カクタスは、優美もしくはほぼ優美である」がある。 より正確には、
任意の三角カクタスは、t ≡ 0, 1 mod 4 個のブロックを持つならば優美に、 t ≡ 2, 3 mod 4 個のブロックを持つならばほぼ優美である。
アルゴリズムと応用 任意のグラフに対してはNP困難である施設配置問題などの問題は、カクタスに対しては多項式時間で解くことができる。
カクタスは外平面グラフの特殊な例であるため、多数のグラフの組合せ最適化問題を多項式時間で解くことができる。
カクタスを用いた電気回路の解析は有用な特徴を持つ。オペアンプをカクタスを用いて解析する応用がなされた。
カクタスは、異なるゲノム間またはゲノムの部分間の関係の表現方法として、比較ゲノミクスの分野で用いられている。
もしカクタスの各頂点が高々2つのブロックにしか属さない場合、そのグラフをクリスマスカクタスと呼ぶ。多面体グラフ（polyhedral graph）はその頂点全てを用いるクリスマスカクタスを部分グラフとして持つ。これは、多面体グラフがユークリッド平面にgreedy embeddingを持ち、任意の頂点間でのルーティングが、greedy forwardingによって成功するというの証明において重要な役割を果たした。
トポロジカルグラフ理論では、cellar embeddingが「平面」であるグラフは、各頂点が高々1つの閉路にしか含まれないカクタスの部分族である。これらのグラフ族は、ダイヤモンドグラフと5頂点フレンドシップグラフという2つの禁断マイナーを持つ。
歴史 カクタスは、伏見康治の功績を讃え、フランク・ハラリーとジョージ・ウーレンベックにHusimi trees（伏見木）と名付けられた。そのハラリーとウーレンベックの論文では、全ての閉路が3辺からなるもののみ「cactus」と呼んでいたが、現在は辺の数にかかわらず「カクタス」と呼ばれている。
その一方で、伏見木と言う名前は現在「全てのブロックが完全グラフであるグラフ」を指すようになった。しかし、これは伏見の功績とはほとんど関係がないため現在はブロックグラフと呼ばれており、このような曖昧さを回避するために、伏見木が現在のカクタスを指すことは少なくなったSee, e.g., , a 1983 review by Robert E. Jamison of a paper using the other definition, which attributes the ambiguity to an error in a book by Mehdi Behzad and Gary Chartrand.。
References
外部リンク
Application of Cactus Graphs in Analysis and Design of Electronic Circuits