PROFESSOR: In this video lecture, we're going to introduce the idea of directed graphs, or digraphs for short. So normally and before this class, you might have thought of graphs as being something like this. Y is a function of x and graphed on the xy plane. But that's not what we want to be thinking about. Instead, we want to think about something like this.
This is a graph to a computer scientist. Show a bunch of vertices, which are those point that you see, and edges, which connect vertices. Being more specific and direct about this, it's composed of a set V of vertices and a set E of edges, which are composed of 2V each. The way you write that out, an edge is v comma w, and that specifies an edge going from v to w. And in the graph, it would look something like this. Note that they are directed. That an edge from v to w is not the same thing as an edge from w to v in a directed graph.
For example, here we have one directed graph, and you write out vertices as the set of all the vertices you see there. And edges are pairs of vertices. You can also realize that digraph is the same thing as a binary relation on the vertices, because each edge just defines the relationship from one vertice to another. So, every binary relation can be drawn out as a graph. You just put each of the things in each of the sets as vertices and edges being the things that relate from one set to the other.
So, now we're going to define walks and paths. Now, a walk follows successive edges but it can repeat vertices or edges. For example, I can start at the black vertice there, and we can go to red, blue, yellow, red. And w can go back to blue again. There's nothing stopping us.
And the length of these paths is not how many vertices we've gone through, but the number of edges that we've gone through. So here, the length would be five because we went from white to black, black to blue, blue to yellow, yellow red, red blue. It's not the six vertices that we went through. And you have to be careful about that, because that difference of one kind of gets you.
A path, on the other hand, walk through vertices with that repeating a single vertex. So, for example, start at blue, you can go to yellow, you can go red, you can go pink, you can go green, but then we're stuck. We can't go back to red. We've already been there. So, that's it. That would be the end of our path. If we went to red again, then it wouldn't be a path anymore. Not be a valid path. And here, the [INAUDIBLE] length is four edges, not five vertices.
And every graph can be represented as a matrix representation. You draw it out like this. And what we're going to do is if there's a edge that goes from one of the things on the right over to one of things on the top, we'll put a one at that position. For example, there's an edge that goes from the black to the red. So, on the black row in the red column, we're going to put in a one. Same thing, there's one that goes from black to green. We'll put black row, green column, put in another one. And so on for all the edges that we have in our graph.
And the rest we just filled with zeroes. And this is called an adjacency matrix. And as you can see, it uniquely defines a graph. Every edge is represented here, and every one of the vertices is represented here. So, any graph can be drawn up this way.