三角カクタス
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/12/10 18:35 UTC 版)
三角カクタスグラフは、カクタスグラフの特殊な例であり、全ての閉路が3つの辺からなるグラフである。例えば、1つの共通頂点で連結された3つの辺からなる閉路C3からなるフレンドシップグラフは、三角カクタスグラフである。 マトロイド・パリティ問題のアルゴリズムを用いることで、任意のグラフから、そのグラフに含まれる最大の三角カクタスを多項式時間見つける事が可能である。三角カクタスは平面グラフである。そのため、グラフの平面化の重要な部分問題として、最大の三角カクタスは最大の平面グラフの部分グラフの近似として用いられる。この近似アルゴリズムの近似度は4/9であり、最大の平面部分グラフを見つける問題の最良の近似である。 最大の三角カクタスを見つけるアルゴリズムは最大のカクタスに含まれるC3の数についてのロヴァースとプラマーの定理を組み合わせたアルゴリズムである。
※この「三角カクタス」の解説は、「カクタスグラフ」の解説の一部です。
「三角カクタス」を含む「カクタスグラフ」の記事については、「カクタスグラフ」の概要を参照ください。
ウィキペディア小見出し辞書の「三角カクタス」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 三角カクタスのページへのリンク
