カクタスグラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/12/10 18:35 UTC 版)
カクタスグラフ（もしくは単にカクタス、カクタス木）は任意の2つの単純閉路が2つ以上の共通頂点を持たない連結グラフである。別の言い方をすれば、全ての辺が高々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
- ^ 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
- ^ Lovász, L.; Plummer, M.D. (2009), Matching Theory, AMS Chelsea Publishing Series, ISBN 9780821847596
- ^ Rosa, A. (1988), “Cyclic Steiner Triple Systems and Labelings of Triangular Cacti”, Scientia 1: 87--95
- ^ 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
- ^ 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
- ^ 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.
- ^ 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
- ^ 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
- ^ 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
- ^ 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
- ^ 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
- ^ 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, MR 0299523
- ^ 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, MR 0053893, PMC 1063779, PMID 16589268
- ^ Husimi, Kodi (1950), “Note on Mayers' theory of cluster integrals”, Journal of Chemical Physics 18 (5): 682–684, doi:10.1063/1.1747725, MR 0038903
- ^ 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.
[続きの解説]
「カクタスグラフ」の続きの解説一覧
- 1 カクタスグラフとは
- 2 カクタスグラフの概要
- 3 外部リンク
- カクタスグラフのページへのリンク
