- [Instructor] Hi.
This is a continuation of our introduction to graphs.
This is a sneak preview into some graph theory
that you'll see in CS 224
and you should treat this as supplementary.
I'm not going to assess you on any material in this video,
so treat this as purely optional,
but I think it's interesting material.
And if you do plan on taking CS 224, which I recommend.
It's the advanced algorithms class,
we call it Algorithm Design and Analysis,
then you'll see some of the concepts
that I'm gonna present here.
And this should help you get up to speed.
But in any event, I hope you find it interesting,
but you won't be examined or quizzed or anything else
with regard to this material.
So let's start with these graphs here.
What do these graphs have in common?
Well, these graphs are fully connected.
Each node is connected to every other node
and we have a special term for this.
We call these complete graphs.
And these are so special that we even have names for them.
We call the complete graph on two vertices K2,
the complete graph on three vertices, K3, and so on.
Now, if we can draw a graph on a 2D surface
without having any of its edges cross,
we call such a graph planar.
So, here in the left, we see K3 is clearly planar,
because we can draw the three vertices,
we can orient them in our drawing in such a way
that the three edges here, none of the cross.
Actually, it's impossible (speaking faintly).
What about K4?
Here we see edges crossing,
but is this the only way to draw K4?
Is it possible to draw K4 on a plane surface
in such a way that none of the edges cross?
And, you know, we could take this one edge here
and stretch it to the outside
and make a drawing that looks kinda like this.
And that's okay, that works,
so now we know that K4 is definitely planar.
It's a little more elegant to draw it this way.
It's sort of a tetrahedral kind of a relationship.
So this is what we mean when we say a graph is planar,
is that we can draw it in 2D
without having any edges cross.
K5, on the other hand, is definitely not planar
and K5 turns up in a lot of proofs in graph theory.
If K5 is found anywhere on a graph,
then the graph is not planar.
So we could hang all kinds of other nodes off of this.
If anywhere on the graph there appears K5,
the graph is not planar.
Now, here's something different that you'll see in CS 224.
Take a look at these two graphs and what do you notice?
Well, A, B, and C form what's called an independent set,
that is none of those vertices,
or none of those nodes, I should say,
shares an edge with any of the others.
So we here we see A, B, C.
A is connected to D, F, and E,
but there's no edge that goes between A and C.
There's no edge that goes between A and B,
and there's no edge that goes between B and C.
So we call that an independent set.
And the same applies to D, E, and F.
You'll see here D, E, and F are connected to A, B, and C,
but there's no edge between F and E,
no edge between F and D,
and no edge between D and E.
And to make this more clear,
we get the picture on the right,
where we've segregated the vertices here,
A, B, and C on one side,
and D, E, and F on the other side.
Remember that these are exactly the same graph,
they're just drawn differently.
So the edge relationships are exactly the same
in both cases.
We're just drawing them differently
so that we can visualize a particular characteristic
of this graph.
And so we have this set containing A, B, and C,
this independent set,
and we have this independent set containing D, E, and F.
Members of these sets share no common edges.
And graphs like this we call bipartite graphs
and we've recently learned about equivalence relations
and it turns out that belonging to an independent set
is an equivalence relation.
And where do these turn up?
Well, bipartite graphs have broad application
and there's all kinds of algorithms
that operate on them.
And one common application is called matching,
and I won't go into too much detail here,
but here's one example of a matching.
On one side, we have high school students,
and on the other side we have the colleges
to which they've been admitted.
By the same token, we could have the same students
and the things to which they're allergic.
So one class of algorithms is designed
to find matchings in a graph,
and another class of algorithms is intended
to produce matchings with certain desirable properties.
For example, the famous Gale-Shapley algorithm
produces stable matchings
and it's used to assign medical students
to medical colleges.
But let's conclude this little sneak preview
and move on to the problem
of how we represent a graph with some data structure.
Now, in the other lecture,
I introduced the adjacency list
and the adjacency matrix
and I mentioned that there was such a thing called
an incidence matrix,
but we didn't go into it there.
We're going to go into it here.
So we're gonna look at this one more data structure,
the incidence matrix.
Now, remember the meaning of incidence.
An edge is incident to a vertex
if the vertex is one of its endpoints, I should say node.
Let me say that again.
An edge is incident to a node
if the node is one of its endpoints.
And the incidence matrix requires
that we label edges and nodes.
And so here you'll see, in the diagram on the left,
we have edge labels e1, e2, e3, and so on through e8.
And don't confuse these with weights.
There are just labels.
We could call them AB, BC, and so on,
but I've adopted this notation
for this particular incidence,
because I think it's more concise and elegant.
So these are just labels.
These are labeling this edge and this edge and this edge,
just like we have labels on our nodes.
So what we do in an incidence matrix
is that we have the edges on one axis,
and these numbers correspond to the subscripts here
of each of these edges.
So this column is going to tell us things about e1
and this column is going to tell us things about e2.
And so we have nodes on the other axis,
these are the node labels,
and what we do is we put a one in the matrix
if a node is an endpoint of an edge, and zero otherwise.
So again, this is our matrix notation
with v and e as subscripts.
V is the vertices, e is the edges.
So let's see how that works.
So here we'll proceed by columns,
each column representing an edge.
So let's start with edge one.
So here we have edge one
and we see that it's incident to A and B,
and so for A, we put a one, for B, we put a one,
and we put zeros on all the other positions.
For edge two, edge two is incident to A
and incident to D,
so we put a one next to A here
and a one here for D
and all the others are zeros.
And similarly for the rest of the incidence matrix.
And so finally, we end up at edge eight,
which is incident to E and F.
You see those down in the lower right-hand corner.
Now, you may wonder what we do
in the case of a directed graph.
Well, in a directed graph, we use negative one.
We use negative one if edge e leaves node v,
and we use positive one if edge e enters node v,
or zero otherwise.
So here we have edge e1
and we would put a negative one
as the entry corresponding to e1 and A,
and a positive one for the entry corresponding
to e1 and B,
because e1 leaves A and enters B.
Okay, so let's see what
the incidence matrix looks like for those.
Again, we'll proceed by columns,
with each column representing an edge.
So you see here e1, it leaves A,
so we've got a negative one here.
It enters B, so we have a positive one here,
and all the rest are zeros.
Have to be because each edge has exactly two components.
And then the same thing.
Here's e2, it leaves D and enters A,
so there's a minus one here
and a positive one here.
And similarly for the rest of the incidence matrix.
Now, notice here that the columns
in the case of a directed graph,
the columns of an incidence matrix will sum to zero
and each row gives the net input to a node.
So if we take a look
and we take the sum here for node A,
we see we have minus one, one, zero,
so there's an equivalent number of in edges and out edges.
This is not true for B, for example,
we see that we have a net of one.
We have one, negative one, and one.
And so that tells us that B has one more in edge
than it has out edges.
And if we check, yeah, that's exactly the case.
We see we have two in edges and one out edge.
So those are some interesting properties
of the incidence matrix.
And I won't go into the applications here,
I just wanted to show you the incidence matrix,
that there are other ways of representing a graph
than just the two that we saw in the previous lecture,
but there are a number of applications
for which incidence matrix provides
the more efficient data structure.
In general, the complexity of the incidence matrix
is big O of V times the cardinality of V
times the cardinality of E.
And again, it has some interesting mathematical properties
and it's used in more advanced applications,
such as polytopes and problems in combinatorics.
And if you don't know what polytopes are and combinatorics,
don't worry now,
but I hope that you see these things in later classes.
And that concludes this little sneak preview
for the graph theory that you might see in CS 224.
Thanks.