Solutions 211{1,2,3,4,5,6,7,8}. See Figure S.l.(b) Each row represents a fundamental cocycle (cut) in the graph. In the tree,
we term one node as root (node i), and we can associate an edge of the tree
with every node like 1 -> b, 2 -¥ a, 3 -» c, 4 -4 d, • • • , 8 ->• h as if we
hanged the tree to the wall by its root. Then, if the associated edge (say edge
6) in the tree for the node (say /) in the identity part of Zi is removed, we
partition the nodes into two sets as V\ = {a,b,c,d,e,f} and V 2 = {g,h,i}.
The nonzero entries in Zf correspond to edges 10,12,13, defining the set of
edges connecting nodes in different parts of this partition or the cut. The set
of such edges are termed as fundamental cocycle. See Figure S.2.Fig. S.2. The cocycle denned by cutting edge 6 —>• / in Problem2.1(c) Each column represents a fundamental cycle. If we add the edge identified
by 1$ part into T, we will create a cycle defined by the nonzero elements of
yi. See Figure S.3.(d) The first 8 columns of A form a basis for column space 11(A). The columns
of matrix Y is a basis for the null space Af(A). The rows of C constitute a
basis for the row space 1Z(AT). Finally, the row(s) of matrix D is (are) the
basis vectors for the left-null space Af(AT).
Remark S.2.1 If our graph G = (V,E) is bipartite, i.e. V = V1IJV2 9
Vif]V 2 = 0, Vi ± 0 + V 2 and Me = (vx,v 2 ) G E, vi G Vu v 2 G V 2 ,
and we solve m&x.cTx s.t. Ax = b, x > 0 using standard simplex algorithm
over GF(2), we will have exactly what we know as the transportation simplex
method. Furthermore, for general graphs G = (V, E), if we solve maxcTx s.t.