|
In graph theory, the treewidth of an undirected graph is a number associated with the graph. Treewidth may be defined in several equivalent ways: from the size of the largest vertex set in a tree decomposition of the graph, from the size of the largest clique in a chordal completion of the graph, from the maximum order of a haven describing a strategy for a pursuit-evasion game on the graph, or from the maximum order of a bramble, a collection of connected subgraphs that all touch each other. Treewidth is commonly used as a parameter in the parameterized complexity analysis of graph algorithms. The graphs with treewidth at most ''k'' are also called partial ''k''-trees; many other well-studied graph families also have bounded treewidth. The concept of treewidth was originally introduced by under the name of ''dimension''. It was later rediscovered by , based on properties that it shares with a different graph parameter, the Hadwiger number. Later it was again rediscovered by and has since been studied by many other authors.〔 pp.354–355〕 ==Definition== A tree decomposition of a graph ''G'' = (''V'', ''E'') is a tree, ''T'', with nodes ''X''1, ..., ''X''''n'', where each ''X''''i'' is a subset of ''V'', satisfying the following properties〔 section 12.3〕 (the term ''node'' is used to refer to a vertex of ''T'' to avoid confusion with vertices of ''G''): # The union of all sets ''X''''i'' equals ''V''. That is, each graph vertex is contained in at least one tree node. # If ''X''''i'' and ''X''''j'' both contain a vertex ''v'', then all nodes ''X''''k'' of the tree in the (unique) path between ''X''''i'' and ''X''''j'' contain ''v'' as well. Equivalently, the tree nodes containing vertex ''v'' form a connected subtree of ''T''. # For every edge (''v'', ''w'') in the graph, there is a subset ''X''''i'' that contains both ''v'' and ''w''. That is, vertices are adjacent in the graph only when the corresponding subtrees have a node in common. The ''width'' of a tree decomposition is the size of its largest set ''X''''i'' minus one. The treewidth tw(''G'') of a graph ''G'' is the minimum width among all possible tree decompositions of ''G''. In this definition, the size of the largest set is diminished by one in order to make the treewidth of a tree equal to one. Equivalently, the treewidth of ''G'' is one less than the size of the largest clique in the chordal graph containing ''G'' with the smallest clique number. A chordal graph with this clique size may be obtained by adding to ''G'' an edge between every two vertices that both belong to at least one of the sets ''Xi''. Treewidth may also be characterized in terms of havens, functions describing an evasion strategy for a certain pursuit-evasion game defined on a graph. A graph ''G'' has treewidth ''k'' if and only if it has a haven of order but of no higher order, where a haven of order is a function ''β'' that maps each set ''X'' of at most ''k'' vertices in ''G'' into one of the connected components of and that obeys the monotonicity property that whenever A similar characterization can also be made using brambles, families of connected subgraphs that all touch each other (meaning either that they share a vertex or are connected by an edge).〔.〕 The order of a bramble is the smallest hitting set for the family of subgraphs, and the treewidth of a graph is one less than the maximum order of a bramble. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Treewidth」の詳細全文を読む スポンサード リンク
|