So in this set of lectures we'll be
discussing the minimum cut problem in
graphs and we'll be discussing the
randomized contraction algorithm. A
randomized algorithm is just so simple and
elegant, it's almost impossible to believe
that it could possibly work, but that's
exactly what we'll be proving. So one way
you can think about this set of lectures
is as a segue of sorts between our
discussion of randomization and our
discussion of graphs. So we just finished
talking about randomization in the context
of sorting and searching. We'll pick it up
again towards the end of the class when we
discuss hashing, but while we're in the
middle of randomization probability
review, I want to give you another
application of randomization in a totally
different domain. In particular to the
domain of graphs rather than to Sorting
and searching. So that's one high-level
goal of these lectures. A second one is
we'll get our feet wet talking about
graphs. And a lot of the next couple
weeks, that's what we're gonna be talking
about: fundamental graph primitives. So
this will give us an excuse to start
warming up with the vocabulary, some of
the basic concepts of the graph, and what
a graph algorithm looks like. Another
perk, although it's not one of the main
goals, but I wanna do, I do wanna point
out this fact. Is that, at least, compared
to most of the stuff that we're discussing
in this class, this is a relatively recent
algorithm, the contraction algorithm. By
relatively recent, I mean, okay, it's
twenty years old. Well at least that means
most of us, I know not all of us, but most
of us at least were born at the time that
this algorithm was invented. And so just
one quick digression. You know, in the
intro course like this most of what we're
gonna cover will be oldies but goodies, so
from as much as 50 years ago. And while
it's kind of amazing given how much the
world and how much technology has changed
over the past 50 years that idea in
computer science from that long ago is
still useful, they are. Okay. So it's just
sort of an amazing thing about the stuff
that the first generation of computer
scientists figured out. Okay. It's still;
it's still relevant to this day. That.
Said, algorithm is still a vibrant field
with lots of open questions and when I
have an opportunity I'll try and give you
glimpses of that fact. So I do wanna point
out here that this is somewhat more reason
algorithms that most of the other ones
will see which dates back to the 90s. So
let's talk about graphs. Fundamentally,
what a graph does is represent pair wise
relationships amongst a set of objects. So
as such, a graph is going to have two
ingredients. So first of all there's the
objects that you're talking about and
these have two very common names and
you're just gonna have to know both of the
names even though they're completely
synonymous. The first name is vertices.
[sound] So vertex is the singular,
vertices is the plural. Also known
interchangeably as nodes. I'll be using
the notation, capital V for the set of, of
vertices. So those are the objects. Now,
we wanna represent pair wise
relationships. So these pairs are gonna be
called edges. It'll be noted by denuded by
capital E and there's two flavors of
graphs and both are really important, both
come up all the time in application. So
you should be aware of both kinds. So
there is undirected graphs and directed
graphs and that just depends on whether
the edges themselves are undirected or
directed. So edges can be undirected by
which I mean this pair is unordered. There
are just two verses of edge. The two n
points say U and V and you don't
distinguish one as the first and one as
the second. Or edges can be directed, in
which case you have a directed graph and
here a pair is ordered. So you do have a
notion of a first vertex or a first end
point and the second vertex or second end
point of an edge. Those are often called
the tail and the head, respectively. And
once in a while although I'll, I'll try to
use, I'll not use this terminology, you
hear directed edges called arcs. Now I
think all of this is much clearer if I
just draw some pictures indeed one used to
call graphs dots and lines, the dots would
refer to the vertices. So here's four dots
or four vertices. And, the edges would be
lines. So the way you denote one of these
edges, is, you just draw a line between
the two, end points of that edge, the two
vertices that it corresponds to. So this
is an undirected graph with four vertices
and five edges. We could equally well have
a directed version of this graph. So
let's, still have four vertices and five
edges. But to indicate that this is a
directed graph, and that each edge has a
first vertex and a second vertex, we're
gonna add arrows to the lines. So the
arrow points to the second vertex, or to
the head of the, of the edge. So the first
vertex is often called the [inaudible] of
the edge. So, graphs are completely
fundamental. They show up not just in
computer science but in all kinds of
different disciplines social sciences and,
and biology being two prominent ones. So,
let me just mention a couple of reasons
you might use them just off the top of my
head. But literally there's hundreds or
thousands of others. So, a very literal
example would be road networks. So,
imagine you type in asking for driving
directions from point A to point B and
some web application or software or
whatever computes a, a road, a route for
you. What it's doing is it's manipulating
some representation of a road network,
which inevitably is going to be stored as
a graph, where the vertices correspond to
intersections, and the edges correspond to
individual roads. The web Is often
fruitfully thought of as a graph, a
directed graph. So here the vertices are
the individual web pages and edges
correspond to hyperlinks. So the first
vertex of an edge, the tail, is going to
be the page that contains the hyperlink.
The second vertex or the head of the edge
is going to be what the hyperlink points
to. So that's the web as a directed graph.
Social networks are, quite naturally,
represented as graphs. So here, the
vertices correspond to the individuals. In
the social network and the edges
corresponds to relationships, say
friendship links. I encourage to think
about amongst the popular social networks
these days, which ones are undirected
graphs and which ones are directed graphs.
We have some interesting examples of each
of those. And often graphs are useful even
when there isn't such an obvious network
structure. So, just to mention one example
let me just write down precedents
constraints. So, to say what I mean you
might think about you know, say you're a
freshman in college and you're looking at
your, your major is [inaudible] a computer
science major. Now, you wanna know what
courses to take in what order. And you
could think the following graph, where
each of the courses in your major
corresponds to a vertex and you draw a
directed edge from one, from course A to
course B, if course A is a prerequisite
for course B, that is, it has to be
completed before you begin course B. 'Kay,
so that's a way to represent dependencies.
Sort of, a temporal ordering between pairs
of, pairs of objects. Using a directed
graph. So that's the basic language of
graphs. Let me now talk about cuts in
graphs, cuz again this set of lectures is
gonna be about the so-called minimum cut
problem. So the definition of a cut of a
graph is very simple. It's just a
grouping, a partition, of the vertices of
the graph, into two groups, A and B. And
both of those two groups should be
non-empty. So to describe this in
pictures, let me give you a cartoon of a
cut in both the undirected and directed
cases. So for an undirected graph, you can
imagine drawing your two sets A and B. And
once you've defined the two sets, A and B,
the edges then fall into one of three
categories. You've got edges with both of
the end points in A. You've got edges with
both of the end points in B. And then
you've got edges with one end point in A,
and one endpoint in B. So that's
generically what the picture graph looks
like viewed through the lens of a
particular cut AB. The picture for
directed graphs is similar, you would
again have an A, and you'd again have a B,
you have directed edges with both end
points in A, directed edges with both end
points in B. And now you have actually two
further categories. So, you have edges who
cross the cut from left to right, that is,
whose tail vertex is in a, and whose head
vertex in b. And you can also have edges
which cross the cut in the opposite
direction that is their tail is in b and
their head is in a. Usually when we talk
about cuts we're gonna be concerned with
how many edges cross a given cut. And by
that I mean the following the crossing
edges of a cut a, b. Are those that
satisfy the following property. So in the
[inaudible] case it's exactly what you
think it would be. One of the endpoints is
in A, the other endpoint is in B, that's
what it means to cross the cut. Now in the
directed case there's a number of
reasonable definitions you could propose
about which edges cross the cut. Typically
and in this course we're going to focus on
the case were we only think about edges
that cross the cut from the left to the
right. And we ignore edges that cross from
the right to the left. So that is the
edges that cross the cut are those with
tail in A and head in B. So referring to
our two pictures, our two cartoons of
cuts, for the undirected one, all three of
these blue edges would be edges crossing
the cut AB, cuz they're the ones that have
one end point on the left side, and one
end point on the right side. Now for the
directed one, we only have two crossing
edges. So the two that cross from left to
right, with tail in A and head in B. The
one that's crossing backward does not
contribute. We don't count it as a
crossing edge of the cut. So the next quiz
is just a sanity check that you've
absorbed the definition of a cut of a
graph. Right, so the answer to this quiz
is the third option. Recall what is the
definition of a cut? It's just the way the
group, the vertices into two sets A and B
both should also be non-empty. So we have
N vertices and essentially we have one
binary degree of freedom for each. For
each vertex we can decide whether or not
it goes in set A or goes in set B. So two
choices for each of the N vertices. That
gives us a two to the N possible choices.
Two to the N possible cuts overall. Now
that's slightly incorrect because recall
that a cut can't have a non-empty set A or
a non-empty set B. So those are two of the
two to the N options which were
disallowed. So strictly speaking, the
number is two to the end, minus two. But,
two to the end is certainly the closest
answer of the four provided. Now the
minimum cut problem is exactly what you'd
think it would be. I'd give you as input a
graph, and amongst these exponentially
many cuts, I want you to identify one for
me with the fewest number of crossing
edges. So a few quick comments so first of
all the name for this cut is a min cut a
min cut is one with the fewest number of
crossing edges. Secondly to clarify I am
going to allow in the input what is called
parallel edges. There will be lots of
applications where parallel edges are sort
of pointless but for minimum cuts it's
natural to allow parallel edges that means
you have two edges that correspond
Finally, the more seasoned programmers
among you are probably wondering what I
mean by, you're given a graph as inputs.
You might be wondering about how, exactly,
that's represented. So the next video's
gonna discuss exactly that. The popular
ways of representing graphs, and, and how
we're gonna usually do it in this course,
specifically via what's called an
adjacency list. Okay so I want to make
sure that everybody understands exactly
what the minimum cut problem is asking, so
let me draw for you a particular graph.
With A vertices. And quite a few edges.
And what I want you to answer is what is
the min-cut value in this graph, that is
how many edged cross the man on cut, the
cut with the fewest number of crossing
edges. Alright, so the correct answer is
the second choice. The [inaudible] cut
value is two, and the cut which shows that
is just to break it, basically, in half,
into the two halves. In this case, there
are only two crossing edges. This one and
this one. And I'll leave it for you to
check that there's no other edge that has
as few as two edges. Now in this case,
we've got a very balanced split when we
took the minimum cut. In general, that
need not be true. Sometimes even a single
vertex can define the minimum cut of a
graph. And I encourage you to think about
a concrete example that proves that. So
why should you care about computing the
minimum cut? Well this is one problem
amongst a genre called graph partitioning
where you're given a graph and you wanna
break it into two or more pieces. And
these kinds of graph partitioning problems
come up all the time in a surprisingly
diverse array of applications. So let me
just mention a couple at a high level. So
one very obvious one when you have a, when
your graph is representing a physical
network. What identifies something like a
[inaudible] allows you to do is identify
weaknesses in your network. Then perhaps
it's your own network and you want to
understand where you want to soup up the
infrastructure. Because it's in some sense
a hot spot of your network or a weak
point. Or maybe there's someone else's
network and you want to know where the
weak spot is in their network. In fact
there is some declassified documents about
mm, about fifteen years ago or so which
showed that the United States and Soviet
Union Militaries, back during the Cold
War, were actually quite interested in
computing minimum cuts. Cuz they were
looking for things like, for example,
what's the most efficient way to disrupt
the other Country's transportation
network. Another application which is a
big deal in social network analyst these
days, is the idea of community detection.
So the question is amongst a huge graph,
like say the graph of everybody whose on
Facebook or something like that, how can
you identify small pockets of people that
seem tightly knit. That seem closely
related from which you like to infer that
they're a community of some sort. You know
maybe they all go to the same school,
maybe they all have the same interest,
maybe they're part of the same biological
family Whatever. Now, it's, to some
degree, still an open question, how to
best define communities and social
networks. But as a quick and dirty sort of
first order heuristic, you can imagine
looking for small regions, which, on the
one hand, are highly interconnected
amongst themselves. But quite weakly
connected. To the rest of the graph, so
subroutines like the minimum cut problem
can be used for identifying these small
densely interconnected, but then weakly
connected to everybody else pockets of the
graph. Finally cut problems are also used
a lot in, in vision. So for example, one
way you can use them is in what's called
image segmentation. So here what's going
on is your given as inputs two D array
where each entry is a pixel from some
image. And there's a graph which is very
natural to define given a two D array of
pixels, namely you have an edge between
two pixels if their neighboring. So for
two pixels that are immediately next to
each other, left to right or top to
bottom. You put an edge there. So that
gives you, what's called a grid graph. And
now unlike the basic minimum cut problem
that we're talking about here. In image
segmentation it's most natural to use edge
weights, where the weight of an edge is
basically how likely you expect those two
pixels to be coming from a common object.
Why not? You expect two neighboring pixels
to come from the same object. Well,
perhaps their color maps are almost
exactly the same, and you just expect that
they're part of the same thing. So once
you've defined this grid graph with
suitable edge weights, now you run a graph
partitioning or mid-cut type sub-routine
and the hope is that the cut that it
identifies rips off one of the contiguous
objects in the picture. And you do that a
few times and you get the major objects in
the given picture. So this list is by no
means exhaustive of the applications of
ming cut and graph partitioning sub
routines, but I hope it serves as
sufficient motivation to watch the rest of
the lectures in this sequence.