0:00

Hi again.

Â In the last lecture we saw the problem of the small wall defect, and

Â how we test if the, if a network or a graph has a small wall defect.

Â And as we said or

Â we ended last time, is by formulating the problem, as a graph theoretic problem.

Â Or the input was a graph, and we had to compute something on the graph.

Â So now the question is, what is a graph?

Â The, the, the purpose of this lecture, is to introduce some basic concepts ah,ah,

Â on graphs, that are needed for this specific problem.

Â Graph theory is a very rich field of computer science.

Â We are not going to cover, even 5% of it.

Â And we are not going to introduce all the concepts that we

Â need throughout this course.

Â Now. We are going to introduce this concept as

Â we need them.

Â For now we need to talk about basics of graphs.

Â What is a graph?

Â How we represent it.

Â What is a distance in a graph because we need the distances to,

Â to look at the small walled problem.

Â So, what is a graph?

Â That first thing we are going to look at at the graphs in terms of

Â directions of edges.

Â So, we are going to talk about two types of graphs in the beginning.

Â There's an undirected graph and there's a directed graph.

Â What is an undirected graph?

Â A, an undirected graph formally is, is, is described by a pair two elements, V and E.

Â V is a set of nodes.

Â We say it's a set of nodes.

Â It has to be, of course, finite.

Â It's a finite set of nodes.

Â And E is a set of undirected edges, where an edge is basically a set of two nodes.

Â Okay? So an edge connects two nodes, and

Â we represent it as a set of these two nodes.

Â So, as an example,

Â [SOUND] this is an undirected graph.

Â That has four nodes and four edges.

Â The set of nodes in this graph are 0, 1, 2, 3.

Â And the set of edges in this graph are, there's an edge between 0 and 1 that is

Â undirected, so we represent it as an unordered pair or a set of two elements.

Â There's 0, 1.

Â There's an edge between 1 and 2.

Â There is an edge between 2 and 3.

Â And there is an edge between 3 and 0.

Â And this graph, if I call this graph G.

Â This is the, the picture of the graph, or the drawing of the graph.

Â Formally, the graph is the pair V, E where V is the set and E is this set.

Â Notice that in sets order does not matter.

Â I could have written two, one, zero, three, three, one, zero, two and so on.

Â The order of the two nodes here zero, one, one, zero are the same.

Â So I don't write it twice.

Â Same thing with one, two, two three, three zero.

Â The, the, the fact that I wrote this edge before this edge means nothing.

Â I could have written this before and so on.

Â So with undirected graphs, we have a set of nodes,

Â we have a set of undirected edges.

Â Okay, when we talk about directed graphs.

Â Directed graphs have a similar, a similar thing in terms of nodes.

Â We have a set of nodes.

Â Doesn't change.

Â What the difference is, with the, with the edges.

Â So now these are undirected edges.

Â But when we talk about directed graph, we have direction on the edges and

Â when we write them formally, we do not use set notation.

Â We use double notation.

Â 3:51

This are their ids or numbers than, the names of the nodes do not have to be zero,

Â one, two, three, the could have been U, V, X, Y, they could have been A1, A2, A3, A4.

Â These are just node ids, in some sense.

Â And the edges now, I have an edge from 0 to 1, from 0 to 1.

Â So we write it as the pair 0,1.

Â 0 on the left, 1 on the right,

Â the way we read it is that the edge is from the left to the right, from 0 to 1.

Â 4:26

Okay?

Â Now notice the difference.

Â Now the notation is different.

Â It is not the curly braces.

Â We have the parentheses to tell us this is an ordered pair.

Â This is the, what we call the tail of the edge.

Â This is the head of the edge.

Â It goes from 0 to 1, 2 to 1, 3 to 1.

Â It has three edges.

Â So, with undirected graphs we have undirected edges that are represented as

Â sets with directed graphs we have, directed edges that are represented as

Â ordered pairs, where the edge is read from the tail to the head.

Â Okay? So we have directed and undirected graphs.

Â In this course, we will not allow.

Â Self-loops and we will not allow parallel edges.

Â What I mean by this is, we will not have a case where we have two edges from 0 to 1.

Â This is not going to be allowed.

Â We don't allow this.

Â This is called parallel edges.

Â Also at the same time, we are not going to have, a self-loop like this.

Â We won't have an edge from a node to itself.

Â So these, we can assume throughout the course that these do not exist.

Â 5:29

Notice that, we can have something like this.

Â These are not considered, these are not considered parallel ledges.

Â Edge from 0 to 1 is not equivalent from the edge from 1 to 0.

Â Think about it as a one-way street, or two-way street.

Â If I, have this,

Â I'm saying the street from intersection 0 to intersection 1, is one-way.

Â If I do this, I'm saying it is a two-way street.

Â And these are not the same thing.

Â Okay?

Â So, in this course we will not allow parallel edges.

Â We are not going to allow self-loops.

Â You can assume this, throughout.

Â Now, this is a graph.

Â This is a drawing of a graph.

Â Remember that, we need to write algorithms that reason about graphs.

Â We need to write computer programs that take graphs as input,

Â manipulate graphs, print graphs, and so on.

Â Of course, we cannot give a computer, a description of a graph like this.

Â I cannot say, here is the drawing of the graph, understand it.

Â We have to represent the graph in a certain way.

Â 6:31

Now, of course, what you see on the board is already one representation of a graph.

Â If you want to describe the graph to me,

Â to an algorithm to a computer program, you can describe two sets.

Â The first set, is the set of the nodes.

Â The second set is a set of, of directed edges around directed edges.

Â However, this is not commonly used representation of graphs.

Â I would want you to think about what would be bad with this representation?

Â Think about it as in terms of the amount of space, or

Â memory, that it's going to take just to represent a very big graph using this.

Â There's a lot of redundancy, in representing the graph like this.

Â Okay?

Â So, this representation, while this is a representation of a graph,

Â in terms of the two sets.

Â These are, this is not the commonly used representation and is not the,

Â the representation that we'll be using, when we talk about algorithms that

Â manipulate graphs or computer programs that manipulate graphs.

Â Instead.

Â We will be using,

Â making use of one of two, representations that are very commonly used.

Â One of them is called adjacency list.

Â And one of them is called adjacency matrices.

Â And we will illustrate them, on the undirected graph that we, we had.

Â 8:16

An adjacent.

Â A node is adjacent, a node i is adjacent node j if there's an edge between them.

Â So, I ask what are the neighbors of node 0?

Â The no, the neighbors of node 0 are 1 and 3.

Â So, I put them like this.

Â What are the neighbors of node 1?

Â It's 0 and 2.

Â What are the neighbors of node 2?

Â It's 1 and 3.

Â What are the neighbors of 3?

Â It's 0 and 2.

Â Okay?

Â This is adjacency list representation of this graph, notice two, two things here.

Â The first thing is that the order of the,

Â on the right hand side does not matter, does not matter.

Â I could have written three one, one three, zero two, two zero, it doesn't matter.

Â The second thing, notice the redundancy in this representation.

Â One is a neighbor of zero.

Â Zero is a neighbor of one.

Â In undirected graphs,

Â it doesn't matter when you have an edge between node zero and one.

Â It's a node, it's an edge between these two nodes.

Â But with adjacents, unless we don't have a way to,

Â to eliminate this, we have to write it twice.

Â 10:58

I put an enter zero here, if i and j, are not an edge.

Â This notation says that i, j, this set is an element of E.

Â This notation says that i, j is not an element of E.

Â Or in English.

Â This says that i, there is an edge between i and j.

Â This says i, there's no edge between i and j.

Â So if I go to this here, there is definitely no edge between zero and

Â itself, or one itself to one itself, three in itself.

Â There is an edge between zero and one.

Â There is an edge between ze, there is no edge between zero and two.

Â There is no, there is an edge between zero and three.

Â So it is one.

Â 12:05

If we go back to 0, 1, 3, and 2.

Â If we go to our original graph.

Â Now, we put in the matrix i, j.

Â Now the order matters.

Â We put one here.

Â If there's an edge from i to j.

Â If i,j is in E and there's zero, if i,j is not in E.

Â Okay?

Â So in this case for example when I do matrix A.

Â [SOUND] I have an edge

Â from 0 to 1.

Â Right there's 1.

Â I have no edge from 1 to 0.

Â So this is 0.

Â Okay?

Â So we say that this matrix is not necessarily symmetric, A, i,

Â j is not necessarily equal to A, j, i.

Â They're equal only if there's an edge in both ways between these two nodes.

Â In the case of undirected graph, that's, the, the matrix was symmetric.

Â If you have one in entry A, i, j, you have to have one in entry A, j, i.

Â Okay? So this is,

Â these are the two representations that we will be using alter in this course.

Â We will assume one of the two in every case, but

Â the, which one we use makes a big difference.

Â 13:27

Because, if the graph is sparse, if the graph has too few edges.

Â It makes more sense to use an adjacency list, if the graph is very dense,

Â it has too many edges very close to the maximum number of edges,

Â it makes more sense to use an adjacency matrix.

Â I encourage you to think about these two facts that I just said or

Â about these two claims I made.

Â That, if the graph is sparse, it's better to use adjacency list,

Â if the graph is dense, it's better to use an adjacency matrix.

Â Think about them and think why these make sense.

Â 14:03

In, in when we look at,

Â at an undirected graph, as I said before, we use a term adjacent or

Â neighbor, two nodes i and j are adjacent, if there's an edge between them.

Â At the same thing we say they are neighbors if there's an edge between them.

Â In an undirected graph, so we, let's have the two graphs here.

Â [SOUND] And,

Â let's [SOUND] erase this.

Â So we have these two graphs here.

Â In this case, we say that 0 and

Â 1 are neighbors, 1 and 2 are neighbors, and so on.

Â The degree of a node is the number of neighbors, so it has, two neighbors here.

Â So the degree of node 0 is 2.

Â And here the degree of node 1 for the, the degree, sorry, the degree of node 0 is 2.

Â The degree of node 1 is 2 and so on.

Â When we talk about directed graph, we talk about in-degree,

Â how many neighbors are connected by an edge from them to the, to the node?

Â So 1 has in-degree 3, because there are two edges coming into it.

Â It has out-degree 0, because it has no edges outgo, outgoing of it.

Â For node 0, it has in-degree 0, no edges incoming into it.

Â And it has out-degree 1, because it has one, one edge going out of it.

Â