graph-min-triangulate | R Documentation |
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)
object |
An undirected graph represented either as a |
tobject |
Any triangulation of |
result |
The type (representation) of the result. Possible values are
|
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 |
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 an igraph object while
minimal_triangMAT()
returns an adjacency matrix.
Clive Bowsher C.Bowsher@statslab.cam.ac.uk with modifications by Søren Højsgaard, sorenh@math.aau.dk
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
## 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)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.