| 翻訳と辞書 |
Clique-sum
In graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs ''G'' and ''H'' each contain cliques of equal size, the clique-sum of ''G'' and ''H'' is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then possibly deleting some of the clique edges. A ''k''-clique-sum is a clique-sum in which both cliques have at most ''k'' vertices. One may also form clique-sums and ''k''-clique-sums of more than two graphs, by repeated application of the two-graph clique-sum operation.
==Related concepts==
Clique-sums have a close connection with treewidth: If two graphs have treewidth at most ''k'', so does their ''k''-clique-sum. Every tree is the 1-clique-sum of its edges. Every series-parallel graph, or more generally every graph with treewidth at most two, may be formed as a 2-clique-sum of triangles. The same type of result extends to larger values of ''k'': every graph with treewidth at most ''k'' may be formed as a clique-sum of graphs with at most ''k'' + 1 vertices; this is necessarily a ''k''-clique-sum.〔.〕
There is also a close connection between clique-sums and graph connectivity: if a graph is not (''k'' + 1)-vertex-connected (so that there exists a set of ''k'' vertices the removal of which disconnects the graph) then it may be represented as a ''k''-clique-sum of smaller graphs. For instance, the SPQR tree of a biconnected graph is a representation of the graph as a 2-clique-sum of its triconnected components.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Clique-sum」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|