123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629 |
- <HTML>
- <!--
- Copyright (c) Jeremy Siek 2000
- Copyright (c) Daniel Trebbien 2010
-
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
- -->
- <Head>
- <Title>Boost Graph Library: Graph Theory Review</Title>
- <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
- <IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
- <BR Clear>
- <H1>Review of Elementary Graph Theory</H1>
- <P>
- <P>
- This chapter is meant as a refresher on elementary graph theory. If
- the reader has some previous acquaintance with graph algorithms, this
- chapter should be enough to get started. If the reader has no
- previous background in graph algorithms we suggest a more thorough
- introduction such as <a
- href="https://mitpress.mit.edu/algorithms">Introduction to Algorithms</a>
- by Cormen, Leiserson, and Rivest.
- <P>
- <H1>The Graph Abstraction</H1>
- <P>
- A graph is a mathematical abstraction that is useful for solving many
- kinds of problems. Fundamentally, a graph consists of a set of
- vertices, and a set of edges, where an edge is something that connects
- two vertices in the graph. More precisely, a <a
- name="def:graph"><I>graph</I></a> is a pair <i>(V,E)</i>, where
- <i>V</i> is a finite set and <i>E</i> is a binary relation on
- <i>V</i>. <i>V</i> is called a <a name="def:vertex-set"><I>vertex
- set</I></a> whose elements are called <I>vertices</I>. <i>E</i> is a
- collection of edges, where an <a name="def:edge"><I>edge</I></a> is a
- pair <i>(u,v)</i> with <i>u,v</i> in <i>V</i>. In a <a
- name="def:directed-graph"><I>directed graph</I></a>, edges are ordered
- pairs, connecting a <a name="def:source"><I>source</I></a> vertex to a
- <a name="def:target"><I>target</I></a> vertex. In an <a
- name="def:undirected-graph"><I>undirected graph</I></a> edges are
- unordered pairs and connect the two vertices in both directions, hence
- in an undirected graph <i>(u,v)</i> and <i>(v,u)</i> are two ways of
- writing the same edge.
- <P>
- This definition of a graph is vague in certain respects; it does not
- say what a vertex or edge represents. They could be cities with
- connecting roads, or web-pages with hyperlinks. These details are left
- out of the definition of a graph for an important reason; they are not
- a necessary part of the graph <I>abstraction</I>. By leaving out the
- details we can construct a theory that is reusable, that can help us
- solve lots of different kinds of problems.
- <P>
- Back to the definition: a graph is a set of vertices and edges. For
- purposes of demonstration, let us consider a graph where we have
- labeled the vertices with letters, and we write an edge simply as a
- pair of letters. Now we can write down an example of a directed graph
- as follows:
- <P>
- <BR>
- <DIV ALIGN="center">
- <table><tr><td><tt>
- V = {v, b, x, z, a, y } <br>
- E = { (b,y), (b,y), (y,v), (z,a), (x,x), (b,x), (x,v), (a,z) } <br>
- G = (V, E)
- </tt></td></tr></table>
- </DIV>
- <BR CLEAR="ALL"><P></P>
- <P>
- <A HREF="#fig:directed-graph">Figure 1</A> gives a pictorial view of
- this graph. The edge <i>(x,x)</i> is called a <a
- name="def:self-loop"><I>self-loop</I></a>. Edges <i>(b,y)</i> and
- <i>(b,y)</i> are <I>parallel edges</I>, which are allowed in a <a
- name="def:multigraph"><I>multigraph</I></a> (but are normally not
- allowed in a directed or undirected graph).
- <P>
- <P></P>
- <DIV ALIGN="center"><A NAME="fig:directed-graph"></A>
- <TABLE>
- <CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG>
- Example of a directed graph.</CAPTION>
- <TR><TD><IMG SRC="./figs/digraph.gif" width="124" height="163"></TD></TR>
- </TABLE>
- </DIV><P></P>
- <P>
- Next we have a similar graph, though this time it is undirected. <A
- HREF="#fig:undirected-graph">Figure 2</A> gives the pictorial view.
- Self loops are not allowed in undirected graphs. This graph is the <a
- name="def:undirected-version"><I>undirected version</i></a. of the the
- previous graph (minus the parallel edge <i>(b,y)</i>), meaning it has
- the same vertices and the same edges with their directions removed.
- Also the self edge has been removed, and edges such as <i>(a,z)</i>
- and <i>(z,a)</i> are collapsed into one edge. One can go the other
- way, and make a <a name="def:directed-version"><I>directed version</i>
- of an undirected graph be replacing each edge by two edges, one
- pointing in each direction.
- <P>
- <BR>
- <DIV ALIGN="CENTER">
- <table><tr><td><tt>
- V = {v, b, x, z, a, y }<br>
- E = { (b,y), (y,v), (z,a), (b,x), (x,v) }<br>
- G = (V, E)
- </tt></td></tr></table>
- </DIV>
- <BR CLEAR="ALL"><P></P>
- <P>
- <P></P>
- <DIV ALIGN="CENTER"><A NAME="fig:undirected-graph"></A><A NAME="1524"></A>
- <TABLE>
- <CAPTION ALIGN="BOTTOM"><STRONG>Figure 2:</STRONG>
- Example of an undirected graph.</CAPTION>
- <TR><TD><IMG SRC="./figs/undigraph.gif" width="103" height="163"></TD></TR>
- </TABLE>
- </DIV><P></P>
- <P>
- Now for some more graph terminology. If some edge <i>(u,v)</i> is in
- graph , then vertex <i>v</i> is <a
- name="def:adjacent"><I>adjacent</I></a> to vertex <i>u</i>. In a
- directed graph, edge <i>(u,v)</i> is an <a
- name="def:out-edge"><I>out-edge</I></a> of vertex <i>u</i> and an <a
- name="def:in-edge"><I>in-edge</I></a> of vertex <i>v</i>. In an
- undirected graph edge <i>(u,v)</i> is <a
- name="def:incident-on"><I>incident on</I></a> vertices <i>u</i> and
- <i>v</i>.
- <P>
- In <A HREF="#fig:directed-graph">Figure 1</A>,
- vertex <i>y</i> is adjacent to vertex <i>b</i> (but <i>b</i> is not
- adjacent to <i>y</i>). The edge <i>(b,y)</i> is an out-edge of
- <i>b</i> and an in-edge of <i>y</i>. In <A
- HREF="#fig:undirected-graph">Figure 2</A>,
- <i>y</i> is adjacent to <i>b</i> and vice-versa. The edge
- <i>(y,b)</i> is incident on vertices <i>y</i> and <i>b</i>.
- <P>
- In a directed graph, the number of out-edges of a vertex is its <a
- name="def:out-degree"><I>out-degree</I></a> and the number of in-edges
- is its <a name="def:in-degree"><I>in-degree</I></a>. For an
- undirected graph, the number of edges incident to a vertex is its <a
- name="def:degree"><I>degree</I></a>. In <A
- HREF="#fig:directed-graph">Figure 1</A>, vertex <i>b</i> has an
- out-degree of 3 and an in-degree of zero. In <A
- HREF="#fig:undirected-graph">Figure 2</A>, vertex <i>b</i> simply has
- a degree of 2.
- <P>
- Now a <a name="def:path"><i>path</i></a> is a sequence of edges in a
- graph such that the target vertex of each edge is the source vertex of
- the next edge in the sequence. If there is a path starting at vertex
- <i>u</i> and ending at vertex <i>v</i> we say that <i>v</i> is <a
- name="def:reachable"><i>reachable</i></a> from <i>u</i>. A path is <a
- name="def:simple-path"><I>simple</I></a> if none of the vertices in
- the sequence are repeated. The path <(b,x), (x,v)> is simple,
- while the path <(a,z), (z,a)> is not. Also, the path <(a,z),
- (z,a)> is called a <a name="def:cycle"><I>cycle</I></a> because the
- first and last vertex in the path are the same. A graph with no cycles
- is <a name="def:acyclic"><I>acyclic</I></a>.
- <P>
- A <a name="def:planar-graph"><I>planar graph</I></a> is a graph that
- can be drawn on a plane without any of the edges crossing over each
- other. Such a drawing is called a <I>plane graph</I>. A <a
- name="def:face"><I>face</I></a> of a plane graph is a connected region
- of the plane surrounded by edges. An important property of planar
- graphs is that the number of faces, edges, and vertices are related
- through Euler's formula: <i>|F| - |E| + |V| = 2</i>. This means that a
- simple planar graph has at most <i>O(|V|)</i> edges.
- <P>
- <P>
- <H1>Graph Data Structures</H1>
- <P>
- The primary property of a graph to consider when deciding which data
- structure to use is <I>sparsity</I>, the number of edges relative to
- the number of vertices in the graph. A graph where <i>E</i> is close
- to </i>V<sup>2</sup></i> is a <I>dense</I> graph, whereas a graph
- where <i>E = alpha V</i> and <i>alpha</i> is much smaller than
- <i>V</i> is a <I>sparse</I> graph. For dense graphs, the
- <I>adjacency-matrix representation</I> is usually the best choice,
- whereas for sparse graphs the <I>adjacency-list representation</I> is
- a better choice. Also the <I>edge-list representation</I> is a space
- efficient choice for sparse graphs that is appropriate in some
- situations.
- <P>
- <H2>Adjacency Matrix Representation</H2>
- <P>
- An adjacency-matrix representation of a graph is a 2-dimensional <i>V
- x V</i> array. Each element in the array <i>a<sub>uv</sub></i> stores
- a Boolean value saying whether the edge <i>(u,v)</i> is in the graph.
- <A HREF="#fig:adj-matrix">Figure 3</A> depicts an adjacency matrix for
- the graph in <A HREF="#fig:directed-graph">Figure 1</A> (minus the
- parallel edge <i>(b,y)</i>). The amount of space required to store
- an adjacency-matrix is <i>O(V<sup>2</sup>)</i>. Any edge can be
- accessed, added, or removed in <i>O(1)</i> time. To add or remove a
- vertex requires reallocating and copying the whole graph, an
- <i>O(V<sup>2</sup>)</i> operation. The <a
- href="./adjacency_matrix.html"><tt>adjacency_matrix</tt></a> class
- implements the BGL graph interface in terms of the adjacency-matrix
- data-structure.
- <P>
- <P></P>
- <DIV ALIGN="CENTER"><A NAME="fig:adj-matrix"></A><A NAME="1701"></A>
- <TABLE>
- <CAPTION ALIGN="BOTTOM"><STRONG>Figure 3:</STRONG>
- The Adjacency Matrix Graph Representation.</CAPTION>
- <TR><TD><IMG SRC="./figs/adj_matrix.gif" width="136" height="135"></TD></TR>
- </TABLE>
- </DIV><P></P>
- <P>
- <H2><A NAME="sec:adjacency-list-representation"></A>
- Adjacency List Representation
- </H2>
- <P>
- An adjacency-list representation of a graph stores an out-edge
- sequence for each vertex. For sparse graphs this saves space since
- only <i>O(V + E)</i> memory is required. In addition, the out-edges
- for each vertex can be accessed more efficiently. Edge insertion is
- <i>O(1)</i>, though accessing any given edge is <i>O(alpha)</i>, where
- <i>alpha</i> is the sparsity factor of the matrix (which is equal to
- the maximum number of out-edges for any vertex in the graph). <A
- HREF="#fig:adj-list">Figure 4</A> depicts an
- adjacency-list representation of the graph in <A
- HREF="#fig:directed-graph">Figure 1</A>. The
- <a href="./adjacency_list.html"><TT>adjacency_list</TT></a> class is
- an implementation of the adjacency-list representation.
- <P>
- <P></P>
- <DIV ALIGN="CENTER"><A NAME="fig:adj-list"></A><A NAME="1713"></A>
- <TABLE>
- <CAPTION ALIGN="BOTTOM"><STRONG>Figure 4:</STRONG>
- The Adjacency List Graph Representation.</CAPTION>
- <TR><TD><IMG SRC="./figs/adj_list.gif" width="108" height="122"></TD></TR>
- </TABLE>
- </DIV><P></P>
- <P>
- <H2>Edge List Representation</H2>
- <P>
- An edge-list representation of a graph is simply a sequence of edges,
- where each edge is represented as a pair of vertex ID's. The memory
- required is only <i>O(E)</i>. Edge insertion is typically <i>O(1)</i>,
- though accessing a particular edge is <i>O(E)</i> (not efficient). <A
- HREF="#fig:edge-list">Figure 5</A> shows an
- edge-list representation of the graph in <A
- HREF="#fig:directed-graph">Figure 1</A>. The
- <a href="./edge_list.html"><TT>edge_list</TT></a> adaptor class can be
- used to create implementations of the edge-list representation.
- <P>
- <P></P>
- <DIV ALIGN="CENTER"><A NAME="fig:edge-list"></A><A NAME="1724"></A>
- <TABLE>
- <CAPTION ALIGN="BOTTOM"><STRONG>Figure 5:</STRONG>
- The Edge List Graph Representation.</CAPTION>
- <TR><TD><IMG SRC="./figs/edge_list.gif" width="322" height="22"></TD></TR>
- </TABLE>
- </DIV><P></P>
- <P>
- <H1>Graph Algorithms</H1>
- <P>
- <H2>Graph Search Algorithms</H2>
- <P>
- <I>Tree edges</I> are edges in the search tree (or forest) constructed
- (implicitly or explicitly) by running a graph search algorithm over a
- graph. An edge <i>(u,v)</i> is a tree edge if <i>v</i> was first
- discovered while exploring (corresponding to the <a
- href="./visitor_concepts.html">visitor</a> <TT>explore()</TT> method)
- edge <i>(u,v)</i>. <I>Back edges</I> connect vertices to their
- ancestors in a search tree. So for edge <i>(u,v)</i> the vertex
- <i>v</i> must be the ancestor of vertex <i>u</i>. Self loops are
- considered to be back edges. <I>Forward edges</I> are non-tree edges
- <i>(u,v)</i> that connect a vertex <i>u</i> to a descendant <i>v</i>
- in a search tree. <I>Cross edges</I> are edges that do not fall into
- the above three categories.
- <P>
- <H2><A NAME="sec:bfs-algorithm"></A>
- Breadth-First Search
- </H2>
- <P>
- Breadth-first search is a traversal through a graph that touches all
- of the vertices reachable from a particular source vertex. In
- addition, the order of the traversal is such that the algorithm will
- explore all of the neighbors of a vertex before proceeding on to the
- neighbors of its neighbors. One way to think of breadth-first search
- is that it expands like a wave emanating from a stone dropped into a
- pool of water. Vertices in the same ``wave'' are the same distance
- from the source vertex. A vertex is <I>discovered</I> the first time
- it is encountered by the algorithm. A vertex is <I>finished</I> after
- all of its neighbors are explored. Here's an example to help make this
- clear. A graph is shown in <A
- HREF="#fig:bfs-example">Figure 6</A> and the
- BFS discovery and finish order for the vertices is shown below.
- <P>
- <P></P>
- <DIV ALIGN="CENTER"><A NAME="fig:bfs-example"></A><A NAME="1826"></A>
- <TABLE>
- <CAPTION ALIGN="BOTTOM"><STRONG>Figure 6:</STRONG>
- Breadth-first search spreading through a graph.</CAPTION>
- <TR><TD><IMG SRC="./figs/bfs_example.gif" width="242" height="143"></TD></TR>
- </TABLE>
- </DIV><P></P>
- <P>
- <PRE>
- order of discovery: s r w v t x u y
- order of finish: s r w v t x u y
- </PRE>
- <P>
- We start at vertex <i>s</i>, and first visit <i>r</i> and <i>w</i> (the two
- neighbors of <i>s</i>). Once both neighbors of are visited, we visit the
- neighbor of <i>r</i> (vertex <i>v</i>), then the neighbors of <i>w</i>
- (the discovery order between <i>r</i> and <i>w</i> does not matter)
- which are <i>t</i> and <i>x</i>. Finally we visit the neighbors of
- <i>t</i> and <i>x</i>, which are <i>u</i> and <i>y</i>.
- <P>
- For the algorithm to keep track of where it is in the graph, and which
- vertex to visit next, BFS needs to color the vertices (see the section
- on <a href="./using_property_maps.html">Property Maps</a>
- for more details about attaching properties to graphs). The place to
- put the color can either be inside the graph, or it can be passed into
- the algorithm as an argument.
- <P>
- <H2><A NAME="sec:dfs-algorithm"></A>
- Depth-First Search
- </H2>
- <P>
- A depth first search (DFS) visits all the vertices in a graph. When
- choosing which edge to explore next, this algorithm always chooses to
- go ``deeper'' into the graph. That is, it will pick the next adjacent
- unvisited vertex until reaching a vertex that has no unvisited
- adjacent vertices. The algorithm will then backtrack to the previous
- vertex and continue along any as-yet unexplored edges from that
- vertex. After DFS has visited all the reachable vertices from a
- particular source vertex, it chooses one of the remaining undiscovered
- vertices and continues the search. This process creates a set of
- <I>depth-first trees</I> which together form the <I>depth-first
- forest</I>. A depth-first search categorizes the edges in the graph
- into three categories: tree-edges, back-edges, and forward or
- cross-edges (it does not specify which). There are typically many
- valid depth-first forests for a given graph, and therefore many
- different (and equally valid) ways to categorize the edges.
- <P>
- One interesting property of depth-first search is that the discover
- and finish times for each vertex form a parenthesis structure. If we
- use an open-parenthesis when a vertex is discovered, and a
- close-parenthesis when a vertex is finished, then the result is a
- properly nested set of parenthesis. <A
- HREF="#fig:dfs-example">Figure 7</A> shows
- DFS applied to an undirected graph, with the edges labeled in the
- order they were explored. Below we list the vertices of the graph
- ordered by discover and finish time, as well as show the parenthesis structure. DFS is used as the kernel for several other graph
- algorithms, including topological sort and two of the connected
- component algorithms. It can also be used to detect cycles (see the <A
- HREF="file_dependency_example.html#sec:cycles">Cylic Dependencies </a>
- section of the File Dependency Example).
- <P>
- <P></P>
- <DIV ALIGN="CENTER"><A NAME="fig:dfs-example"></A><A NAME="1841"></A>
- <TABLE>
- <CAPTION ALIGN="BOTTOM"><STRONG>Figure 7:</STRONG>
- Depth-first search on an undirected graph.</CAPTION>
- <TR><TD><IMG SRC="./figs/dfs.gif" width="141" height="204"></TD></TR>
- </TABLE>
- </DIV><P></P>
- <P>
- <PRE>
- order of discovery: a b e d c f g h i
- order of finish: d f c e b a
- parenthesis: (a (b (e (d d) (c (f f) c) e) b) a) (g (h (i i) h) g)
- </PRE>
- <P>
- <H2><a name="sec:minimum-spanning-tree">Minimum Spanning Tree Problem</a></H2>
- <P>
- The <I>minimum-spanning-tree problem</I> is defined as follows: find
- an acyclic subset <i>T</i> of <i>E</i> that connects all of the vertices
- in the graph and whose total weight is minimized, where the
- total weight is given by
- <P></P>
- <DIV ALIGN="left">
- <i>w(T)</i> = sum of <i>w(u,v)</i> over all <i>(u,v)</i> in <i>T</i>,
- where <i>w(u,v)</i> is the weight on the edge <i>(u,v)</i>
- </DIV>
- <BR CLEAR="ALL">
- <P></P>
- <i>T</i> is called the <I>spanning tree</I>.
- <!--
- <P>
- Kruskal's algorithm [<A
- HREF="bibliography.html#kruskal56">18</A>]
- for solving the minimum spanning tree problem. This is a greedy
- algorithm to calculate the minimum spanning tree for an undirected
- graph with weighted edges.
- <P>
- This is Prim's algorithm [<A
- HREF="bibliography.html#prim57:_short">25</A>] for solving the
- minimum spanning tree problem for an undirected graph with weighted
- edges. The implementation is simply a call to <a
- href="./dijkstra_shortest_paths.html"><TT>dijkstra_shortest_paths()</TT></a>
- with the appropriate choice of comparison and combine functors.
- -->
- <P>
- <H2><a name="sec:shortest-paths-algorithms">Shortest-Paths Algorithms</a></H2>
- <P>
- One of the classic problems in graph theory is to find the shortest
- path between two vertices in a graph. Formally, a <I>path</I> is a
- sequence of vertices <i><v<sub>0</sub>,v<sub>1</sub>,...,v<sub>k</sub>></i>
- in a graph <i>G = (V, E)</i> such that each vertex is connected to the
- next vertex in the sequence (the edges
- <i>(v<sub>i</sub>,v<sub>i+1</sub>)</i> for <i>i=0,1,...,k-1</i> are in
- the edge set <i>E</i>). In the shortest-path problem, each edge is
- given a real-valued weight. We can therefore talk about the <I>weight
- of a path</I><BR>
- <p></p>
- <DIV ALIGN="left">
- <i>w(p) = sum from i=1..k of w(v<sub>i-1</sub>,v<sub>i</sub>)</i>
- </DIV>
- <BR CLEAR="ALL"><P></P>
- The <I>shortest path weight</I> from vertex <i>u</i> to <i>v</i> is then
- <BR>
- <p></p>
- <DIV ALIGN="left">
- <i>delta (u,v) = min { w(p) : u --> v }</i> if there is a path from
- <i>u</i> to <i>v</i> <br>
- <i>delta (u,v) = infinity</i> otherwise.
- </DIV>
- <BR CLEAR="ALL"><P></P>
- A <I>shortest path</I> is any path who's path weight is equal to the
- <I>shortest path weight</I>.
- <P>
- There are several variants of the shortest path problem. Above we
- defined the <I>single-pair</I> problem, but there is also the
- <I>single-source problem</I> (all shortest paths from one vertex to
- every other vertex in the graph), the equivalent
- <I>single-destination problem</I>, and the <I>all-pairs problem</I>.
- It turns out that there are no algorithms for solving the single-pair
- problem that are asymptotically faster than algorithms that solve the
- single-source problem.
- <P>
- A <I>shortest-paths tree</I> rooted at vertex in graph <i>G=(V,E)</i>
- is a directed subgraph <G'> where <i>V'</i> is a subset
- of <i>V</i> and <i>E'</i> is a subset of <i>E</i>, <i>V'</i> is the
- set of vertices reachable from , <i>G'</i> forms a rooted tree with
- root , and for all <i>v</i> in <i>V'</i> the unique simple path from
- to <i>v</i> in <i>G'</i> is a shortest path from to <i>v</i> in . The
- result of a single-source algorithm is a shortest-paths tree.
- <P>
- <H2><a name="sec:network-flow-algorithms">Network Flow Algorithms</H2>
- <p>
- A flow network is a directed graph <i>G=(V,E)</i> with a
- <b><i>source</i></b> vertex <i>s</i> and a <b><i>sink</i></b> vertex
- <i>t</i>. Each edge has a positive real valued <b><i>capacity</i></b>
- function <i>c</i> and there is a <b><i>flow</i></b> function <i>f</i>
- defined over every vertex pair. The flow function must satisfy three
- constraints:
- <p>
- <i>f(u,v) <= c(u,v) for all (u,v) in V x V</i> (Capacity constraint) <br>
- <i>f(u,v) = - f(v,u) for all (u,v) in V x V</i> (Skew symmetry)<br>
- <i>sum<sub>v in V</sub> f(u,v) = 0 for all u in V - {s,t}</i> (Flow conservation)
- <p>
- The <b><i>flow</i></b> of the network is the net flow entering the
- sink vertex <i>t</i> (which is equal to the net flow leaving the
- source vertex <i>s</i>).<p>
- <i>|f| = sum<sub>u in V</sub> f(u,t) = sum<sub>v in V</sub> f(s,v)</i>
- <p>
- The <b><i>residual capacity</i></b> of an edge is <i>r(u,v) = c(u,v) -
- f(u,v)</i>. The edges with <i>r(u,v) > 0</i> are residual edges
- <i>E<sub>f</sub></i> which induce the residual graph <i>G<sub>f</sub>
- = (V, E<sub>f</sub>)</i>. An edge with <i>r(u,v) = 0</i> is
- <b><i>saturated</i></b>.
- <p>
- The <b><i>maximum flow problem</i></b> is to determine the maximum
- possible value for <i>|f|</i> and the corresponding flow values for
- every vertex pair in the graph.
- <p>
- The <b><i>minimum cost maximum flow problem</i></b> is to determine the maximum flow which minimizes <i> sum<sub>(u,v) in E</sub>
- cost(u,v) * f(u,v) </i>.
- <p>
- A flow network is shown in <a href="#fig:max-flow">Figure
- 8</a>. Vertex <i>A</i> is the source vertex and <i>H</i> is the target
- vertex.
- <P></P>
- <DIV ALIGN="center"><A NAME="fig:max-flow"></A>
- <TABLE>
- <CAPTION ALIGN="BOTTOM"><STRONG>Figure 8:</STRONG> A Maximum Flow
- Network.<br> Edges are labeled with the flow and capacity
- values.</CAPTION>
- <TR><TD><IMG SRC="./figs/max-flow.gif" width="578" height="240"></TD></TR>
- </TABLE>
- </DIV><P></P>
- <p>
- There is a long history of algorithms for solving the maximum flow
- problem, with the first algorithm due to <a
- href="./bibliography.html#ford56:_maxim">Ford and Fulkerson</a>. The
- best general purpose algorithm to date is the push-relabel algorithm
- of <a
- href="./bibliography.html#goldberg85:_new_max_flow_algor">Goldberg</a>
- which is based on the notion of a <b><i>preflow</i></b> introduced by
- <a href="./bibliography.html#karzanov74:_deter">Karzanov</a>.
- <h2><a name="sec:min-cut-algorithms">Minimum Cut Algorithms</a></h2>
- <h3>Undirected Graphs</h3>
- <p>Given an undirected graph <i>G</i> = (<i>V</i>, <i>E</i>), a <em>cut</em> of <i>G</i> is a partition of the vertices into two, non-empty sets <i>X</i> and <img src="stoer_wagner_imgs/6e4.gif" alt="\overline{X} = V - X" style="vertical-align: middle; padding-bottom: 2px">. The <i>weight</i> of a cut is defined as the number of edges between sets <i>X</i> and <img src="stoer_wagner_imgs/f79.gif" alt="\overline{X}" style="vertical-align: middle; padding-bottom: 3px"> if <i>G</i> is unweighted, or the sum of the weights of all edges between sets <i>X</i> and <img src="stoer_wagner_imgs/f79.gif" alt="\overline{X}" style="vertical-align: middle; padding-bottom: 3px"> if <i>G</i> is weighted (each edge has an associated, non-negative weight).
- <p>When the weight of a cut <img src="stoer_wagner_imgs/8b7.gif" alt="C = \{X, \overline{X}\}" style="vertical-align: middle"> is minimal for a graph <i>G</i> (that is, no other cut of <i>G</i> has a lesser weight), then the cut is known as a <em>minimum cut</em> or a <em>min-cut</em>. For example, given this weighted graph:
- <p><a href="stoer_wagner_imgs/stoer_wagner-example.dot"><img src="stoer_wagner_imgs/stoer_wagner-example.gif"></a>
- <p>The cut {{0, 6}, {3, 2, 7, 1, 5, 4}} has weight 13:
- <p><a href="stoer_wagner_imgs/stoer_wagner-example-c1.dot"><img src="stoer_wagner_imgs/stoer_wagner-example-c1.gif"></a>
- <p>And the min-cut is {{0, 1, 4, 5}, {2, 3, 6, 7}} (weight 4):
- <p><a href="stoer_wagner_imgs/stoer_wagner-example-min-cut.dot"><img src="stoer_wagner_imgs/stoer_wagner-example-min-cut.gif"></a>
- <p>Unlike this example, a graph will sometimes have multiple min-cuts, all of equal weight. A minimum cut algorithm determines one of them as well as the min-cut weight.
- <h3>Directed Graphs</h3>
- <p>Given a directed graph <i>G</i> = (<i>V</i>, <i>E</i>), a <em>cut</em> of <i>G</i> is a partition of the vertices into two, non-empty sets <i>S</i> and <i>T</i> where <i>S</i> is known as the set of <em>source vertices</em> and <i>T</i> is known as the set of <em>sink vertices</em>. The <em>capacity</em> of a cut <i>C</i> = (<i>S</i>, <i>T</i>) is the number of edges from a vertex in <i>S</i> to a vertex in <i>T</i> if <i>G</i> is unweighted, or the sum of weights of edges from a vertex in <i>S</i> to a vertex in <i>T</i> if <i>G</i> is weighted.
- <p>When the capacity of a cut <i>C</i> = (<i>S</i>, <i>T</i>) of a directed graph is minimal (that is, no other cut of <i>G</i> has lesser capacity), then <i>C</i> is known as a <em>minimum cut</em> or <em>min-cut</em>.
- <p>For example, given this directed graph:
- <p><a href="stoer_wagner_imgs/digraph1.dot"><img src="stoer_wagner_imgs/digraph1.gif"></a>
- <p>A min-cut is:
- <p><a href="stoer_wagner_imgs/digraph1-min-cut.dot"><img src="stoer_wagner_imgs/digraph1-min-cut.gif"></a>
- <p>where <i>S</i> = {0}, <i>T</i> = {1, 2, 3}, and the min-cut capacity is 1.
- <br>
- <HR>
- <TABLE>
- <TR valign=top>
- <TD nowrap>Copyright © 2000-2001</TD><TD>
- <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|