カクタスグラフとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > カクタスグラフの意味・解説 

カクタスグラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/12/10 18:35 UTC 版)

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


  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, MR 0299523 
  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, MR 0053893, 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, MR 0038903 
  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.


「カクタスグラフ」の続きの解説一覧



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「カクタスグラフ」の関連用語

カクタスグラフのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



カクタスグラフのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのカクタスグラフ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2024 GRAS Group, Inc.RSS