Page 311 -

Section 9.4 Segmentation, Clustering, and Graphs 279

• Given a connected graph G = {V, E},a spanning tree is a tree with vertices V
and edges a subset of E. By our definition, trees are connected, so a spanning
tree is connected.
• Every graph consists of a disjoint set of connected components—that is, G =
{V 1 ∪ V 2 ...V n ,E 1 ∪ E 2 ... E n },where {V i ,E i } are all connected graphs and
there is no edge in E that connects an element of V i with one of V j for i = j.

• A forest is a graph whose connected components are trees.
In a weighted graph, there are efficient algorithms for computing minimum
weight spanning trees (see, for example, Jungnickel (1999) or Cormen et al. (2009)).
Another very important problem that can be solved efficiently seeks to maximize
flow in a directed graph. In particular, in a directed graph identify one vertex as a
source s and another as a target t. Associate with each directed edge e a capacity,
c(e), which is a non-negative number. A flow is a non-negative value f(e) associated
with each edge with the following properties. First, 0 ≤ f(e) ≤ c(e). Second, at
any vertex v ∈{V − s − t},

f(e) − f(e)= 0
earriving at v eleaving fromv
(i.e., all flow arriving at a vertex leaves it; this is Kirchoff’s law). The value of a
flow is

f(e).
earriving att
There are efficient algorithms to maximize the flow in, for example, Ahuja et al.
(1993) or Cormen et al. (2009). A dual problem is also interesting. Decompose the
vertices into two disjoint sets S and T , such that s ∈S and t ∈T . This represents
a cut.Consider W∈ E, the set of directed edges from S to T . The value of the
cut is

c(e).
e∈W
The value of the cut can again be minimized efficiently; algorithms appear in, for
example, Ahuja et al. (1993), Jungnickel (1999), or Schrijver (2003).

9.4.2 Agglomerative Clustering with a Graph

Felzenszwalb and Huttenlocher (2004) showed how to use graph theoretic ideas to
build a straightforward but very effective segmenter based around an agglomer-
ative clusterer. Represent the image as a weighted graph. There are edges be-
tween any pair of pixels that are neighbors. Each edge has a weight that measures
dissimilarity—i.e., weights are large if pixels are very different, and small if they
are similar. The weights could come from a variety of pixel representations. For
example, we could use the squared difference in intensity; we could represent the
color at each pixel with a vector, and use the length of the difference vector; we
could represent the texture at each pixel with a vector of filter outputs (after the