| 词条 | K-tree |
| 释义 |
In graph theory, a k-tree is an undirected graph formed by starting with a (k + 1)-vertex complete graph and then repeatedly adding vertices in such a way that each added vertex v has exactly k neighbors U such that, together, the k + 1 vertices formed by v and U form a clique.[1][2] CharacterizationsThe k-trees are exactly the maximal graphs with a given treewidth, graphs to which no more edges can be added without increasing their treewidth.[2] They are also exactly the chordal graphs all of whose maximal cliques are the same size k + 1 and all of whose minimal clique separators are also all the same size k.[1]Related graph classes1-trees are the same as unrooted trees. 2-trees are maximal series-parallel graphs,[2] and include also the maximal outerplanar graphs. Planar 3-trees are also known as Apollonian networks.[3] The graphs that have treewidth at most k are exactly the subgraphs of k-trees, and for this reason they are called partial k-trees.[4] The graphs formed by the edges and vertices of k-dimensional stacked polytopes, polytopes formed by starting from a simplex and then repeatedly gluing simplices onto the faces of the polytope, are k-trees when k ≥ 3.[5] This gluing process mimics the construction of k-trees by adding vertices to a clique.[6] A k-tree is the graph of a stacked polytope if and only if no three (k + 1)-vertex cliques have k vertices in common.[7] References1. ^1 {{citation | last = Patil | first = H. P. | mr = 966069 | issue = 2-4 | journal = Journal of Combinatorics, Information and System Sciences | pages = 57–64 | title = On the structure of k-trees | volume = 11 | year = 1986}}. 2. ^{{citation|page=177|title=The Steiner Tree Problem|volume=53|series=Annals of Discrete Mathematics (North-Holland Mathematics Studies)|first1=Frank|last1=Hwang|first2=Dana|last2=Richards|first3=Pawel|last3=Winter|publisher=Elsevier|year=1992|isbn=978-0-444-89098-6}}. 3. ^Distances in random Apollonian network structures, talk slides by Olivier Bodini, Alexis Darrasse, and Michèle Soria from a talk at FPSAC 2008, accessed 2011-03-06. 4. ^1 2 {{citation|page=390|contribution=Structural Properties of Sparse Graphs|first1=Jaroslav|last1=Nešetřil|author1-link=Jaroslav Nešetřil|first2=Patrice|last2=Ossona de Mendez|author2-link= Patrice Ossona de Mendez |title=Building Bridges: between Mathematics and Computer Science|volume=19|series=Bolyai Society Mathematical Studies|editor-first1=Martin|editor-last1=Grötschel|editor1-link=Martin Grötschel|editor-first2=Gyula O. H.|editor-last2=Katona|editor2-link=Gyula O. H. Katona|publisher=Springer-Verlag|year=2008|isbn=978-3-540-85218-6|contribution-url=http://kam.mff.cuni.cz/~kamserie/serie/clanky/2008/s863.pdf}}. 5. ^{{citation | last1 = Koch | first1 = Etan | last2 = Perles | first2 = Micha A. | author2-link = Micha Perles | contribution = Covering efficiency of trees and k-trees | mr = 0457265 | pages = 391–420. Congressus Numerantium, No. XVII | publisher = Utilitas Math., Winnipeg, Man. | title = Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976) | year = 1976}}. See in particular p. 420. 6. ^{{cite arXiv|title=The Complexity of Finding Small Triangulations of Convex 3-Polytopes|first1=Alexander|last1=Below|first2=Jesús A.|last2=De Loera|author2-link=Jesús A. De Loera|first3=Jürgen|last3=Richter-Gebert|eprint=math/0012177 }}. 7. ^{{cite journal|last=Kleinschmidt|first=Peter|title=Eine graphentheoretische Kennzeichnung der Stapelpolytope|journal=Archiv der Mathematik|date=1 December 1976|volume=27|issue=1|pages=663–667|doi=10.1007/BF01224736}} 4 : Graph minor theory|Trees (graph theory)|Perfect graphs|Graph families |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。