graph-min-triangulate: Minimal triangulation of an undirected graph

graph-min-triangulateR Documentation

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.


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

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



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


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


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


The amount of details to be printed.


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


Any triangulation of object; a symmetric adjacency matrix.


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.


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


Clive Bowsher with modifications by Søren Højsgaard,


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


## 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)

gRbase documentation built on Sept. 22, 2023, 5:12 p.m.