Chordal graph

Chordal Graph

A chordal graph, also known as a triangulated graph or a perfect elimination graph, is a type of graph that has a special property related to its cycles and cliques. In a chordal graph, every cycle of length four or more has a chord, which is an edge that connects two non-adjacent vertices of the cycle. Chordal graphs have various applications in computer science, including optimization problems, network analysis, and bioinformatics.

Definition

A graph G = (V, E) is said to be chordal if every cycle of length four or more in G has a chord. In other words, for any cycle C in G with four or more vertices, there exists an edge between two non-adjacent vertices of C. This property distinguishes chordal graphs from other types of graphs, such as cycles or trees.

Properties

Chordal graphs have several interesting properties that make them useful in various applications. Some of these properties include:

1. Perfect elimination order: A chordal graph can be represented by a perfect elimination order, which is an ordering of the vertices such that, for each vertex v, the neighbors of v that appear after v in the order form a clique. This property allows for efficient algorithms to solve optimization problems on chordal graphs.

2. Cliques and separators: Chordal graphs have a special relationship between cliques and separators. A clique in a chordal graph is a subset of vertices that are all pairwise adjacent. A separator is a subset of vertices that, when removed from the graph, disconnects it into two or more components. In a chordal graph, every minimal separator is a clique.

3. Tree representation: Every chordal graph can be represented by a tree, known as a clique tree or a junction tree. The vertices of the tree correspond to the maximal cliques of the chordal graph, and the edges represent the intersections between these cliques. This tree representation allows for efficient inference algorithms in probabilistic graphical models.

Applications

Chordal graphs have various applications in computer science and related fields. Some of these applications include:

1. Optimization problems: Chordal graphs can be used to model and solve various optimization problems, such as the maximum clique problem, the minimum vertex cover problem, and the maximum independent set problem. The perfect elimination order property of chordal graphs allows for efficient algorithms to solve these problems.

2. Network analysis: Chordal graphs are used in network analysis to study the structure and properties of complex networks, such as social networks, biological networks, and communication networks. The tree representation of chordal graphs provides insights into the connectivity and clustering patterns of these networks.

3. Bioinformatics: Chordal graphs are employed in bioinformatics to analyze biological networks, such as protein-protein interaction networks and gene regulatory networks. The properties of chordal graphs help in identifying functional modules, detecting protein complexes, and predicting gene functions.

See Also

• Graph Theory
• Clique (graph theory)
• Tree (graph theory)

References

1. Golumbic, Martin Charles. "Algorithmic graph theory and perfect graphs." Academic Press, 2004. 2. Tripathi, Anurag, et al. "Chordal graphs: structure and algorithms." Foundations and Trends in Theoretical Computer Science 9.3-4 (2014): 185-356. Template:Graph Theory