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

trekSeparation -- trek separation statements of a mixed graph



A trek between vertices $i$ and $j$ in a mixed graph $G$ with directed and bidirected edges is a triple $(P_L,P_R)$ where $P_L$ is a directed path of directed edges with sink $i$ and source $k$, $P_R$ 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 $(P_L,P_R)$ from a vertex in $A$ to a vertex in $B$, either $P_L$ contains a vertex in $CA$ or $P_R$ 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


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

See also

Ways to use trekSeparation :

For the programmer

The object trekSeparation is a method function.