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 => set {d}} } d => set {a} Digraph => Digraph{b => set {c, d}} c => set {d} d => set {} Graph => Graph{} o1 : MixedGraph |
i2 : S = trekSeparation G o2 = {{{a}, {b, c}, {}, {}}, {{b, c}, {a, b}, {}, {b}}, {{b, a}, {b, c}, {}, ------------------------------------------------------------------------ {b}}, {{b, c}, {a, c}, {}, {c}}, {{b, c}, {a, d}, {}, {d}}} o2 : List |