Citation
Generalization of network flow theory to matroids

Material Information

Title:
Generalization of network flow theory to matroids
Creator:
Haskins, Irene Mae
Publication Date:
Language:
English
Physical Description:
75 leaves : illustrations ; 28 cm

Subjects

Subjects / Keywords:
Matroids ( lcsh )
Network analysis (Planning) ( lcsh )
Matroids ( fast )
Network analysis (Planning) ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 74-75).
General Note:
Submitted in partial fulfillment of the requirements for the degree, Master of Science, Department of Applied Mathematics ; Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Irene Mae Haskins.

Record Information

Source Institution:
University of Colorado Denver
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
19783322 ( OCLC )
ocm19783322
Classification:
LD1190.L622 1988m .H385 ( lcc )

Full Text
GENERALIZATION OF NETWORK FLOW
THEORY TO MATROIDS
by
IRENE MAE HASKINS
B.S., EASTERN NEW MEXICO UNIVERSITY, 1977
M.A., EASTERN NEW MEXICO UNIVERSITY, 1978
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado in partial fulfillment
of the requirements for the degree of
Master of Science
Department of Applied Mathematics
1988


This thesis for the Master of Science degree by
Irene Mae Haskins
has been approved for the
Department of
Applied Mathematics
by
DATE

S \CV(?7-





Haskins, Irene Mae (M.S., Applied Mathematics)
Generalization Of Network Flow Theory to Matroids
Thesis directed by Assistant Professor Jennifer Ryan
A matroid is a combinatorial abstraction of
graphs and vector spaces. The ideas of network flow
theory can be generalized to the study of matroids. It
is possible to develop the concept of a matroid flow
for arbitrary matroids, and to define an algorithm that
is applicable to specific types of matroids. This
paper begins with an overview of graph theory, network
flow theory, and matroid theory. This overview is
intended to provide the reader sufficient background in
these three areas before developing the idea of a
matroid flow.
The form and content of this abstract are approved. I
recommend it's publication.
Signed


This thesis is dedicated to
my husband
David W. Haskins
for his support
and in
memory of my father
Jack G. Bennett


ACKNOWLEDGEMENTS
This thesis was made possible by the support of
many people. I would especially like to formally thank
the people listed below.
Dr. Jennifer Ryan- thesis advisor. It was with
Jennifer's encouragement that I first decided to write
a thesis. She not only provided assistance and
support, but also spent a great many hours of her own
time in reviewing the thesis and helping me develop
proofs. I deeply appreciate her help and patience and
feel it was an honor to work with her.
Dr. Richard Lundgren and Dr. Harvey Greenberg-
thesis committee members. I would like to thank both
Rich and Harvey for the time they spent in reviewing
the thesis. I appreciate their time and the input they
provided.
David W. Haskins- husband. I want to thank my
husband for his support and encouragement. He was a
tremendous help by taking over my share of household
responsibilities to provide the time needed to pursue
the thesis. I thank him also for the time he spent in
proof-reading the thesis, illustrating the graphs and
most of all his faith in me.


CONTENTS
CHAPTER
I. GRAPH THEORY.............................. 1
II. NETWORK FLOWS............................. 11
III. MATROIDS.................................... 18
IV. MATROID FLOWS............................. 4 3
74
BIBLIOGRAPHY


CHAPTER I
GRAPH THEORY
The origin of the study of graph theory is
generally credited to Euler (EU36), who in 1736 used
graph theory to address the famous Konisberg Bridge
Problem. Kirchoff (KR47) in 1847, applied graph theory
to analyze electrical networks and Cayley (CY57) in
1874 used graph theory in the study of organic
chemistry. Today graph theory is widely used in many
fields including biology, genetics, and communications.
In this section, several definitions and
examples are presented to provide the reader with a
basic understanding of the graph theoretic tools used
later in this paper.
We begin by defining exactly what is meant by
the term "graph". A GRAPH is a pair (V,E), where V is
a set of elements, and E is a set of pairs of elements
of V. The elements of V are referred to as vertices
but may also be called nodes. The elements of E are
referred to as edges. We denote the vertex set of a
graph G, by V(G), and the edge set of a graph E(G).
If the pairs of elements in the set E are
ordered, then the graph is called a DIGRAPH. The edge


2
set and vertex set of a digraph are denoted by E(D) and
V(D) respectively. Edges in a digraph may also be
i
referred to as "arcs".
For notation purposes, we denote an edge of a
graph by a pair of vertices (x,y), and denote a
directed edge of a digraph by an ordered pair of
vertices (z,w).
Later we will denote an edge by a single
character, for example, e = (x,y), but for now it is
important to think of edges as a "relation" connecting
two vertices. The following examples will illustrate
the concepts covered thus far.
Example 1.1
Let G be a graph with vertices = (1,2,3,4) and edges =
{(1,2), (2,4), (3,4), (1,3)}. The graph G can be
represented by the following diagram.
1 2
3
Note that the diagram completely describes the graph.
Example 1.2
Let D be the digraph with vertices = (1,2,3,4} and
edges ={(1,2),(2,3) (3,1),(3,4),(4,1)}. The digraph D


3
can be represented by the following diagram.
Again, the diagram completely describes the graph.
Let e = (u,v) be an edge in a graph, and u and
v be ENDPOINTS of e. Suppose that e^ = (v,u) is a
directed edge from vertex v to vertex u. We call u the
HEAD of the edge, denoted h(e^), and v is the TAIL of
the edge denoted t(e^).
Example 1.3
v y u
t(e) h(e)
In this example, the head of the edge is the vertex u
and the tail of the edge is vertex v.
Suppose now that we wish to get from a vertex x
in a (di)graph to a vertex z in that same
(di)graph. The sequence of vertices and edges that are
passed through in traveling from x to z is called a-
(DI)PATH. A (di)path may also be referred to as a
CHAIN. We denote a (di)path as: v^e1,v2,e2,...,v^_
1,ei-l'vi' where ek = (vk'vk+l^ A diPath is
considered to be SIMPLE if all v^'s are distinct, that
is, any vertex is used just once in the (di)path. A
path is CLOSED if v.^ = v^. We can now define a circuit
as being a simple, closed path. Circuits are also


4
called CYCLES.
Example 1.4
Let D2 be a digraph with vertex set V(D2) =
*V1,V2,V3,V4,V5} and edgS SSt E(D2) = {ei,e2'e3,S4,e5}
where the edges of D2 are defined as follows: e1 =
(V1'V2>' e2 = ' S3 =' e4 = ' e5
(v4,v5),and e6 (v5,v1).
The sequence e.^, v2, e2, v3, e^, v is a dipath
from v1 to v4 This is a simple path as no vertex is
used more than once. An example of a circuit is:
Vl'ei,V2,e2,V3'e4'V4'e5,V5'e6'Vl Notice that this is
a simple, closed path because each vertex is passed
through only once, and the path started and ended with
the same vertex.
Two vertices u and v in a graph G are ADJACENT
if there is an edge (u,v) in E(G). A (di)graph is
CONNECTED if there exists a path from vertex v to
vertex u for all u,v G V(G). In the case of digraphs,
edge orientation is disregarded when determining
connectivity.


5
A SUBGRAPH H = (V',E') of a graph G = (V,E) is
a graph with vertices V' E V and edges E' E E. A
GENERATED SUBGRAPH is a subgraph H = (V',E') with E'
being the set of all possible edges e^ E E with the
property that both endpoints of e^ are in V' E V. If H
= (V',E') is a subgraph of G = (V,E), then H is a
SPANNING SUBGRAPH if V = V.
Example 1.5
a bababab
c d c c c d
(a) (b) (c) (d)
Let (a) represent the graph G, then (b) is a subgraph
of G, (C) is a generated subgraph of G, and (d) is a
spanning subgraph of G.
An important class of graphs are "trees". A
TREE is a graph that is both connected and has no
circuits. If a spanning (di)graph is a tree, then we
call the spanning subgraph a SPANNING TREE. A FOREST
is a graph whose connected components are trees.
Example 1.6
Let G be the following graph:


6
:________ [ |
(a) (b) (c)
In this example (a) is a tree, (b) is also a tree, but
it is a.spanning tree of G, and (c) is a forest.
BIPARTITE graphs are a special type of graph.
In order to define this type of graph, we must first
introduce the concept of "coloring" a graph. By
coloring, we refer to the assignment of a color to each
vertex of the graph. We color the vertices of the graph
so that no edge connects any two vertices of the same
color. We define a bipartite graph as a graph that can
be colored using at most two colors. This is
equivalent to partitioning the vertices of a graph into
two sets so that every edge in the graph has it's two
endpoints in different sets.
Example 1.7
Given the above graphs with colorings R = red, B =
blue, Y = yellow, then graphs (A), and (B) are
bipartite graphs, and (C) is not.
A MATCHING is a set M of edges in G, such that


7
every vertex is incident to at most one edge in M.
Example 1.8
Let G be the given bipartite graph:
In this example, the dark edges in (a) represent a
matching, however it is not a maximum cardinality
matching as it is possible to add more edges to the
matching. The dark edges in graph (b) do not form a
matching because there is a vertex that is connected to
two different dark edges. Graph (c) represents a
maximum cardinality matching.
A PLANAR graph has the property that it can be
drawn so that no two edges cross except at a vertex.
To verify that this property holds for a graph may not
always be obvious from first glance. It may be
necessary to redraw the graph preserving vertex-edge
incidence to check if a graph is planar or not.
Consider the following example:


8

Example 1.9
a b a
c d c d
The above graph is planar, as it is possible to redraw
it preserving vertex-edge incidence in such a way that
no edge crosses any other except at a vertex.
Another concept in graph theory we will need to
make use of is that of an INCIDENCE MATRIX. Such a
matrix records the vertex-edge incidences of a graph.
We construct an incidence matrix for a graph as an m x
n matrix, with m rows, one for each vertex; and n
columns, one for each edge. The a^^th entry of an
incidence matrix A is 1 if vertex i is on edge j, and 0
otherwise.
Example 1.10
Let G be the following graph. Let T
a lb
(a)
The corresponding vertex-edge incidence matrix A is
given by:


9
1 2 3 4 5
1110 0
10 0 10
0 10 0 1
0 0 111
We conclude our discussion of graph theory by
introducing graph MINORS. There are three types of
minors: deletion, restriction, and contraction. We
define the graph minors as follows: The RESTRICTION G|T
of the graph G is the subgraph (V,T). The DELETION G\T
is the subgraph (V,E\T) The CONTRACTION G/T of T in G
is the subgraph formed by shrinking the edges of T to a
node.
EXAMPLE 1.11
Let T = {a} and let G be the following graph:
b
3 e 4
Deletion of T:
1 2
b
3 e 4
Restriction to T:
2
1
a


Contraction of T
b


CHAPTER II
NETWORK FLOWS
A "network" is a (di)graph with edges e 6 E,
and vertices v E V such that each edge has one or more
weights assigned to it. The idea of a NETWORK FLOW
PROBLEM, is to pass "flow" (i.e. units of a commodity)
through a network from a source vertex "s", to a sink
vertex "t". Each edge in the network is weighted by a
vector, u = (ue:e E E), where uq represents the
"capacity" of the edge e. If xg represents the amount
of flow on an edge, then 0 < xq £ u&. That is, flow on
any edge of the network must be non-negative and cannot
exceed that capacity of that edge.
The NET FLOW into a vertex v is v(x) =
Z(Xj:v=h(j)) S(Xj:v=t(j)). In the network flow
problem we insist (except for the source and the sink)
that the net flow of a vertex is zero. This is called
the CONSERVATION OF FLOW law and simply states that the
flow going into a vertex equals the flow leaving a
vertex.
We define a flow to be FEASIBLE if the
following two conditions are satisfied:
i) 0 < x^ < u for all e E E.
e e


12
ii) v(x) = 0, for all v E V\{s,t).
Theorem 2.1
If the conservation of flow equations ((ii) above) are
satisfied for a flow x, then s(x) = -t(x).
A proof for Theorem 2.1 may be found in Ford
and Fulkerson (FF62).
The following definitions are necessary to
further discuss network flow problems. An edge is
considered to be a FORWARD-EDGE on a path from s to t,
if the orientation of the edge is from s to t. An edge
is considered to be a BACKWARD EDGE, if the orientation
of the edge is not in the direction of a path from s to
t. A path P is said to be a FLOW AUGMENTING PATH if
for each forward edge of P, xq < ue, and for each
backward edge of P, xq > 0. The flow can be increased
on all forward edges and decreased on all backward
edges of a path P without violating the conservation of
flow equations. To determine how much additional flow
can be sent on P we do the following:
1. Let e1 = min((ue xg) for each forward edge in P).
2. Let 2 = min(xe:edge e is a backward edge in P).
3. c = min(e1 ,&2 ) .
4. The augmented flow x' for each edge in P is as


13
follows:
x'
x + e, e is forward in P;
e
Jxg a, e is a backward edge in P;
x otherwise,
e'
\
Notice that augmenting the flow as above will result in
a new flow which is still feasible.
Example 2.1
The graph G represents a network with the following
capacities ue, and flows xg, associated with each edge:
ua = 3' ub = 5' uc = 2' ud = 4' ue = 3
xa = 3' xb = 1' xc = 2' xd = 1' xe = 3
The path p = {d,c,b} is a flow augmenting path because
the forward edges d and b both have flow less than
capacity, and the backward edge c, has nonzero flow. It
can be determined that s = 2, and the augmented flow x
is as follows: x' = 3, x' = 3, x' = 0, x' = 3, and
a b c d
x' =3.
e
A CUTSET is a set of edges such that their
removal would cause the graph to become disconnected.
We denote the forward edges in the cutset by &(S) and
the reverse edges in the cutset by S(S), where £>(S) =
{e £ Ere has exactly one endpoint in S and S is the set


14
of vertices on one side of the cut}. An (s,t)-cut is a
set of the form 5(S) where s E S C V\{t} and u(5(S)) is
the capacity of the cut.
Lemma 2.1
For any feasible flow x, and any set S where s E S C
V\{t}, then t(x) = x(5(S)) x(5(S)).
A proof of Lemma 2.1 may be found in Ford and
Fulkerson (FF62).
Corollary 2.1
For any feasible flow x and any set S, s E S C V\{t},
then t(x) <, u(5 (S)) .

The proof of Corollary 2.1 may also be found in Ford
and Fulkerson (FF62).
Consider the case where t(x) = u(S(S)) for some
sESCV\{t}. No additional flow can be passed
through S(S), because it is at capacity. It follows
from Corollary 2.1 that t(x) cannot be increased, so x
is a maximum flow and S(S) is a minimum capacity cut.
Corollary 2.2
Max{t(x):x is a feasible flow) < min{u(S): s E S C
V\{t}}.


15
Theorem 2.2
A feasible flow x is maximum if and only if there
exists no x-augmenting path.
Proof:
First, assume x is a feasible flow which is maximum.
Since x is maximum, then it cannot be increased, so it
must be that no augmenting paths exist. Secondly, assume
there is no augmenting path in the network. Let S be a
set of vertices that can be reached from vertex s by a
flow augmenting path. By definition of S, s E S, and t
is not in S. By Lemma 2.1, t(x)' = x(5 (S)) -x(5 (S) ) .
Because there are no flow augmenting paths, then
x(5(S )) = 0 and x(S(S)) = u(5(S)), hence t(x) =
u(5(S)). It follows from Corollary 2.2 that x is a
maximum flow.i
By Theorem 2.2, to find the maximum flow, it
suffices to search for flow augmenting paths. If we
can find a flow augmenting path, then we increase the
flow along that path. If no flow augmenting paths
exist, then we cannot increase flow to t, thus t(x) is
maximum and the flow x is optimal. As in the proof of
Therem 2.2 there exists a cut S(S) with u(5(S)) =
t(x). The following theorem due to Ford and Fulkerson
formalizes the above discussion.


16
Theorem 2.3 (FF62} Max-Flow, Min-Cut Theorem
The Max{t(x):x is a feasible flow} = Min{u(5(S)): s G S
G V\{t}}.
No proof of Theorem 2.3 is given as we have
already proven it in the above discussion.
The following Maximum Flow Algorithm due to
Ford and Fulkerson finds the maximum flow by searching
for flow augmenting paths.
Maximum Flow Algorithm:CFF62}
STEP 0: Begin with a feasible flow x = 0.
STEP 1: Let T = G({s}, STEP 2: If xe = ue for all e E S(V(T)) and xq = 0 for
all e G 6(V( T)) then STOP; x is a maximum flow and
5(V(T)) is a minimum capacity cut.
STEP 3: Choose e G &(V(T)) having xg < ug or e G &(V
(T)) having xq > 0. Add e and it's other end to T. If
t E V(T) go to Step 4, else go to Step 2.
STEP 4; The path P from s to t in T is flow-
augmenting. Augment x to x' as follows, then go to
Step 1.
a) = min(ue xg) for each forward edge in a path P
from s to t;
b) = min (xe:edge e is a backward edge in path P);
and


17
c) c = min(£1,e2).
d) The augmented flow x' for each edge in P is as
follows:

X + e, e is forward in P;
e
xe - e, e is a backward edge in P;
x , otherwise.
l e
Although the unrefined version of Ford and
Fulkerson's Algorithm above can take a number of steps
which is exponential to the size of the input, simple
refinements (see e.g. Edmonds(ED72)) yield an efficient
algorithm.


CHAPTER III
MATROIDS
A matroid is a combinatorial abstraction of
graphs and vector spaces. The history of matroids
dates back to the 1930's when the concept of a matroid
was first introduced by H. Whitney (WT33). Whitney
based his work on an abstraction of matrix theory that
related to graph theoretical properties. Other early
pioneers in this field include R. Rado (RD42) who wrote
on the combinatorial applications of matroids, and
Tutte (TT58, TT59), who characterized certain
subclasses of matroids including those arising from
graphs and those that can be related to vector spaces.
Recent research includes the use of matroid theory to
develop an efficient algorithm to test if a given
matrix is totally unimodular, and relating matroids to
network flow theory, which is the subject of Chapter
IV.
Matroids may be defined in different ways
through the use of various axioms. We will be working
largely with the "circuit" axioms definition, but we
will also make use of the "independence set" axioms
definition. There are many alternative definitions for


19
matroids that the interested reader may find in a good
reference book such as Matroid Theory by D.J.A. Welsh
(WL76).
We begin our discussion on matroids by
introducing both the circuit axioms and the
independence system axioms. The circuit axioms are
stated as follows:
Let E be a finite set and let C 0 be a family of
subsets of E.
Axiom 3.1 Clutter Property:
For all C1, C2 C C, if C1 ?! C then C1 is not
contained in C2.
Any family of subsets of E satisfying Axiom 3.1
is a clutter.
Axiom 3.2 Circuit Exchange Property:
For all C2 C C, where C1 2 C^, if e G (c n C ),
then there exists C3 G C such that C3 is contained in
(C1 U C2)\{e}.
A set M = (E,C) defined on a set E, with
"circuit" set C that satisfies the circuit Axioms 3.1
and 3.2 is a MATROID.


20
EXAMPLE 3.1
Let the set E be the set of edges of the graph, and the
set C be the set of graph theoretic circuits of the
graph. So we have E = {a,b,c,d,e,f} and =
{a,b,c,e}, C2 = {c,d,f}, C3 = {a,d,f,e,b}. Note that
no CL G C is contained in any other CL, so the clutter
property holds. We now illustrate the circuit exchange
property. Select two circuits, for example C1 and .
C1 t C2 and c G C1 fl C2. Now form (C^ U C2)\{c) =
{a,b,e,d,f}. Note that this set is equal to C3, thus
the circuit exchange axiom holds for this choice of
circuits. It is simple but tedious to check that the
circuit exchange axiom holds in all cases. Since the
edge set E and the circuit set C satisfy the circuit
axioms, M = (E,C) is a matroid.
EXAMPLE 3.2
Let M be the following matrix:
a b c d e f g
1 1 2 0 0 1 2
1 0 1 0 0 0 1
1 0 1 0 0 0 1
0 0 0 1 0 1 -1
0 0 0 2 1 3 -2
The columns of M={a,b,d,c,e,f,g} are the set E and the


21
circuit set C can be defined as all minimal sets of
dependent columns of M.
The circuit set C contains the following circuits:
Cl = {a,b,c}, C2 = {b,d,e,f}, C3 = {c,d,g}
C4 = {b,c,e,f,g}, C5 = {a,b,d,g}, C6 = {a,b,e,f,g},
C7 = {a,b,d,e,f}.
It is easy to see that no circuit is contained in any
other circuit, so the clutter property holds. As in
Example 3.1, it would be a simple, but tedious task to
check that the circuit exchange axiom holds in all
cases. We will illustrate how the axiom is checked on
two circuits, C.^ and C5. The axiom should however, be
checked for all pairs of circuits in C. Consider ^ 2
C5 and a G n C5). Now, (C1 U C5)\{a} = {b,c,d,g}
and {b,c,d,g} D C^. Since the column set E, and the
circuit set C satisfy both the clutter and circuit
exchange properties, M = (E,C) is a matroid.
An alternative definition for matroids is based
on the "independent system" axioms. Let E be a finite
p
set of elements, and let St G 2 then (E,&) is an
independence system if the conditions given in Axioms
3.3 and 3.4 are satisfied.


22
Axiom 3.3
$ E &
Axiom 3.4
If X E &, and Y C X, then YES.
The independence system (E,&) is a matroid if
additionally, the following axiom is satisfied.
Axiom 3.5
If X,Y C & and |X| = |Y| + 1, then there exists e E
(X\Y) such that YU {e} E S.
Some examples of independence systems are
presented below.
Example 3.3
ial Let E = {1,2,3,......,n} and S ={XCE:|X[<4}
This example is an independence system because Axiom
3.3 is satisfied by $ E S, and Axiom 3.4 is clearly
satisfied.
(b) Let E^ = {v.^,v2,..,vm) E Rn, and let = (X C
Eb:X is a linearly independent set}. Clearly $ E so
Axiom 3.3 is satisified. Since any subset of a
linearly independent set of vectors is also linearly
independent, Axiom 3.4 is satisfied.


23
(c) Let E = (e:e is an edge of the given bipartite
c
graph G), and let & = (X G E :X is a matching}.
G C
Axiom 3.3 is satisfied since the empty set is a
matching. Axiom 3.4 is satisfied since any subset of a
matching is a matching.
(d) Let E^ = edges of the given graph = {a,b,c,d}
Define = {X & E^:X has no graph theoretic
circuits). Once again Axiom 3.3 is clearly satisfied
by # G Axiom 3.4 is also satisfied since if a set
X G does not contain a circuit, any subset Y C X
does not contain a circuit.
We now determine whether the above examples are
matroids by checking to see if Axiom 3.5 is satisfied.
Example 3.4
Assume the independence systems (Ea,&a), (),
(Ec,&c), are defined as in Example 3.3.
(a) To illustrate how Axiom 3.5 is verified let X =
{1,2,3} and Y = {2,3}. Form X\Y = {1} and note that Y U
{1} = {1,2,3} G &. That Axiom 3.5 holds for all X and


24
for all Y with |Y| = |X| 1 can be checked in a
similar manner to verify that (E S ) is a matroid.
fb) If X and Y are both sets of linearly independent
columns, with |X| = |Y| + 1, then the rank of the
subspace spanned by X is greater than the rank of the
subspace spanned by Y. Thus, there must exist some
column e G X that cannot be written as a linear
combination of elements of Y, and so (YU {e}) is
linearly independent. Thus (E^*^) is also a matroid.
(c) The independence system (E & } is not a matroid
c o
and we use a counter-example to show this. Let X =
{a,d,g} and Y = {c,f}. No element of X can be added to
Y and still have a matching, thus Axiom 3.5 fails.
(dT To illustrate how Axiom 3.5 would be verified in
Example 3.3(d), let X = (a,c,e) and let Y = {a,c}.
Form (X\Y) = {e} and (Y U (e)) = {a,c,e} = X G &d As
in the previous examples, it can be easily shown that
Axiom 3.5 holds for this example by checking all
cases. Thus the independence system in Example 3.3(d)
is a matroid since Axioms 3.3, 3.4, and 3.5 are
satisfied.
The following definitions are associated with
matroids related to the independent system axioms. A
BASE of a matroid is a maximal, independent subset of
E. The RANK function r(s), of a matroid is defined on
the subsets S of E and is the cardinality of a maximal


25
independent subset of S, i.e., r(s) = max{|X|: X C S, X
E &}, where S C E.
Example 3.5
(a) Refer to the matroid M given by Example 3.3(a). A
base of M is {1,2,3,4} and if S = {1,2,3} then the rank
r(S) = 3.
(b) Let M be a matroid on the following set of
linearly independent vectors.
a b c d e
A base of M is {a,b,c,d,e}. If S = {a,c,d,e}, then
the rank r(S) = 4.
(c) Let M be a matroid as given in example 3.3(d). A
base of M is {a,c,d} and if S = {a,c,e,d} then the rank
r(s) = 3.
We have so far looked at matroids defined using
the circuit axioms and matroids defined using
independence system axioms. Although the axioms are
quite different, there is some relationship between
them. Let's look first at circuits. It can be easily
shown (WL76) that a circuit is a minimal dependent set.
If any one element of a circuit is removed, the result
is an independent set. Similarily, a base is a maximal


26
independent set so any element added to a base yields a
dependent set and thus contains a circuit.
We now return now to matroids as defined by the
circuit axioms and discuss some further definitions and
* A
properties related to them. Consider a set C which
satisfies the Circuit Exchange Property but not the
A
Clutter Property. Note that C is the set of dependent
sets (they're not independent as the sets contain
A
circuits). Form a new set C = min (C) by deleting
A A
those sets C £ C that contain another element of
A A
C. Using the definition of C, it can be easily checked
A
that the Clutter Property holds for C. It is also easy
to verify that the circuit exchange property is still
A
satisfied, so the set M = (E,C) is a matroid.
A A
Given a matroid M = (E,C), form a set D, where
A
D is the family of subsets D, D 2 0, of E, which
satisfy the following:
Property 3.1
|cnD|*i,vcec.
A A
If we let D = min(D) by deleting from D all
elements which contain another then the following
theorem holds.


27
Theorem 3.1
D is the set of circuits of a matroid (E,D).
A proof of this theorem may be found in (WL76).
Notice that if M = (E,C) arises from a graph as'in
Example 3.3d, then the set D is the set of all cutsets
of the graph G. This follows from the fact that |C n
D| = 0(mod 2) for all circuits C and cutsets D of a
. *
graph. In general, we call the matroid M = (E,D),
where D is defined as above, the DUAL MATROID of M =
(E,C), and we call D the COCIRCUIT set of M. By the
symmetry of Property 3.1, it follows that (M ) = M.
Our discussion of matroid theory continues by
looking at some special classes of matroids.
Theorem 3.2
If G is a graph, then the (graph theoretic) circuits of
G are the circuits of a matroid M(G) on E(G). Such a
matroid is called the CIRCUIT MATROID of G.
It is easy to verify that the set C = (circuits
of a graph G} satisfies the circuit axioms (see example
3.1). The details of the proof are left to the
reader. A matroid M is a GRAPHIC MATROID if it is the
circuit matroid for some graph G.
We now look at the bases of a graphic matroid.
Recall, that a base is a maximal independent subset of


28
E. Such a subset for a graph would be a spanning tree,
if G is connected, or a spanning forest if G is not
connected. Therefore, the bases for graphic matroids
are either spanning trees or spanning forests.
Example 3.6
a
b
d
e
f
c
Let G be the graph shown. The edge set of G contains
the following circuits: = {a,b,c,d}, C2 = {e,d,f}
and C3 = {a,e,f,c,b}. It is easy to check that the
circuit axioms are satisfied on the set (E,C), so we
can define a graphic matroid M(G) having the circuits
C1,C2'C3 G* To a kasi-s for M(G) we want to find
a spanning tree of G, since G is connected. One
possible basis of M(G) is:
a
b
c
Because circuits in a graph are fixed for that
graph, then a graph uniquely determines a graphic
matroid. Can we say the converse of that statement is
true, that is, does a graphic matroid uniquely
determine a graph? To show that the converse is not


29
true, we present a counter-example.
The only circuit of either graph is {a,b,c}.
Thus is isomorphic to M(G2). (Two graphs G1 and
G2 are isomorphic if there exists a permutation mapping
vertices of G1 to vertices of G2 that preserves
adjacencies. Two matroids and M2 are isomorphic if
there exists a permutation mapping elements of M1 to
elements of M2, while preserving circuits). Note that
G^ is not isomorphic to G . ' ^
We can define a cographic matroid using the
sets of cutsets of a graph. A matroid whose circuits
are the minimal cutsets of a graph is called the
COGRAPHIC MATROID. The cocircuit matroid of a graph G
is the. dual of the graphic matroid of G. The reason is
simply due to the property that if D is a cutset of G,
|C n D| = O(mod 2), and so the cutsets of G are the
cocircuits of M(G).
If G is planar, then the planar dual, G has
circuits corresponding to the cutsets of G. In this
case, the cographic matroid M(G) is isomorphic to
k ,
M(G ). If G is not planar, the cographic matroid is
not a graphic matroid. (If it were, there would be a


graph G' whose circuits are in one-to-one
correspondence with the cutsets of G, which is only
possible for planar graphs.)
30
Example 3.7
Consider the following bipartite graph.
The above bipartite graph is called K_ _, and is an
example of a nonplanar graph. Therefore the cographic
matroid of K3 3 is not graphic.
Before continuing our discussion of specific
classes of matroids, we present an interesting property
of matroids due to Minty (MT66). The following theorem
is called the "painting" theorem, and will be used
extensively in Chapter IV.
Theorem 3.3 (MT66)
. , , rk
(Painting Theorem) Let M = (E,C) and M = (E,D) be a
pair of dual matroids and let E=RUGUBbea
partition of E with [G| =1. Exactly one of the
following properties will hold:
3.3a) There exists a green-blue circuit C G C.
or
3.3b) There exists a green-red cocircuit D G D.


31
The proof of this theorem follows, but we need
to present the idea of a hyperplane in order to
complete the proof of Theorem 3.3. A hyperplane is a
maximal set H C E with rank(H) = rank(E) 1.
Lemma 3.1 fWL76^
tfc k
If E\H is independent in M then E\H C X is contained
"k k
in a basis X of M .
Lemma 3.2
If H C E is a hyperplane in M, then E\H is a circuit of
k
the dual M .
Proof:
k
First it must be shown that E\H is dependent in M .
'k k
Suppose that E\H is independent in M Then, E\H C X
it it
is contained in a basis X of M Note that E\H is a
base in M*. So E\(E\H) 3 E\X* is a basis of M.
Therefore, rank(H) = rank([E|). This is a
k
contradiction! Thus E\H is dependent in M Secondly,
k
we show that E\H is minimally dependent in M Let e E
E\H, then HU {e} has rank(H U e) = rank(E). Thus, H U
{e} contains a base X of M such that X C H U {e}.
Therefore E\(H U e) C E\(X) which is a base of M*. This
implies that the set E\(H U e) is independent in M for
k
any e, so (E\H)\e is independent in M Thus E\H is
k
minimally dependent in M which implies that E\H is a


32
. *
circuit of the dual M .I
Now, we present the proof of the painting
theorem.
Proof:
First we show that both properties 3.3a and 3.3b cannot
occur simultaneusly. To do this we assume the
contrary, i.e., both property 3.3a and 3.3b hold. Let
*
element e represent the green element. By property
3.3a there exists a blue-green circuit CL, and by
property b) there exists a red-green cocircuit both
containing e It must be that | CL n D^| = 1, since
the only element common to both CL and is e This
is a contradiction of Property 3.1, so both 3.3a and
3.3b cannot hold at the same time. Now it will be shown
that at least one property, either 3.3a and 3.3b must
hold. To accomplish this we assume that property 3.3a
fails and show that property 3.3b must then hold. If
property 3.3a fails then any circuit containing the
_ *
green element e must also contain red elements. The
element e E span(B) because if it were not then, 3e £
*
CCBUe CBUG which is Property 3a. Therefore
rank(B U e ) > rank(B), which implies rank(B) < rank(B
k
U e ) < rank(E) so rank(B) <; rank(E) 1. Hence, there
is a hyperplane H 3 B with e H, and E\H C D by Lemma
3.1. Also, since B C H, E\H C R U G. Thus property
3.3b holds, and the theorem is proven.!


33
Not only is Theorem 3.2 interesting in relation
to matroids, it implies the Fredholm Alternative in
linear algebra. Before we discuss the Fredholm
Alternative, we need to present representable matroids.
A matroid M = (E,S) which can be defined by
linear independence in a vector space over some field
F, is called a REPRESENTABLE or MATRIX matroid. An
example of such a matroid is given in Example 3.5b.
The matrix A= (I | B) is a STANDARD MATRIX
REPRESENTATION of the matroid M, with respect to the
basis {e ,e2,...en). Note that by pivoting one can
obtain a standard representation with respect to any
basis. A matroid that is representable over GF(2) is
called a BINARY MATROID.
Theorem 3.4 CHR69)
All graphic matroids are binary.
A proof is not given as we've demonstrated this
concept earlier using the incidence matrix of a graph,
see Example 3.2. The following property and corollary
are required in order to show that the painting theorem
for matroids implies the Fredholm Alternative for
vector spaces.


34
Property 3.2 fWL76^
Let M be a representable matroid represented by the
matrix C. Let C be a matrix in which the rows of C
^
are a basis for the null space of C. Then C represents
the dual M .
Corollary 3,1
. *
If M is represented by [A III/ then M is
mxn m
T
represented by [I |-An x ml
Proof:
, T
A | I I -A
1 m n 1
= A | I I
1 m n -A
= A A = 0.1
We now use the Painting Theorem to prove
Fredholm's Theorem. (See Linear Algebra and it's
Applications by Strang (ST80) for a traditional proof
of this theorem.)
Theorem 3.5 (Fredholm's Theorem of the Alternative!
For any m x n matrix A and m-vector b, one and only one
of the following systems has a solution:
(a) 3x such that Ax = b.
(b) 3y such that A^y = 0, y^b 2 0.


35
Proof:
Let M be a matroid represented by, and colored as
follows:
A | b | I
in
B G R
Note that if property (a) holds, there exists a blue-
green circuit containing the green element. We first
show that not both property (a) and property (b) hold.
If they did both hold, then ATy= 0 => yTA = 0 => yTAx =
T . . . .
0 => y b = 0, which is a contradiction. Now, it must be
shown that at least one of the two properties holds.
Assume that property (a) does not hold, i.e., there
does not exist a blue-green circuit. By Minty's
Painting Theorem there exists a red-green cocircuit,
(containing the green element) which implies 3 a red-
green circuit (containing the green element) in the
dual. By Corollary 3.1 the dual is represented by:
I - A T
n + 1 T
B G - b R
The green column in the dual is dependent on the red
columns, so there exists y such that:
0 T
- A
t"
0 - b
1


36
The above equation shows that alternative b) holds and
this completes the proof.
Before we continue our discussion of different
classes of matroids,' we present three operations
associated with matroids: deletion, restriction, and
contraction. The results of these operations are
called matroid MINORS, and are analogous to the graphic
minors discussed in Chapter I. Let E C T be a subset
of elements of a matroid, and let C|T={CEC: CCT}.
The minor operations can be defined as follows: M|T =
(T,C|T) is called the RESTRICTION of M to T C E. M\T =
M|(E\T) is the DELETION of T C E from M. M/T = (M*\T)*
is called the CONTRACTION of T in M.
Theorem 3.6
M\T is a matroid.
The proof of this theorem is left to the
reader, as it is easy to show that the circuit axioms
hold for M\T. Similarily, it can be shown that M|T and
M/T are also matroids. A matroid N of M is a minor of
M if N can be derived from succesive applications of
restriction, deletion, and contraction.
Theorem 3.7 (WL76')
M\T = (M*/T)*.
Proof:


37
Let T C E, and take the contraction of T in M. We have
M/T = (M*\T)*. Similarly M*/T = (M\T)*. Taking the
dual of both sides gives (M /T) = (M\T).i
The above theorem shows that the operations of
contraction and deletion are "dual operations". The
reader is referred back to Chapter II for an example of
the minor operations on graphs.
An important class of matroids is the class of
regular matroids. Included in this class are graphic
and cographic matroids. There are also regular
matroids that are neither graphic or cographic. There
are several equivalent definitions of regular
matroids. The simplest definition is that a regular
matroid is one which is representable over any field.
Theorem 3.8 (TT71)
Is G is a graph and F is a field, then the matroid M(G)
has a matrix representation in which every entry in A
is 0 or a unit of the field F, and each column has only
two non-zero entries.
We omit a proof, but note that when F= GF(2),
the vertex-edge incidence matrix illustrates the
theorem. Thus graphic matroids are regular.
An alternative definition due to Tutte (TT71)
is that a matroid M = (E,C) is called regular if an
only if it is the matrix matroid of a totally unimodular


38
matrix A. A totally unimodular matrix is a matrix
whose square submatrices all have determinant 0 or 1.
The reader is referred to (TT71) where it is shown that
this is an equivalent definition of a regular matroid.
Minty (MT66) defined regular matroids by
partitioning the circuits and cocircuits of a matroid M
= (E,C) into positive and negative elements as follows:
Partition the elements of a circuit C into subsets e E
C+ and e E C We call e E C+ positive elements, and e
E C negative elements. A similar partitioning can be
done for elements of a cocircuit D. We may now define
the partition property.
Property 3.3
Every circuit C E C and cocircuit D E D can be
partitioned into C = C+ U C and D = D+ U D such that:
|C+D D+|+|C n D | = |C+D D |+|C n D+|, for every pair
(C,D) E C X D.
Minty used the partition property to define
regular matroids: a matroid M = (E,C) with circuit set
C, and cocircuit set D is regular if and only if the
partition property is satisfied. The reader is referred
Minty's paper on matroids (MT66) to see why this
definition is equivalent to the definition of regular
matroids given above.
If A is an incidence matrix of a graph, we can


39
associate incidence vectors x having |E| components,
c
where x (e) E (0,1,-1), to the partitions of the
circuits as follows:
x (e) = 1 if and only if e E C+.
x (e) = 1 if and only if e E C.
x (e) = -1 if and only if e E C .
The same association holds similarily for cocircuits D.
Using the above relationship between
(co)circuits and incidence vectors, the definition for
a regular matroid due to Minty can be rewritten as the
ORTHOGONALITY PROPERTY.
Property 3.4 (Orthogonality Property)
M = (E,C) is a regular matroid if and only if it is
possible to assign to each C E C and D E D incidence
vectors xc, xD with components in {0,1,-1} such that:
xcTxn = l x (e)-x (e) =0 V (C,D) E C X 2)
^ u eEE U U
Example 3.8
Let G be the graph as shown.
1 a 2
3
e
4


40
An incidence matrix for the above graph is:
a b c d e
A = 1 11100
2 10 0 10
3 0 1 0 0 1
4 0 0 1 1 1
A circuit in A is {a,c,d} and a cocircuit is {a,b,c}.
x^-xD=l+0+l+0+0=0.
We will see in Chapter II how the partition
property of regular matroids leads to a network flow
function.
The Fano Matroid is an example of a matroid
that that is representable over GF(2), and thus is
binary. However this matroid is not regular, as it is
not representable over all fields. We denote the Fano
"k
matroid as F^ and it's dual as F?. The elements of the
Fano Matroid are the members of the set {1,2,3...7},
and the bases are all 3-sets of elements, except
and {3,6,7}. Even though the Fano Matroid is not
graphic it is still possible to diagram it as follows:
X^, (1,0,1,1,0)
xD = (1,1,1,0,0)
. T , ,
3
6
7
The the bases are all 3 sets except those occuring on a
line. Tutte proves that the Fano matroid is not regular


in Introduction to the Theory of Matroids. The next
two theorems can also be found in this book.
41
Theorem 3.9(TT71)
A binary matroid is regular if an only if it does not
, *
contain as a minor F7 or F7 .
Another type of matroid is included in the
class of "Uniform" matroids and is denoted U .. This
z ; 4
matroid is the independence system on four elements for
which every subset of size two or less is independent.
Tutte was able to characterize binary matroids as those
which do not contain U_ as a minor.
^ 4
Theorem 3.10 (TT7H
A matroid is binary if and only if it does not contain
U2 4 as a minor.
We conclude the discussion of matroids by
presenting a chart which shows the relationship between
the different classes of matroids.


42
MATROIDS
BINARY MATROIDS WHICH ARE
MATROIDS NOT BINARY
BINARY MATROIDS
WITH F* MINORS

v
BINARY MATROIDS
WITH NO F* MINORS
REGULAR MATROIDS BINARY MATROIDS
(NO F?/ F* MINORS) WITH NO F*, BUT
WITH Fy MINOR.
V ^
GRAPHIC MATROIDS COGRAPHIC REGULAR MATROIDS
MATROIDS MATROIDS, WHICH
ARE NEITHER
GRAPHIC OR
COGRAPHIC
Figure 1: Hierarchy of matroid classes


CHAPTER IV
MATROID FLOWS
We now show that it is possible to generalize
the ideas and concepts of network flow problems to
matroid theory. We will begin by looking at regular
matroids and network flows. It is possible to define
an algorithm to find the maximum flow in a regular
matroid. The idea of a matroid flow can be defined for
any matroid. Seymour (SY77) characterized those
matroids which satisfy a Max-Flow Min-Cut Property
analogous to the same property for network flows.
Recall the orthogonality property for regular
matroids, that is, a matroid M is regular if and only
if it is possible to assign to each C G C and each D £
2) incidence vectors xc, x^ G {0,1,-1} such that:
T
x *x = 2{x (e)*x (e): e G E} = 0.
CD C D
We use the orthogonality property of regular
matroids as a basis to generalize the ideas of network
flow theory to regular matroids. Consider graphic
matroids which we have seen are regular. If we assign
an orientation to each edge of an undirected graph and
partition each circuit C and each cocircuit D into C+,


44
C D+, D then it can be verified that the partition
property holds. "Complementa1" partitions can also be
defined in relation to the partitions C = C+ U C and D
= D+ U D as follows:
i+ _ i + i_ +
If C = C ; C = C ; D = D ; D = D ;
then, C = C + U C and D = D + U D
Example 4.1
Let M = (E,C) be a regular matroid with circuit set C,
where C is the set of circuits of the given digraph.
Consider a particular circuit, i.e., C1 = {a,c,d}. If
we run through the edges of C1 in a clockwise
direction, then C+ = {a,d} and C = {c}. Running
through the edges of in a counter-clockwise
, . i +
direction we get the complemental partition C = {c}
I _
and C = {a,d}. The partition property holds for
either partition.
As a matter of shorthand we will use the
following notation:
Ce={C6C:eGC},VeGE;


45
{C G C: e G C+}, VeGE;
{CGC: e G C~}, VeGE;
{C G E: C = C+};
{CGC: C = C-}.
We define 3£, 3*, 3e, 3+, and 3 similarily.
It will always be assumed that every e G E is contained
in at least one circuit CGC, and in at least one
cocircuit D G 3. We will also restrict ourselves to
studying flows with real capacity values, and for the
time being to regular matroids.
The value of a network flow was defined to be
the amount of flow passed from a distinguished vertex s
to a distinguished vertex t. In the case of matroid
flows, we define the value of a flow as the amount of
flow passed over a distinguished element e G E. We'll
call this distinguished element e.^ and define E' =
EXfe^. To put this concept into perspective, assume
that M = (E,C) is a regular matroid that is graphic for
a graph G = (E,V).
The value of a flow in G in terms of a network
flow problem would be the net flow into vertex t. The
elements of M(G) correspond to the edges of G. To


46
modify a network flow problem into a matroid flow
problem, we add a directed edge e1 from vertex t to
vertex s, and assign a capacity for e-j^ of infinity.
The value of the flow for the matroid is the flow going
from t to s over edge e1- This form of the network flow
problem is called the "circulation" form.
Let R denote the real numbers. Given a capacity
function for all elements in E1, k:E' => (0,) we
define a matroid flow as follows: A function f:E => R
is called a MATROID FLOW (M-Flow), if the following
conditions are satisfied. (For shorthand we will use
f(T) = 2{f(e) : e E T} for all T C E.)
Property 4.1: Capacity Property
0 < f(e) < k(e), V e E E.
Property 4.2: Cocircuit Property
l f(e) = f(D+) = f(D") = l f (e) VD E 3).
eED+ eED~
We call fCe^^) the VALUE of the M-flow, and f is
called a maximum M-flow if ffe^ is maximum over all M-


47
flows. Note that Property 4.2 corresponds to the
conservation of flow property discussed in Chapter 2.
In network flow problems we insist that the flow
entering any vertex (with the exception of the sink and
source vertices) equals the flow leaving that vertex.
This forces the flow across any cutset in the forward
direction to equal the flow across the cutset in the
reverse direction. Thus conservation of flow in
networks generalizes to Property 4.2. The following
lemma can be found in (HM80).
Lemma 4.l
Let f be an M-flow and D E 2) , then:
el
f(ex) < k(D+).
Proof:
Since f(e) > 0, Ve E E, we have that ffe^ < f(e1)
+f(D Me^) = f(D ). From Property 4.2 we have that
f(D ) = f(D+), therefore f(e) < f(D+) ^ k(D+).l
In analogy to flow augmenting paths in network
flow problems, we define the concept of a flow
augmenting circuit. First, define a cocircuit D E 2) to
I
be f-saturated if and only if the following are
t
I
satisfied:


Property 4.3 (HMSS1)
f(e) = 0, Ve e (D \{e1});
Property 4.4 (HM83)
k(e) f(e) = 0, Ve e D+.
The f-saturated cocircuits correspond to
saturated cuts in network flow problems.
Corollary 4.1 Maximum Criteria(HM83)
If there exists an f-saturated cocircuit, then f is a
maximum M-flow.
Proof:
Let D be an f-saturated corcircuit. Consider the flow
on element e^ Note that f(e1) = fCe^ + f(D-\{e1}),
since e.^ is the only element in D~ with flow. Thus
f(ex) = f(D~). But f(D-) = f(D+), and f(D+) = k(D+), by
Property 4.4., and it follows from Lemma 4.1 that the
flow is maximum.!
The idea is to repeatedly augment flow until a
f-saturated cocircuit is found. If one exists, then
the M-flow is maximum. If no f-saturated cocircuits
exist, then the flow can be augmented.


49
Lemma 4.2 (HM83)
Let f be a M-flow, and suppose C £ C+ Let £ E R be
el
chosen such that e < f(e)
f(e) for all e E C+\{e1).
(f + e) (e)
f(e) + c,
f(e) ,
for all e E C
Define
= f'(e) =
if e E C+ ;
if e E c" ;
otherwise.
and £ < k(e) -
Then f' is an M-flow.
Proof:
It must be shown that f' fulfills the both the capacity
property and the cocircuit property. The capacity
property is fulfilled since 0 < f'(e) < k(e), Ve E E,
follows from the choice of £. To show that the
cocircuit property is fulfilled let D E 2), and refine
the partition D+ and D as follows:
D> + III D+\C, D++= D+n c+, and o + i in D+n c".
A D = D"\C, D = D~n c", and in + i Q D-n c+.
Using the partition property,
ID++| |D+ | = |D-+| |D |.
By the definition of f',
f'(D+) = f(D+)+f(D++)+£|D++|+f(D+")-£|D+_|,
and
f1(D ) = f(D~)+f(D_+)+£|D_+|+f(D )-£|D |.


50
So we have that
f'(D+)-f(D") =
= f(D+)-f(D~)+f(D++)+f(D+_)-f(D_+)-f(D_+)
= f(D+)-f(D") = 0.1
We call a circuit for which the £ of Lemma 4.2
is greater than zero an F-AUGMENTING CIRCUIT. As in
network flow problems where flow was added to forward
edges and reduced on reverse edges, in matroid flows,
flow is augmented for positive elements e E C+, and
reduced from negative elements e E C If there exists
a flow augmenting circuit C, we want to send as much
flow as possible around C. The most flow that can be
sent on C E C is e of Lemma 4.2. A formal statement
ei
defining flow augmenting circuits is as follows. A
circuit C E C+e is a flow augmenting circuit if the
following properties are satisfied:
Property 4.5
k(e) f(e) 0, Ve E C+ \{e1).
Property 4.6
f(e) 0, Ve E C .


51
Theorem 4.1 Augmenting Circuit Theorem CHM83)
If C is a flow augmenting circuit, then there exists a
M-flow f' satisfying f1 (e^ > ffe^.
Proof:
Assume C is a f-augmenting circuit.
Let = min(k(e) f(e)) for e G C+\{e1>;
c2 = min f(e) for e G C ;
and let c(C) = min (c ,& ).
By Lemma 4.2, f + e(C) is an M-flow. Note also that
f1(e^) > f(e1) since e^ G C+ and e(C) 2 0.1
Up to this point, it has been shown that if an
augmenting circuit exists we can increase the value of
the flow. The following theorem shows that if no
augmenting circuit exists, the value of the current
flow is in fact maximum, so that it suffices to look
for augmenting circuits when searching for the maximum
flow.
The following lemma which is a strengthening of
the Circuit Exchange Property is needed to prove
Theorem 4.2.
Lemma 4.3 (BL781
if cf c2 g c, X g (c+ n c2) u (c~ n c2)
and y G (C^\C2^ U (ci\C2^' then 3C3 with:


52
C+ C (C+ U C+)\ X,
C~ C (C U C")\ X,
and
Y e c3.
Theorem 4.2 (HM83)
If there are no f-augmenting circuits the current.flow
is maximum.
Proof:
Assume that no f-augmenting circuits exists, then for
all C e C+, there is an element e = e(C) satisfying
el
either

a) e(C) G C and k(e(C)) f(e(C)) = 0.
or
b) e(C) G C" and f(e(C)) = 0.
Let S = U{e(C): C G C+ } Let S' C S be a minimal set
el
satisfying | S' fl C| >1 for all C G C+ Note that for
all e G S', 3C with S' n C = e. We want to say that Ve
G S', 3C with e = e(C) and S' n C = e, (i.e., if e is
at capacity, we want e in C+, or if e has a flow of
zero, we want e in C ). If e = e(C), we're done,
otherwise e = e1 = e(C1) for some C^. Suppose S' fl
= e2,...e^}. If k = 1, then we're done. By
minimality, 3C ,C_,...C. such that S' DC. = e. for j =
£ o jC 3 3
2,...k. Note the element e.^ used in this context is
not the distinguished element e^ Suppose (without loss
+
of generality) e1 G C^.
= e^. If e^ G C* then
Let x


53
without loss of generality let e^ E C^.. Conversely, if
+ '
e^ E then let e^ E C^. If e1 E C^, by Lemma 4.3, 3C^
C (C1 U C^) with e1 £ Cj, and e^ E C^, so we can assume
e1 £ C^,. Now let y = e1, then again by Lemma 4.3, 3C^ C
. ' + 1
(C1 U with e1 E C1 and e^ £ C1 Now we have e^
t
G S' fl C- C {en,e ...e, }. Repeating the process,
there exists some C, with e^ E C+, (so e1 can play the
role of e(C)) and S' D C = e.^. A symmetric argument
works if e1 E Since 6 = 6^^ was arbitrary, we have
that for all e E S', 3C with S n C = e, and e = e(C).
We now employ the Painting Theorem 3.3
presented earlier to complete the proof. Let R = S', G
= (e1>, and B = E\(S' U (e^). Assume that a circuit C
is green-blue, as in alternative 3.3a), then without
loss of generality C E C+ By definition of S', |S' n
el
C| >1. Therefore, C contains a red element, which is
a contradiction. From the Painting Theorem, it must be
that a green-red cocircuit exists as in alternative
3.3b), i.e., {e1> C 3 C (S' U (e^). Without loss of
generality, e.^ E D Choose any e E D\{e1). It must be
that S' n C = {e} for some C. We have then that D n C
= (e^,e). Because e^ E C+ n D and M is regular, the
partition property implies that either e = D+ n C+ or e
= D D C+. Thus we have either:


54
i) e G D+=> 3C G C+ e = e(C) G C+
el
=> k (e) f(e) = 0
or
ii) e G D"\{e } => 3C G C+ e = e(C) G C~
x el
=> f(e) = 0.
This implies that D is an f-saturated
cocircuit, and the flow is maximum.!
The Maximum Flow Minimum Cocircuit (MF/MC)
Theorem for regular matroids can be stated in an
abbreviated form simply as:
max f(e.) = {min k(D+) : D G 3 }.
1
The MF/MC theorem tells us that to find a
maximum M-flow we can look for f-augmenting circuits
until we determine that an f-saturated cocircuit
exists. This parallels exactly the network flow
algorithm, where we look for flow-augmenting paths or
determine that there is a cut at capacity. As with
network flows, we can now state an algorithm that finds
maximum M-flows by searching for f-augmenting circuits.
AUGMENTING CIRCUIT ALGORITHM
START: Let f be an M-flow.
STEP 1: Determine an f-augmenting circuit C. If none
exists go to step 3.


55
STEP 2: Define f = f + a(C), go to step 1.
STEP 3: There exists an f-saturated cocircuit D.
Therefore .f is maximum with f (e1) = k(C+). STOP.
Note that if the capacities are integer each
augmentation will be integer and so the maximum flow
will be integer valued. It is easy to verify that this
algorithm works identically to the network flow version
by using as an example a graphic matroid. We now
present an example of a flow in a matrix matroid that
is also regular.
Example 4.2
Let M = (E,C) be the matroid represented by the given
matrix A.
A
a b c d e
11-110
-1-1 1 0 1
The circuits and cocircuits along with their respective
orientations are as follows:
Cx = {b+,c+} C4 = {a+, d+, e+}
C2 = {a+,b+} C5 = {b",d+,e+}
C3 = {a+,c-} C6 = {c",d,e~}
and
Dx = {e+,d-} D2 = {a+,b",c+,d} D3 = {a,b+,c",e+}


Let "b" be the distinguished element, and assign the
following capacities:
56
oT II k(c) = 3 k(e) 4
k(b) = os k(d) = 2
Let f^ be a vector representing the current flow on the
elements for the ith iteration of the algorithm. The
algorithm begins with fQ = (0,0,0,0,0) and searches for
a flow augmenting circuit (FAC). Note that C.^ is a FAC
with & = 3. We augment the flow by 3 units and the new
flow vector is f^ = (0,3,3,0,0). The algorithm
searches for another FAC. The circuit C2 is a such a
circuit with & = 4. We augment the flow by 4 units and
the new flow vector is f2 = (4,7,3,0,0). The algorithm
searches for another FAC but none exist. It must be
that a saturated cocircuit exists and that the flow is
maximum. It can be easily verified that D2 is a
saturated cocircuit. The maximum flow is given as:
f (a) = 4 f(c) = 3 f(e) = 0
f(b) = 7 f(d) = 0
We have shown thus far that is is possible to
have a matroid flow on a regular matroid, and that
there exists an algorithm for producing a maximum flow.
We turn now to work by Seymour who shows that it is
possible to-generalize the idea of a matroid flow to a
larger class of matroids. There is not, however a
known algorithm for these matroid flows. We begin this


57
discussion by taking a slightly different approach to
the network flow problem.
Once again consider the circulation form of the
network flow problem. In terms of a linear programming
problem (LP), we can express the maximum flow over the
network as follows:
LP 4.1
Maximize x
el
subject to: Nx = 0
0 < x < k.
where xg represents the flow over the distinguished
edge e^, k represents the vector capacities of edges e
E E, and N is the vertex-edge incidence matrix of a
digraph D, representing the network.
Now suppose that the graph representing the
network has undirected edges. The LP is then stated as
follows:
LP 4.2
Maximize x
el
Subject to: Nx = 0
-k < x <; k.
If we replace each undirected edge of the graph
with two edges in opposite directions, then the above


58
LP simply reduces to LP 4.1. This shows that the two
problems may be thought of as the same.
We earlier characterized representable matroids
as those which can be represented by a matrix. The LP
form of the network flow problem generalizes to
representable matroids. Replace the matrix N by an
arbitrary matrix A. Recall that N is a representation
of a graphic matroid. The set of usable circuits
(circulations) are the supports of vectors in the
orthogonal complement of the row space of the matrix A.
We want to be be able to generalize the LP form
of the network flow problem over arbitrary matroids,
not just those that are representable. To do so, we
present the "path form" of the LP for a graph G.
Define a PATH SET ? = {C\{e1) : e1 E C E C}. Let A be
a (0,1)-incidence matrix with columns representing
E(G)\e1, and the rows of A representing paths PSP.
The path form of the maximum flow problem is the LP:
LP 4.3
Maximize l*y.
subject to: yA < k
y > 0


59
Theorem 4.3
The maximum value of the flow x (from LP 4.1) equals
el
the maximum value of l*y defined in LP 4.3.
The above theorem is intuitively obvious, but a
proof of it may be found in Combinatorial Optimization
by Lawler (LW76).
Example 4.3
Let D be the digraph above with capacity function k(e)
defined as follows:
k(ex) = = CO k(c) = 2 k(f) = 2
k(a) = = 2 k(d) = 4
k(b) = 4 k(e) = 4
We have that T = {b,e,f}} and a b c d e f
> II h* 1 0 0 1 0 0
P2 0 1 1 1 1 0
P3 0 1 0 0 1 1


60
The linear programming problem is:
Maximize: y + y2 + Y3
Subject to: y*A <, (2,4,2,4,4,2)
y > 0
If 2> denotes the collection of edge-sets of
minimal cut-sets in a graph G, we can define a set K =
{D\{e }: ex G D G 3}. If we form K n P for any KG K,
and P E T, we know that this set must be non-empty
since any s-t path uses an edge of every s-t cut.
Since if yA < k(e), then it can be shown that the
capacity of a cut K is an upper bound on the value of
any flow:
£{k(e) : e e K} = k-xk > (yA)xk = y(Axk) > y-l.
where: K E K, xk is the (0,1)-incidence vector of the
set K. Let k' represent the minimum 2{k(e) : e E K}
over all cuts K. The fact that k' > l*y is an example
of linear programming weak duality.
Theorem 4.4 (see e.q. BX82)
The maximum value of l*y in LP 4.3 equals the minimum-
1.
cut capacity of a graph G. Also, if k(e) is integral,
then there is an integral vector y that solves LP 4.3,
and K E K is a cut.
This is simply a restatement of the Max Flow-


61
Min Cut Theorem in Chapter III.
Example 4.4
Refer to example 4.3 The set of cuts K =
{{a,b},{e,c,d}, {a,c,f}, {d,f}, {a,e}, {b,c,d}}, and
the minimum capacity k1 =6.
Theorem 4.5
The maximum flow value for M = (E,C) with capacity
function k(e) is less than or equal to the minimum-cut
capacity.
The proof of this theorem follows the proof of
the analogous theorem for graphs. The only thing left
to be shown in order to use the same proof is that for
PEP and KEK, P n K 2 $. This fact can be verified
by noting that PEP implies P = C\e1, e1 E C E C; and
KEK implies K = D\e1, e^ E D E 2). Also e1 E C D D
implies 3e ^ e^ E E, such that e E C D D, (since |C fl
D| 2 1) which implies that e E P n K.
A matroid M = (E,C) is said to have the
Maximum-Flow/Minimum Cocircuit (MF/MC) property if the
maximum-flow value equals the minimum-cut capacity. A
matroid M = (E, C) is said to have the STRONG MF/MC
property if whenever k(e) is integral for all e E E,
then y from LP 4.3 is integral. Graphic matroids have
the strong MF/MC property, but arbitrary matroids in


62
general, do not. We will be interested in those
matroids that do have the strong MF/MC property. The
following example presented in Bixby's Matroids and
Operations Research shows that the uniform matroid U
does not have the strong MF/MC property.
Example 4.5 fBX82^
Let M= the uniform matroid U2 4 with E = {a,b,c,e1),
with distinguished element e.^ and k(e) =1 for elements
a,b,c and ^(e^^) = The set of paths, P= {{a,b},
(a,c), {b,c}} and the corresponding path-incidence
matrix A is given as follows:
a b c
Oil
110
10 1
In this example K = P and the minimum cocircuit
capacity must equal 2. Summing the constraints in yA <
k(e) gives
2Yi + 2Y2 + 2y3 i 3
=> y i + y2 + y3 s 3/2.
Therefore the maximum flow value is no larger than 3/2,
and must be smaller than 2, the minimum cocircuit
capacity. Thus it must be that the uniform matroid
does not have the MF/MC property. Also note that we


earlier showed that no binary matroid can contain the
uniform matroid. The following lemma implies that no
non-binary matroid can have the MF/MC property.
63
Lemma 4.4 (BX82^
If M has the (strong) MF/MC property, then all it's
minors have the (strong) MF/MC property.
Proof:
We present the proof for the case of deletion only;
similar proofs work for contraction and restriction.
Recall that the circuits of M\T are those C G C with C
C E\T. Let T C E and let M' = M\T. We must show that
if M has the MF/MC property, then M' also does. If k is
a capacity function of M, let k' be a capacity function
for M* defined as follows:
k'(e) = k(e), V e E E\T.
k'(e) = 0 for e E T.
Let y be a maximum flow and let k be a minimum cut for
M. By the choice of k', Y and K will also give a
maximum flow and a minimum cut in M'. Thus if M has the
(strong) MF/MC property so does M'.I
Theorem 4.6
If M has the MF/MC property, then M is binary.
The above theorem follows from Example 4.5
using the uniform matroid U2 4, Lemma 4.4 and Theorem


64
4.5. Theorem 4.6 tells us that for a matroid to have
the MF/MC property it must be binary. However, it is
not necessarily true that all binary matroids have the
MF/MC property. We present a counter-example borrowed
from Bixby's Combinatorial Optimization.
Example 4.6
Let M be the-self dual matroid represented by the
following matrix:
1
0
0
0
0 0 0 1 1
1 0 0 1 1
0 10 10
0 0 10 1
1
0
1
1
0
1
1
1
The MF/MC property fails to hold for k(e) =1, and for
every choice of distinguished element e1-
As noted earlier, the following theorem holds:
Theorem 4.7
Regular matroids have the; strong MF/MC property.
The next example also borrowed from Bixby shows
*
that F^ does not have the strong MF/MC property.
Example 4.7
Let M = (E,C) be the dual Fano matroid F^. We can
represent F7 by the following binary matrix.
1 0 0 0 1 1 0
0 1 0 0 1 0 1
0 0 1 0 0 1 1
0 0 0 1 1 1 1


65
Let column 7 be the distinguished element e1. Then the
path-element incidence matrix P can be computed as
follows:
1 2 3 4 5 6
0 1 1 1 0 0
p = 1 0 1 0 1 0
1 1 0 0 0 1
0 0 0 1 1 1
The corresponding matrix * p of all cocircuits is:
0 1 0 0 1 0
0 0 1 0 0 1
0 0 0 1 1 1
1 1 0 0 p 1
1 0 1 0 1 0
0 1 1 1 0 0
For the LP capacity function k = 1, the minimum
cocircuit capacity is equal to 2. If we sum the
constraints yA < k, the result is 3(1 y) < 6,
yielding 1 y < 2. In order to have yA = k, the
solution must be y1 = y2 = V3 = Y4 = V2- it is
impossible to have an integral solution, hence F7 does
not have the strong MF/MC property.
The above example showing that F7 does not have
the strong MF/MC property combined with Lemma 4.4 shows
that no matroid with a F7 minor has the strong MF/MC
property. The following theorem due to Seymour (SY77)
characterizes exactly which matroids satisfy the strong
MF/MC property.


66
Theorem 4.8
A matroid M has the strong MF/MC property (with respect
to every choice of a distinguished element e.^ and
capacity function k(e)), if and only if M is binary and
*
has no F? minor.
The proof is difficult but may be found in
(SY77). Bixby however, gives the following sketch of a
constructive proof. In order to outline the proof we
need to present the definition of 2-separation, a lemma
and a theorem for binary matroids. The following lemma
can be found in (BX82).
Lemma 4.5
has the strong Max Flow-Min Cut property.
Let M= (E,C) be a matroid. A partition (E1,E }
of E is called a 2-SEPARATION of M if the following
properties are satisfied:
Property 4.7
|e1i ;> 2 £ | e2 |
Property 4.8
For every pair of circuits C2 G C such that:
C1 n Ei * $
C1 n E2 2 $
C2 n E1 2 $
C2 n E2 $


67
then, (D E1) U (C2 D E2) is a circuit of M.
Example 4.8 CBX82}
Let G be the given graph:
E^ = {a,b,c,d,e} and E2 = {remaining edges}. Since
|E^| £ 2, and IE2| £ 2, then Property 4.7 holds. It
can be verified that for every pair of circuits C.^, and
C2, that Property 4.8 holds. Therefore {{E1,E2}} defines
a 2-separation for the matroid M on the graph G.
Theorem 4.9
Let M be a binary matroid which has no F^ minor, then
either (a) M has no F7 minor, (b) M is 2-separable, or
(c) M = F?.
A proof for Theorem 4.9 can be found in
(SY77). We now outline the proof of Theorem 4.8.
Proof:
Let M be a binary matroid with no F? minor. By Theorem
3.9 the matroid M is either regular or has an F?
minor. If M is regular, then M has the strong MF/MC


68
property. Now assume that M has an F^ minor. If M is
2-separable, then the problem can be decomposed into
smaller problems, and there is a way to combine the
maximum flow and minimum cocircuits from the smaller
problems to the bigger problem. Otherwise, M = F^ which
we have noted does have the strong MF/MC property.B
Although Seymour proved that this larger class
of matroids does have the strong MF/MC property, there
is no known algorithm that determines how to augment
flow through such matroids.
We present the idea of a flow decomposition
before concluding the paper. Hamacher (HM83) showed
that the flow over a regular matroid could be decomposed
into separate flows over the circuits of the matroid.
We present a lemma, then a theorem for decomposing
matroid flows.
Lemma 4.5 CHM83^
Let f be a M-flow and let e* G E with f(e*) > 0. There
exists a circuit C G C+A satisfying the following
e
properties:


69
Property 4.9
C
c
+
Property 4.10
f(e) > 0, V e e C.
The proof of this lemma may be found in
Hamacher. The argument involves use of regularity
properties and employs the Painting Theorem.
Theorem 4.10 Decomposition Theorem (HM83)
Let f be an M-flow. Then there exists a function g
satisfying the following properties:
Property 4.11
g(C) > 0 => C = C
Property 4.12
fg(e) = l g(c) = f(e), V e E E.
C E C
e
The proof of this theorem is given by the
following algorithm due to Hamacher (HM83).
Decomposition Algorithm
Start: f' = f, g = 0.
STEP 1: If there exists an element e E E with f(e) >
ft
f (e), then define e = e and go to Step 2. Else:STOP,
y


70
STEP 2: Determine a circuit C E C+A with C = C+ and
e
f' (e) >0, V e E C.
STEP 3: Define g(C) = min f'(e) where e E C, as
follows:
f' (e) g(C) e E c.
f1 (e) =
f (e) e jZ C.
STEP 4 If f(e*) = f (e*), go to Step 1. Otherwise go
to Step 2.
Hamacher showed the validity of the algorithm
and that the algorithm stops after |E| iterations.
The algorithm works by decomposing the flow
through a matroid into separate flows over circuits.
The algorithm begins by letting g = 0, and assumes a
flow f. We set f' = f, and define e to be an e E E.
A circuit C is determined that contains element e and
g(C) is defined to be the smallest quantity f' of flow
over all elements in C. At this point, a new flow f'
is defined by subtracting g(C) from each e E C, and
leaving f1(e) unchanged for all other e E E. A check
is made to see if all flow over e has been accounted
Jf
for, i.e., is f'(e ) = 0? If flow is remaining on
element e then determine another circuit that
*
contains e a new g(C) and a new flow function f'(e).
If all the flow over e has been accounted for the
algorithm finds another element that has nonzero value


71
for f'(e), and repeats the process. The algorithm ends
when f'(e) =0, Ve G E. The decomposed flow can be
represented by listing each circuit used in the
algorithm, and assigning to each such circuit a flow
g(c).
Example 4.9
Let M = (E,C) be the matroid represented by the
following digraph.
Let the capacity function k(e) be given as:
k(a) = 5, k(d) = 2, k(g) = 2,
k(b) = 7, k(e) = 3, k(h) = 5,
k(c) = 4, k(f) = 4, k(ei) = 9.
START: g = 0, f' = f given as follows:
f 1 (a) CM II 'O f' (b) = 7, f(e) = 3, f' (h) = 5,
f' (c) = 4, f'(f) = 4, f' (-l) = 9.
STEP 1: f(a) * = 5 > 0, so let e = a.
STEP 2: Let C = (a^c^).
STEP 3: gtC^) = min f(e) = 4, where e G C. We


72
determine f'(e) now to be as follows:
f(a) = 1/ f'(d) = 2, f(g) = 2,
f'(b) = 3, f' (e) = 3, f 1 (h) = 5,
f'(c) = 0, f (f) = 4, . f(&1) = 5.
Since f (a) # f (a) g' 1 , go to Step 2.
At this point another circuit C2 = (a,b,e,h,e1) with
g(C2 ) = 1 is determined along with a new flow function
f'(e). We continue this process until f'(e) = 0 V e £
E. The algorithm continues and the following circuits
with corresponding g(C)'s are determined:
C^= (ftdi^/e,h,e^), 2,
C4= , g(c4) = 2.
We now have that f' (e)* =0, Ve £ E, so the flow over
the matroid has been completely decomposed into
circuits as follows:
Cl' with flow = 4;
C2' with flow = 1;
S' with flow = 2;
C4 ' with flow = 2.
Note that the sum of the flow over all decomposed
circuits is equal to the total flow over the matroid.
We conclude by noting that although the scope
of this paper dealt primarily with showing that it is
possible to generalize the ideas of network flow
problems to matroids, it may be possible to carry
further network flow concepts to matroids. One such


73
example is the possibility of using a matroid flow to
determine a maximum cardinality matroid intersection,
analogous to the application of network flows to
bipartite matching. It was hoped that we would be able
to produce such a result, but due to time constraints
this problem is left for future research.


BIBLIOGRAPHY
(BL78)
(BX82)
(CY57)
(ED72)
(EU36)
(FF62)
(HM80)
(HM83)
(HR69)
(KR47)
(LW76)
Bland, R. G., Las Vergnas, M. "Orientability
of Matroids" Journal of Combinatorial Theory,
B, Vol. 24, No. I, Feb. 1978
Bixby, R., Advanced Techniques in the
Practice of Operations Research.
Edited by: Greenberg, Murphy, Shaw
Elsevier Science Publishers
North Holland, NY (1982)
Cayley, A., "On the Theory of the Analytical
Forms Called Trees", Philosophy Magazine 13,
(1857) 172-176.
Edmonds, J. ; Karp., R.M. "Theoretical
Improvement in Algorithmic Efficiency for
Network Flow Problems", Journal of the ACM,
19, (1972), 248-264
Euler, L., "Solutio Problematis ad Geometriam
Situs Pertinentis", Comment. Acad. Sci. I.
Petropolitanae, 8 (1736), 128-140
Ford, L.; Fulkerson D., Flows in Networks.
Princeton University Press, (1962)
Hamacher, H., "Algebraic Flows in Regular
Matroids", Discrete Applied Math. 2,
(1980), 27-38
Hamacher, H., Flow in Regular Matroids
Konigstein/Ts: Hain; Cambridge, MA (1981)
Harrary, F., Graph Theory. Addison-Wesley,
Reading, Mass. (1969)
Kirchoff, G., "Uber die Auflosung der
Gleichungen, auf, welche man bei der
Untersuchung der linearen Verteilung
galvanischer Strome gefuhrt wird", Ann.
Phys. Chem., 72 (1847) 497-508
Lawler, E., Combinatorial Optimization.
Holt, Rinehart and Winston, New York (1976)


75
(MT66)
(PS82)
(RD42)
(RN87)
(RY87)
(RB84)
(ST80)
(SY77)
(SY80)
(TT58)
(TT59)
(TT71)
(WL76)
Minty, G. J., "On the Axiomatic Foundations
of the Theories of Directed Linear Graphs,
Electrical Networks and Network Programming",
Journal Math. Mech. 15 (1966) 246-300
Papadimitriou, C. H.; Steiglitz, K.,
Combinatorial Optimization: Algorithms and
Complexity. Prentice-Hall, Englwood Cliffs,
New Jersey (1982)
Rado, R., "A Theorem on Independence
Relations", Quarterly Journal of Math,
(Oxford) 13 (1942) 83-89
Ryan, J., Lecture Notes: Combinatorial
Optimization, Univ. of Colo. Denver, 1987
Ryan, J., Graph Theory Seminar Notes:
Matroids, Univ. of Colo. Denver, 1987
Roberts, F. S., Applied Combinatorics.
Prentice-Hall, Englewood Cliffs, NJ (1984)
Strang, G., Linear Aleaebra and it's
Applications. Academic Press, Inc.
Orlando, FL (1980)
Seymour, P., "The Matroids with the Max-Flow
Min-Cut Property", JCT (B) 23, (1977) 189-222
Seymour, P., "Decomposition of Regular
Matroids," JCT (B) 28, (1980) 305-359
Tutte, W. T., "A Homotopy Theorem for
Matroids I and II", Tran. Amer. Math. Soc.,
88 (1958) 144-174
Tutte, W. T., "Matroids and Graphs", Trans.
Amer. Math. Soc. 90 (1959) 527-552
Tutte, W. T., Introduction to the Theory
of Matroids. American Elsevier Publishing
Company, New York (1971)
Welsh, D.J.A., Matroid Theory. Academic
Press, New York, (1976)