Minimal triangulation of an undirected graph

An undirected graph uG is triangulated (or chordal) if it has no cycles of length >= 4 without a chord which is equivalent to that the vertices can be given a perfect ordering. Any undirected graph can be triangulated by adding edges to the graph, so called fill-ins which gives the graph TuG. A triangulation TuG is minimal if no fill-ins can be removed without breaking the property that TuG is triangulated.

minimal_triang(
  object,
  tobject = triangulate(object),
  result = NULL,
  details = 0
)

minimal_triangMAT(amat, tamat = triangulateMAT(amat), details = 0)

Arguments

object

An undirected graph represented either as a graphNEL object, a (dense) matrix, a (sparse) dgCMatrix.

tobject

Any triangulation of object; must be of the same representation.

result

The type (representation) of the result. Possible values are "graphNEL", "matrix", "dgCMatrix". Default is the same as the type of object.

details

The amount of details to be printed.

amat

The undirected graph which is to be triangulated; a symmetric adjacency matrix.

tamat

Any triangulation of object; a symmetric adjacency matrix.

Value

minimal_triang() returns a graphNEL object while minimal_triangMAT() returns an adjacency matrix.

Details

For a given triangulation tobject it may be so that some of the fill-ins are superflous in the sense that they can be removed from tobject without breaking the property that tobject is triangulated. The graph obtained by doing so is a minimal triangulation.

Notice: A related concept is the minimum
triangulation, which is the the graph with the smallest number
of fill-ins. The minimum triangulation is unique. Finding the
minimum triangulation is NP-hard.

References

Kristian G. Olesen and Anders L. Madsen (2002): Maximal Prime Subgraph Decomposition of Bayesian Networks. IEEE TRANSACTIONS ON SYSTEMS, MAN AND CYBERNETICS, PART B: CYBERNETICS, VOL. 32, NO. 1, FEBRUARY 2002

See also

mpd, rip, triangulate

Author

Clive Bowsher C.Bowsher@statslab.cam.ac.uk with modifications by Søren Højsgaard, sorenh@math.aau.dk

Examples

## An igraph object
g1 <- ug(~a:b + b:c + c:d + d:e + e:f + a:f + b:e, result="igraph")
x <- minimal_triang(g1)

tt <- ug(~a:b:e:f + b:e:c:d, result="igraph")
x <- minimal_triang(g1, tobject=tt)

## g2 is a triangulation of g1 but it is not minimal
g2 <- ug(~a:b:e:f + b:c:d:e, result="igraph")
x <- minimal_triang(g1, tobject=g2)

## An adjacency matrix
g1m <- ug(~a:b + b:c + c:d + d:e + e:f + a:f + b:e, result="matrix")
x <- minimal_triangMAT(g1m)