|
In graph theory, a ''k''-tree is a chordal graph 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''.〔.〕 The ''k''-trees are exactly the maximal graphs with a given treewidth, graphs to which no more edges can be added without increasing their treewidth. 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.〔.〕 Every ''k''-tree may be formed by starting with a (''k'' + 1)-vertex complete graph and then repeatedly adding vertices in such a way that each added vertex has exactly ''k'' neighbors that form a clique.〔〔 Certain ''k''-trees with ''k'' ≥ 3 are also the graphs formed by the edges and vertices of stacked polytopes, polytopes formed by starting from a simplex and then repeatedly gluing simplices onto the faces of the polytope; this gluing process mimics the construction of ''k''-trees by adding vertices to a clique.〔.〕 Every stacked polytope forms a ''k''-tree in this way, but not every ''k''-tree comes from a stacked polytope: 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. 1-trees are the same as unrooted trees. 2-trees are maximal series-parallel graphs,〔.〕 and include also the maximal outerplanar graphs. Planar 3-trees are also known as Apollonian networks.〔(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.〕 In higher-dimensional geometry, the stacked polytopes have graphs that are ''k''-trees.〔. See in particular p. 420.〕 ==References== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「K-tree」の詳細全文を読む スポンサード リンク
|