Wikipedia

カクタスグラフ

カクタスグラフ（もしくは単にカクタス、カクタス木）は任意の2つの単純閉路が2つ以上の共通頂点を持たない連結グラフである。別の言い方をすれば、全ての辺が高々1つの閉路にしか含まれない連結グラフや、（非自明だが）全てのブロック（切断点のない最大部分グラフ）が閉路または辺となる連結グラフであると言える。

カクタスグラフの例

特徴 編集

カクタスは平面グラフであり、外平面グラフ（outerplanar graph）でもある。また、疑似木（pseudotree）はカクタスである。全てのブロックが単純閉路または辺のいずれかである場合にのみ、非単純グラフ（連結な多重グラフ）はカクタスである。

各連結成分がカクタスである族は、「グラフの細分に対して閉じている」といえる。つまり、任意のカクタスの任意の細分はカクタスである。このグラフの族は、たった一つの禁断マイナーで特徴付けられ、完全グラフK4から1辺のみを除去した4頂点ダイヤモンドグラフがカクタスの禁断グラフである[1]。

三角カクタス 編集

 
フレンドシップグラフの例。フレンドシップグラフは常に三角カクタスである。

三角カクタスグラフは、カクタスグラフの特殊な例であり、全ての閉路が3つの辺からなるグラフである。例えば、1つの共通頂点で連結された3つの辺からなる閉路C3からなるフレンドシップグラフは、三角カクタスグラフである。

マトロイド・パリティ問題のアルゴリズムを用いることで、任意のグラフから、そのグラフに含まれる最大の三角カクタスを多項式時間見つける事が可能である。三角カクタスは平面グラフである。そのため、グラフの平面化の重要な部分問題として、最大の三角カクタスは最大の平面グラフの部分グラフの近似として用いられる。この近似アルゴリズムの近似度は4/9であり、最大の平面部分グラフを見つける問題の最良の近似である[2]。

最大の三角カクタスを見つけるアルゴリズムは最大のカクタスに含まれるC3の数についてのロヴァースとプラマーの定理を組み合わせたアルゴリズムである[3]。


ローザの予想 編集

三角カクタスに関連する重要な予想に、アレクサンダー・ローザのローザの予想「三角カクタスは、優美もしくはほぼ優美である」がある[4]。 より正確には、

任意の三角カクタスは、t ≡ 0, 1 mod 4 個のブロックを持つならば優美に、 t ≡ 2, 3 mod 4 個のブロックを持つならばほぼ優美である。

アルゴリズムと応用 編集

任意のグラフに対してはNP困難である施設配置問題などの問題は、カクタスに対しては多項式時間で解くことができる[5][6]。

カクタスは外平面グラフの特殊な例であるため、多数のグラフの組合せ最適化問題を多項式時間で解くことができる[7]。

カクタスを用いた電気回路の解析は有用な特徴を持つ。オペアンプをカクタスを用いて解析する応用がなされた[8][9][10]。

カクタスは、異なるゲノム間またはゲノムの部分間の関係の表現方法として、比較ゲノミクスの分野で用いられている[11]。

もしカクタスの各頂点が高々2つのブロックにしか属さない場合、そのグラフをクリスマスカクタスと呼ぶ。多面体グラフ（polyhedral graph）はその頂点全てを用いるクリスマスカクタスを部分グラフとして持つ。これは、多面体グラフがユークリッド平面にgreedy embeddingを持ち、任意の頂点間でのルーティングが、greedy forwardingによって成功するというLeighton & Moitra (2010)の証明において重要な役割を果たした[12]。

トポロジカルグラフ理論では、cellar embeddingが「平面」であるグラフは、各頂点が高々1つの閉路にしか含まれないカクタスの部分族である。これらのグラフ族は、ダイヤモンドグラフと5頂点フレンドシップグラフという2つの禁断マイナーを持つ[13]。

歴史 編集

カクタスは、伏見康治の功績を讃え、フランク・ハラリーとジョージ・ウーレンベックにHusimi trees（伏見木）と名付けられた[14][15]。そのハラリーとウーレンベックの論文では、全ての閉路が3辺からなるもののみ「cactus」と呼んでいたが、現在は辺の数にかかわらず「カクタス」と呼ばれている。

その一方で、伏見木と言う名前は現在「全てのブロックが完全グラフであるグラフ」を指すようになった。しかし、これは伏見の功績とはほとんど関係がないため現在はブロックグラフと呼ばれており、このような曖昧さを回避するために、伏見木が現在のカクタスを指すことは少なくなった[16]。

References 編集

  1. ^ El-Mallah, Ehab; Colbourn, Charles J. (1988), “The complexity of some edge deletion problems”, IEEE Transactions on Circuits and Systems 35 (3): 354–362, doi:10.1109/31.1748 
  2. ^ Călinescu, Gruia; Fernandes, Cristina G; Finkler, Ulrich; Karloff, Howard (2002), “A Better Approximation Algorithm for Finding Planar Subgraphs”, Journal of Algorithms, 2 27: 269– 302, doi:10.1006/jagm.1997.0920 
  3. ^ Lovász, L.; Plummer, M.D. (2009), Matching Theory, AMS Chelsea Publishing Series, ISBN 9780821847596 
  4. ^ Rosa, A. (1988), “Cyclic Steiner Triple Systems and Labelings of Triangular Cacti”, Scientia 1: 87--95 
  5. ^ Ben-Moshe, Boaz; Bhattacharya, Binay; Shi, Qiaosheng (2005), “Efficient algorithms for the weighted 2-center problem in a cactus graph”, Algorithms and Computation, 16th Int. Symp., ISAAC 2005, Lecture Notes in Computer Science, 3827, Springer-Verlag, pp. 693–703, doi:10.1007/11602613_70 
  6. ^ Zmazek, Blaz; Zerovnik, Janez (2005), “Estimating the traffic on weighted cactus networks in linear time”, Ninth International Conference on Information Visualisation (IV'05), pp. 536–541, doi:10.1109/IV.2005.48, ISBN 0-7695-2397-8 
  7. ^ Korneyenko, N. M. (1994), “Combinatorial algorithms on a class of graphs”, Discrete Applied Mathematics 54 (2–3): 215–217, doi:10.1016/0166-218X(94)90022-1. 
  8. ^ Nishi, Tetsuo; Chua, Leon O. (1986), “Topological proof of the Nielsen-Willson theorem”, IEEE Transactions on Circuits and Systems 33 (4): 398–405, doi:10.1109/TCS.1986.1085935 
  9. ^ Nishi, Tetsuo; Chua, Leon O. (1986), “Uniqueness of solution for nonlinear resistive circuits containing CCCS’s or VCVS’s whose controlling coefficients are finite”, IEEE Transactions on Circuits and Systems 33 (4): 381–397, doi:10.1109/TCS.1986.1085934 
  10. ^ Nishi, Tetsuo (1991), “On the number of solutions of a class of nonlinear resistive circuit”, Proceedings of the IEEE International Symposium on Circuits and Systems, Singapore, pp. 766–769 
  11. ^ Paten, Benedict; Diekhans, Mark; Earl, Dent; St. John, John; Ma, Jian; Suh, Bernard; Haussler, David (2010), “Cactus Graphs for Genome Comparisons”, Research in Computational Molecular Biology, Lecture Notes in Computer Science, 6044, pp. 410–425, doi:10.1007/978-3-642-12683-3_27, ISBN 978-3-642-12682-6 
  12. ^ Leighton, Tom; Moitra, Ankur (2010), “Some Results on Greedy Embeddings in Metric Spaces”, Discrete & Computational Geometry 44 (3): 686–705, doi:10.1007/s00454-009-9227-6, http://people.csail.mit.edu/moitra/docs/dcg-greedy.pdf 
  13. ^ Nordhaus, E. A.; Ringeisen, R. D.; Stewart, B. M.; White, A. T. (1972), “A Kuratowski-type theorem for the maximum genus of a graph”, Journal of Combinatorial Theory, Series B 12: 260–267, doi:10.1016/0095-8956(72)90040-8, MR0299523 
  14. ^ Harary, Frank; Uhlenbeck, George E. (1953), “On the number of Husimi trees, I”, Proceedings of the National Academy of Sciences 39 (4): 315–322, doi:10.1073/pnas.39.4.315, MR0053893, PMC 1063779, PMID 16589268, http://www.pubmedcentral.nih.gov/articlerender.fcgi?tool=pmcentrez&artid=1063779 
  15. ^ Husimi, Kodi (1950), “Note on Mayers' theory of cluster integrals”, Journal of Chemical Physics 18 (5): 682–684, doi:10.1063/1.1747725, MR0038903 
  16. ^ See, e.g., MR0659742, 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.

外部リンク 編集

「https://ja.wikipedia.org/w/index.php?title=カクタスグラフ&oldid=70916137」から取得