gRbase (version 1.3.9)

minimalTriang: Minimal triangulation of an undirected graph

Description

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.

Usage

minimalTriang(uG, TuG = triangulate(uG, method = "mcwh"), details = 0)
minimalTriangMAT(uGmat, TuGmat = triangulateMAT(uGmat, method = "mcwh"), details = 0)

Arguments

uG

The undirected graph which is to be triangulated; a graphNEL object

TuG

Any triangulation of uG; a graphNEL object

uGmat

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

TuGmat

Any triangulation of uG; a symmetric adjacency matrix

details

The amount of details to be printed.

Value

• minimalTriang() returns a graphNEL object while minimalTriangMAT() returns an adjacency matrix.

Details

For a given triangulation TuG it may be so that some of the fill-ins are superflous in the sense that they can be removed from TuG without breaking the property that TuG 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

Examples

## A graphNEL object
g1 <- ug(~a:b+b:c+c:d+d:e+e:f+a:f+b:e)
x <- minimalTriang(g1)

## g2 is a triangulation of g1 but it is not minimal
g2 <- ug(~a:b:e:f+b:c:d:e)
x<-minimalTriang(g1, TuG=g2)

## An adjacency matrix
g1m <- ugMAT(~a:b+b:c+c:d+d:e+e:f+a:f+b:e)
x<-minimalTriangMAT(g1m)