# graph-min-triangulate: Minimal triangulation of an undirected graph In gRbase: A Package for Graphical Modelling in R

 graph-min-triangulate R Documentation

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

``````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.

### 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.
```

### Value

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

### Author(s)

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

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

`mpd`, `rip`, `triangulate`

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