| 翻訳と辞書 |
Boxicity
In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969.
The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis-parallel boxes. That is, there must exist a one-to-one correspondence between the vertices of the graph and a set of boxes, such that two boxes intersect if and only if there is an edge connecting the corresponding vertices.
==Examples==
The figure shows a graph with six vertices, and a representation of this graph as an intersection graph of rectangles (two-dimensional boxes). This graph cannot be represented as an intersection graph of boxes in any lower dimension, so its boxicity is two.
showed that the graph with 2''n'' vertices formed by removing a perfect matching from a complete graph on 2''n'' vertices has boxicity exactly ''n'': each pair of disconnected vertices must be represented by boxes that are separated in a different dimension than each other pair. A box representation of this graph with dimension exactly ''n'' can be found by thickening each of the 2''n'' facets of an ''n''-dimensional hypercube into a box. Because of these results, this graph has been called the ''Roberts graph'',〔E.g., see and .〕 although it is better known as the cocktail party graph and it can also be understood as the Turán graph ''T''(2''n'',''n'').
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Boxicity」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|