Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Tree-depth
Résumé
In graph theory, the tree-depth of a connected undirected graph is a numerical invariant of , the minimum height of a Trémaux tree for a supergraph of . 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. Intuitively, where the treewidth of a graph measures how far it is from being a tree, this parameter measures how far a graph is from being a star.
The tree-depth of a graph may be defined as the minimum height of a forest with the property that every edge of connects a pair of nodes that have an ancestor-descendant relationship to each other in . If is connected, this forest must be a single tree; it need not be a subgraph of , but if it is, it is a Trémaux tree for .
The set of ancestor-descendant pairs in forms a trivially perfect graph, and the height of 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 , mirroring the definition of treewidth as one less than the size of the largest clique in a chordal supergraph of .
Another definition is the following:
where is the set of vertices of and the are the connected components of . 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 is a forest of height with the property that every edge of connects an ancestor and a descendant in , then a centered coloring of using colors may be obtained by coloring each vertex by its distance from the root of its tree in .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.