Macaulay2 » Documentation
Packages » GraphicalModels :: trekSeparation
next | previous | forward | backward | up | index | toc

# trekSeparation -- trek separation statements of a mixed graph

- Usage:
    `trekSeparation(G)`
- Inputs:
  - G, an instance of the type MixedGraph, mixed graph with directed and bidirected edges
- Outputs:
  - a list, of lists \{A,B,CA,CB\}, where (CA,CB) trek-separates A from B

## Description

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

## Caveat

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

## See also

- trekIdeal -- trek separation ideal of a mixed graph

## Ways to use trekSeparation:

- `trekSeparation(MixedGraph)`

## For the programmer

The object trekSeparation is a method function.

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/GraphicalModels.m2:2686:0.