|
In graph theory, the tree-depth of a connected undirected graph ''G'' is a numerical invariant of ''G'', the minimum height of a Trémaux tree for a supergraph of ''G''. This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages.〔; ; , p. 116.〕 Intuitively, where the treewidth graph width parameter measures how far a graph is from being a tree, this parameter measures how far a graph is from being a star. ==Definitions== The tree-depth of a graph ''G'' may be defined as the minimum height of a forest ''F'' with the property that every edge of ''G'' connects a pair of nodes that have an ancestor-descendant relationship to each other in ''F''.〔, Definition 6.1, p. 115.〕 If ''G'' is connected, this forest must be a single tree; it need not be a subgraph of ''G'', but if it is, it is a Trémaux tree for ''G''. The set of ancestor-descendant pairs in ''F'' forms a trivially perfect graph, and the height of ''F'' is the size of the largest clique in this graph. Thus, the tree-depth may alternatively be defined as the size of the largest clique in a trivially perfect supergraph of ''G'', mirroring the definition of treewidth as one less than the size of the largest clique in a chordal supergraph of ''G''.〔.〕 Another definition is the following: where ''V'' is the set of vertices of ''G'' and the are the connected components of ''G''.〔, Lemma 6.1, p. 117.〕 This definition mirrors the definition of cycle rank of directed graphs, which uses strong connectivity and strongly connected components in place of undirected connectivity and connected components. Tree-depth may also be defined using a form of graph coloring. A centered coloring of a graph is a coloring of its vertices with the property that every connected induced subgraph has a color that appears exactly once. Then, the tree-depth is the minimum number of colors in a centered coloring of the given graph. If ''F'' is a forest of height ''d'' with the property that every edge of ''G'' connects an ancestor and a descendant in the tree, then a centered coloring of ''G'' using ''d'' colors may be obtained by coloring each vertex by its distance from the root of its tree in ''F''.〔, Section 6.5, "Centered Colorings", pp. 125–128.〕 Finally, one can define this in terms of a pebble game, or more precisely as a cops and robber game. Consider the following game, played on an undirected graph. There are two players, a robber and a cop. The robber has one pebble he can move along the edges of the given graph. The cop has an unlimited number of pebbles, but she wants to minimize the amount of pebbles she uses. The cop cannot move a pebble after it has been placed on the graph. The game proceeds as follows. The robber places his pebble. The cop then announces where she wants to place a new cop pebble. The robber can then move his pebble along edges, but not through occupied vertices. The game is over when the cop player places a pebble on top of the robber pebble. The tree-depth of the given graph is the minimum number of pebbles needed by the cop to guarantee a win.〔, Theorem 5, , Main Theorem.〕 For a star graph, two pebbles suffice: the strategy is to place a pebble at the center vertex, forcing the robber to one arm, and then to place the remaining pebble on the robber. For a path with vertices, the cop uses a binary search strategy, which guarantees that at most pebbles are needed. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Tree-depth」の詳細全文を読む スポンサード リンク
|