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.
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 : R = gaussianRing G o2 = R o2 : PolynomialRing |
i3 : S = trekSeparation G
o3 = {{{a}, {b, c}, {}, {}}, {{a, b}, {b, c}, {}, {b}}, {{b, c}, {a, b}, {},
------------------------------------------------------------------------
{b}}, {{b, c}, {a, c}, {}, {c}}, {{b, c}, {d, a}, {}, {d}}}
o3 : List
|
i4 : trekIdeal(R,G,S)
o4 = ideal (s , s , - s s + s s , - s s + s s , -
a,b a,c a,c b,b a,b b,c a,c b,b a,b b,c
------------------------------------------------------------------------
s s + s s , s s - s s )
a,c b,c a,b c,c a,c b,d a,b c,d
o4 : Ideal of R
|