|
In graph theory, a branch-decomposition of an undirected graph ''G'' is a hierarchical clustering of the edges of ''G'', represented by an unrooted binary tree ''T'' with the edges of ''G'' as its leaves. Removing any edge from ''T'' partitions the edges of ''G'' into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of ''G'' is the minimum width of any branch-decomposition of ''G''. Branchwidth is closely related to tree-width: for all graphs, both of these numbers are within a constant factor of each other, and both quantities may be characterized by forbidden minors. And as with treewidth, many graph optimization problems may be solved efficiently for graphs of small branchwidth. However, unlike treewidth, the branchwidth of planar graphs may be computed exactly, in polynomial time. Branch-decompositions and branchwidth may also be generalized from graphs to matroids. ==Definitions== An unrooted binary tree is a connected undirected graph with no cycles in which each non-leaf node has exactly three neighbors. A branch-decomposition may be represented by an unrooted binary tree ''T'', together with a bijection between the leaves of ''T'' and the edges of the given graph ''G'' = (''V'',''E''). If ''e'' is any edge of the tree ''T'', then removing ''e'' from ''T'' partitions it into two subtrees ''T''1 and ''T''2. This partition of ''T'' into subtrees induces a partition of the edges associated with the leaves of ''T'' into two subgraphs ''G''1 and ''G''2 of ''G''. This partition of ''G'' into two subgraphs is called an e-separation. The width of an e-separation is the number of vertices of ''G'' that are incident both to an edge of ''E''1 and to an edge of ''E''2; that is, it is the number of vertices that are shared by the two subgraphs ''G''1 and ''G''2. The width of the branch-decomposition is the maximum width of any of its e-separations. The branchwidth of ''G'' is the minimum width of a branch-decomposition of ''G''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Branch-decomposition」の詳細全文を読む スポンサード リンク
|