Okay, so this video's not about any
particular graph problem, not about a, any
particular graph algorithm. Just, sort of,
the preliminaries we need to discuss
algorithms on graphs. How do we measure
their size? How do we represent them, and
so on. Remember what a graph is, it really
has two ingredients. First of all, there's
this set of objects we're talking about.
Those might be called vertices.
Synonymously, we might call them nodes. We
represent pair wise relationships using
edges. These can be either un-directed in
which case, they're ordered pairs or an
edge can be directed from 1 to another. In
that case, they're ordered pairs, and we
have a directed graph. Now, when we talk
about say, the size of a graph, or the
running time of an algorithm that operates
on a graph. We need to think about what we
mean by input size. In particular, for a
graph, there's really two different
parameters that control how big it is,
unlike an array. For arrays, we just had a
single number, the length. For graphs, we
have the number of vertices, and we have
the number of edges.
Usually we'll use the notation n for the
number vertices, m for the number of
edges. So the next quiz will ask you to
think about how the number of edges m, can
depend on the number of vertices, n. So,
in particular, I want you to think about
in this quiz, an un-directed graph It has
n vertices. There's no parallel edges.
'Kay, so for a given pair of vertices,
there's either zero or one edge between
them. Moreover, let's assume that the
graph is unconnected. 'Kay?
So I don't want you to think about graphs
that have zero edges. Now, I haven't
defined what a graph is. What it means for
a graph to be connected formally, yet, but
I hope you get the idea. It means it's in
one piece, you can't break it into two
parts that have no edges crossing between
them. So, for such a graph, no parallel
edges, in one piece, n vertices, think
about what is the minimum number of edges
it could possibly have, and what is the
maximum number of edg es, as a function of
n, that it could possibly have. All right,
so the correct option is the first one The
fewest number of edges that a connected
undirected graph we can have is n minus 1,
and the maximum number of edges that an
undirected graph with no parallel edges
can have is n times n minus 1 over 2,
better known as n choose 2. So why does it
need at least n minus 1 edges, if it's
going to be in one piece. Well think about
at, adding the edges one at a time. Okay,
on each of the edges of the graph. Now,
initially, you just have a graph with zero
edges, the graph has indifferent pieces
and isolated vertices has no edges at all.
Now each time you add one edge, what you
do is you take two of the existing pieces,
at best, and fuse them into one. So, the
maximum decrease you can have in the
number of different pieces of a graph is
it can decrease by 1 each time you add an
edge. So from a starting point of n
different pieces, you've got to get down
to 1 piece. So that requires the addition
of n minus 1 edges. You can also convince
yourself of this best, by drawing a few
pictures and noticing that trees achieve
this bound exactly, so for example here is
a 4 vertex tree that has 3 edges. So this
is a case where m is indeed, n minus 1.
Now, for the upper bound, why can't you
have more than n choose 2? Well, it's
clear that the largest number of edges you
can have is for the complete graph. Where
every single pair of edges has 1 between
them. Again, there's no parallel arcs and
edges are unordered. So, there's at most,
n choose 2 possibilities of where to put
an edge. So again, if n equals 4, here
would be an example with a maximum
possible number, 6 edges. So, now that
I've got you thinking about how the number
of edges can vary with the number of
vertices. Let me talk about the
distinction between sparse and dense
graphs. It's important to distinguish
between these two concepts because some
data structures and algorithms are better
suited for sparse graphs. Other data
structures and algorithms are better
suited for dense graphs. So, to make this
precise, let me just put down this very
common notation n is the number of
vertices of the graph under discussion, m
is the number of inches. This is quite
standard notation. Please get used to it
and use it yourself. If you reverse these,
you will confuse a lot of people who have
familiarity with graph algorithms and data
structures. Now one thing we learned from
the previous quiz is the following. So in
most applications, not all applications,
but most applications, m is at least
linear in n. Remember in the quiz we saw
is at least n minus 1 if you wanted the
graph to be connected, and it's also big O
of n squared. This is under the assumption
that there's no parallel arcs. Now, there
are cases where we want to allow parallel
arcs. In fact we'll do that in the
contraction algorithm for the min cut
problem. There are cases where we want to
allow the number of edges to drop so low,
that the graph breaks into multiple
pieces. For example, when we talk about
connected components but more often than
not, we're thinking about a connected
graph with no parallel edges. And then we
can pin down the number of edges m to be
somewhere between the linear and the
number of nodes, linear and n and
quadratic in it. Now I'm not going to give
you a super formal definition of what a
sparse or a dense graph is, and people are
a little loose with this, this terminology
in practice. But basically, sparse means
you're closer to the lower bound, closer
to linear. Dense means, you're closer to
the upper bound, closer to quadratic. Now
I know this leaves ambiguity when the
number of edges is something you know like
n to the 3 halves. usually in that case
you'd think of that as a dense graph. So
usually anything which is more than N
times logarythmic terms, you'd think of
that as a dense graph. But again, people
are a little bit sloppy with this when
they talk about graphs. Next I want to
discuss two representations of graphs and
we're mostly going to be using the s econd
one in this course, but this first one,
the adjacency matrix, I do want to mention
just briefly, just on this slide. This is
the supernatural idea where you represent
the edges in a graph using a matrix. Let
me describe it first for undirected
graphs. So, the matrix is going to be
denoted by capital A, and it says square n
by n matrix where n is the number of
vertices of the graph. And the semantics
are the i-jth entry of the matrix is 1. If
and only if there's an edge between the
vertices i and j in the graph. I'm
assuming here that the vertices are named
1, 2, 3, 4, et cetera all the way up to n.
It's easy to add bells and whistles to the
adjacency matrix to accommodate parallel
edges to accommodate edge weights, which
is accommodate directed arcs, directed
edges. If you wanted to have parallel
arcs, you could just have Aij denote the
number of arcs that are between i and j.
If edges have different weights, you could
just have Aij be the weight of the ij
edge. And for the directed graph you could
use plus ones and minus ones. So if the
arc is directed from i to j, you'd set i,
Aij to be plus 1. If the arc is directed
from j to i, you'd set Aij to minus 1.
There are many metrics by which you can
evaluate a data structure, or a
representation. two important ones I want
to discuss here. First of all, the number
of resources it requires and in this
context, that's the amount of space that
the data structure needs. The second thing
is what are the operations of the data
structure supports. So let's just begin
with space requirements. What are they for
the adjacency matrix? Alright, so the
answer at least with the sort of straight
forward way of storing a matrix is n
squared. And this is n dependent of the
number of edges. So you could try to beat
this down for sparse graphs using sparse
matrix tricks. But for the basic idea of
just actually representing an n by n
matrix, you got n squared entries, you
gotta store one bit in each whether the
edge is there or not. So that's going to
give yo u n squared space. The constants
are, of course, very small, because you're
just storing one bit per entry. But
nonetheless this is quadratic in the
number of vertices. Now that's going to be
fine if you have a dense graph, the number
of edges is as high as n squared, then
you're not really wasting anything in this
representation. But in a sparse graph, if
m is much closer to linear, then this is a
super wasteful representation. Let's talk
about the ajacently list representation,
this is the, the dominant one we'll be
using in this class. This has several
ingredients. So, first you keep track of
both the vertices and the edges as
independent entities. So you're going to
have an array, or a list of each. And then
we want these two arrays to
cross-reference each other in the obvious
way. So given a vertex, you want to know
which edges it's involved in. Given an
edge, you want to know what its endpoints
are. So, let's say first, most simply,
each edge is going to have two pointers,
one for each of the two endpoints. And in
directed graph, of course, it would keep
track of which one is the head and which
one is the tail. Now, each vertex is going
to point to all of the edges of which it's
a member. Now in an undirected graph, it's
clear what I mean by that. In a directed
graph, you could do it in a couple ways.
Generally you'd have a vertex, keep track
of all of the edges, for which it is the
tail. That is, all of the edges which you
can follow one hop out from the edge. If
you wanted to, you can also have a second
array, at a more expense of storage, where
the vertex also keeps track of the edges
pointing to it. The edges for which it's
the head. So, let me ask you the same
question I did with an adjacency matrix.
What is the space required of an adjacency
list, as a function of the number of edges
m, and the number of vertices n, of the
graph? So, the correct answer to this
question is the third option, theta of m
plus n, which we're going to think of as
linear space in the size of the gra ph.
So, this quiz is, is a little tricky. So,
it's explain the answer when we return to
the slide with the ingredients of
adjacency lists. And let's compute the
space for each of these four ingredients
separately. Most of them are
straightforward. For example, consider the
first ingredient. This is just an array,
or a list of the n vertices. And we just
need constant space per vertex to keep
track of its existence. So this is going
to be theta of n, linear in the number of
vertices. Similarly, for the m edges, we
just need linear space in the number of
edges to remember their existence. So
that's going to be theta of m. Now, each
edge has to keep track of both of its
endpoints. So that's two pointers, but two
is a constant. For each of the m edges, we
have a constant space to keep track of
endpoints. So that's going to give us
another theta of m constant per edge. Now,
this fourth case, you might be feeling
kind of nervous, because a vertex, in
principle could have edges involving all n
minus 1 of the vertices. So the number of
point or is it a single vertex could be
theta of n. Also you could have you know,
you do have n vertices that could be theta
of n squared. And certainly in something
like a complete graph you really would
have that function. But the point is in
sparse graphs n, n squared is way overkill
to the space needed by this fourth set of
pointers. Actually, if you think about it
for each pointer in the fourth category, a
vertex pointing to a given edge, there is
a pointer in the third category pointing
in the opposite direction, from that edge
back to that vertex. So, there's actually
a one to one correspondence. Between
pointers in the third category, and
pointers in the fourth category. Since the
third category has space theta of m, so
does all of the pointers in the fourth
category. So adding up over the four
ingredients, we have one theta of n, and
three theta of ms, so that's going to give
us overall a theta of m plus n. If you
prefer, another way you could think about
this would be theta of the max of m and n.
These are the same up to a constant
factor. Now, as we discussed in a previous
slide. Often, m is going to be bigger than
n, but I wanted to do a generic analysis
here, which applies even if the graph is
not connected, even, even if it is in
multiple pieces. So the space of the
adjacency list is within a constant factor
the same as the number of ingredients in
the graph, the number of vertices plus the
number of edges. So in that sense, that's
exactly what you want. Now being
confronted with these two graph
representations that I've shown you I'm
sure you're asking, well, which one should
you remember? Which one should you use?
And the answer, as it so often is, is it
depends. It depends on two things. It
depends on the density of your graph. It
depends on how m compares to n. And it
also depends on what kind of operations
that you support, want to support. Now
given what we're covering in this class,
and also the motivating applications I
have in mind I can give you basically a
clean answer to this question for the
purposes of these five weeks. Which is
we're going to be focusing on adjacency
lists. The reason we're going to focus on
adjacency lists in this class, is both, is
for both of these reasons, both because of
the operations we want and both because of
the graph density and motivating
applications. So, first of all, most of
the graph primitives, not all, but most,
will be dealing with graph search and
adjacency lists are perfect for doing
graph search. You get to a node. You
follow an outgoing arc. You go to another
node. You follow an outgoing arc and so
on. And so, adjacency lists are the
perfect thing to do graph search.
Adjacency matrices are definitely good for
certain kinds of graph operations. But
they're not things we're really going to
be covering in this class. So that's
reason one. Reason two is, a lot of the
motivations for graph primitives these
days comes from massive, massive networks.
I mentioned earlier how the web ca n be
fruitfully thought of as a directed graph.
Where the vertices are individual web
pages. And directed arcs correspond to
hyperlinks, going from the page with the
hyperlink, pointing to the one that the
hyperlink goes to. Now, it's hard to get
an exact measurement of the web graph, but
a conservative lower bound on the number
of vertices is something like 10 billion.
So that's 10 to the 10. Now that's pushing
the limits of what computers can do, but
it's within the limits. So if you work
hard, you can actually operate on graphs
with 10 to the 10 nodes. Now, suppose we
use an adjacency matrix representation. So
if n is 10 to the 10, then n squared is
going to be like 10 to the 20. And now
we're getting close to the estimated
number of atoms in the known universe. So
that is clearly not feasible now and it's
not going to be feasible ever. So the
adjacency matrix representation is totally
out for, huge sparse graphs like the web
graph. Adjacency lists, well, the degree,
on average, in the web, is thought to be
something like 10. So, the number of edges
is only going to be something like 10 to
the 11. And then the adjacency of this
representation will be proportional to
that. And again, that's really pushing
what we can do with current technology,
but it is within the limits, so using that
representation we can do non-trivial
computations on graphs, even at the scale
of the web graph.