Citation |

- Permanent Link:
- http://digital.auraria.edu/AA00004937/00001
## Material Information- Title:
- Generalization of network flow theory to matroids
- Creator:
- Haskins, Irene Mae
- Publication Date:
- 1988
- 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 )
## Auraria Membership |

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 = (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 |