Triangulated graph
In graph theory , a graph is called triangulated or chordal if and only if it satisfies one of the following equivalent conditions:
- Every induced circle is a triangle. A circle is induced exactly when there are no further edges in the original graph between its nodes .
- Every minimal ab separator to two corners a and b is a clique.
- Every induced subgraph contains a simplicial vertex (Rose, 1970), i.e. a vertex whose neighbors form a clique .
- G is the intersection graph of a set of subtrees of a tree (Gavril, 1974).
properties
In triangulated graphs, the calculation of the parameters clique number , chromatic number , independence number and clique coverage number - for any graphs NP-difficult problems - can be carried out in linear time. The characterization via simplicial corners enables a chordality test in linear time. A node order of the graph is called the perfect elimination order , so that for every graph with the node set restricted (by eliminating the nodes to ) the following applies: is simplicial in . Each (in relation to the selected order) “smallest” node in forms a clique with its neighbors .
Triangulated graphs are not to be confused with the (maximally planar) triangle graphs . Triangle graphs are not all triangulated, as can be seen from a graph that consists of a circle of length , inside and outside of which there is another node that is adjacent to all nodes of the circle. Conversely, triangulated graphs do not necessarily have to be triangle graphs, as a non-planar complete graph shows.
However, triangular graphs are still referred to as triangulated graphs in the specialist literature.
literature
- Jorge L. Ramírez Alfonsín, Bruce A. Reed: Perfect Graphs . Wiley 2001, ISBN 978-0-471-48970-2 , p. 14 ( limited online version in Google Book Search - USA )
- Sven Oliver Krumke and Hartmut Noltemeier: Graph theoretical concepts and algorithms . 2nd Edition. Vieweg-Teubner 2009. ISBN 978-3-8348-0629-1 . P. 61
Web links
- Eric W. Weisstein : Chordal Graph . In: MathWorld (English).
Individual evidence
- ↑ i11www.iti.kit.edu (PDF)