next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
GraphicalModels :: trekSeparation

trekSeparation -- the trek separation statements of a mixed graph

Synopsis

Description

A trek between vertices i and j in a mixed graph G with directed and bidirected edges is a triple (PL,PR) where PL is a directed path of directed edges with sink i and source k, PR is a directed path of directed edges with sink j and source l, and either k=l or there is a bidirected edge between k and l. Let A,B,CA,CB be subsets of vertices of G.

We say that (CA,CB) trek-separates A from B in G if for every trek (PL,PR) from a vertex in A to a vertex in B, either PL contains a vertex in CA or PR contains a vertex in CB.

The function trekSeparation returns a list of trek separation statements {A,B,CA,CB} where #CA + #CB < min(#A, #B). Each statement is maximal in the ordering where {A1,B1,CA,CB} < {A2,B2,CA,CB} if A1 is a subset of A2 and B1 is a subset of B2. Each statement is also unique up to symmetry, since {B,A,CB,CA} is a trek separation statement if and only if {A,B,CA,CB}.

i1 : G = mixedGraph(digraph {{b,{c,d}},{c,{d}}},bigraph {{a,d}})

o1 = MixedGraph{Bigraph => Bigraph{a => {d}}   }
                                   d => {a}
                Digraph => Digraph{b => {c, d}}
                                   c => {d}
                                   d => {}
                Graph => Graph{}

o1 : MixedGraph
i2 : S = trekSeparation G

o2 = {{{a}, {b, c}, {}, {}}, {{a, b}, {b, c}, {}, {b}}, {{b, c}, {a, b}, {}, {b}}, {{b, c}, {a, c}, {}, {c}}, {{b, c}, {d, a},
     ----------------------------------------------------------------------------------------------------------------------------
     {}, {d}}}

o2 : List

Caveat

trekSeparation G is only implemented for mixedGraphs with directed and bidirected edges.

See also

Ways to use trekSeparation :