User:Vernon1016

In graph theory, a decomposable graph is a type of graph which is used to model various mathematical concepts. These include modeling [[probability|probabilities in Bayesian statistics, and forming junction trees. Junction trees are a specialized type of a mathematical structure known as a tree. These junction trees can be used to solve problems such as graph coloring and constraint satisfaction.^[1]

Definitions[edit]

We say that $A$ , $B$ , and $S$ , subsets of a graph $G$ , form a proper decomposition of $G$ , written as the ordered 3-tuple $(A,B,S)$ if the following statements all hold:

$A$ , $B$ , and $S$ are subsets of $G$ such that $V=A$ ∪ $B$ ∪ $S$ , where $V$ is the vertex set of $G$ .
The elements of $A$ , $B$ , and $S$ are distinct and share no common elements.
The set $S$ is a clique , which is a complete subset of vertices in $G$ .
$S$ is a vertex separator in $G$ .^[2]

A graph $G$ is said to be decomposable if either of the following holds:

$G$ is complete.
$G$ possesses a proper decomposition $(A,B,S)$ such that the induced subgraphs $G$ _{( $A$ ∪ $S$ )} and $G$ _{( $B$ ∪ $S$ )} are decomposable.^[3]

Properties and Facts[edit]

All decomposable graphs are triangulated, or chordal. The converse is also true. This means that every cycle in a graph with length of at least 4 contains a chord, which is an edge connecting non-adjacent vertices.^[2]
The removal of an edge (x,y), from a graph G, results in a decomposable graph if and only if the two vertices x and y are in exactly one clique.
The addition of an edge (x,y), into a graph G, results in a decomposable graph if and only if x and y are unconnected, and contained in adjacent cliques in some junction tree of the graph G.^[4]