ALBERT MEYER: The topic for this video lecture is Connected Vertices, the kind of connections we can have between different vertices through edges. We're going to start by showing that the shortest walk between two vertices is a path. We're going to prove it by contradiction.
Suppose we have some path from u to v and it crosses over itself. So here we have u and v. At some point, you get to c, and you go back to c, and from there you go to v. So you've gone through some vertice twice. But if you want to get the shortest path from u to v, why would you go through this loop? Why not just keep going straight from c to v?
The path without that section that goes from c back to itself also for u to v and is shorter. So if we have any path that crosses over itself, we can just get rid of that part that loops around back into itself, and we still have a walk from u to v. So therefore the shortest walk from u to v is going to be a path.
Now we're going to talk about the length and the walk relation. What this means is with two vertices, v and w, there is this Gn relation between v and w if there exists a length n walk from v to w. Gn is called the length n walk relation for G. So basically, if you can find a way to go from v to w in exactly n steps, then Gn applies from v to w. G itself, when you think about it, is a length 1 walk relation. The graphs define these relations. There is an edge from one vertice to another if there is a length 1 edge from one vertice to another. It is itself.
Now, this lemma-- they say that Gm and relational composition with Gn equals Gm plus n. Let's explain with this means. So what that relational composition means is that the relational composition between the two applies from x to y if there is some vertice, z, such that there is a path, n, from x to z, and then a path, n, from z to y.
Gm applies from x to z and Gn applies from z to y. And this is why this is the same thing as Gm plus n makes sense. If there is a path length n to z and a path length n from there to y, you just go from x to z in m steps, then z to y in n steps. And you have m plus n steps from x to y.
The length 0 walk relation just make each vertice go back to itself. It points back to itself, the individual one. And the lemma is still true. G0 composes with Gn is just Gn, which makes sense. Everything itself plus Gn just gives you Gn.
Let's talk about composition of matrices. So if we have some adjacency matrix for G and we do a composition with sum h, then we can get that by applying this Boolean and/or matrix multiplication. These adjacency matrices are ones and zeros. So we do matrix multiplication, but with Boolean operations instead of plusses and multiplications.
So we can compute A G of n by fast matrix exponentiation. How do we do that? Well, basically you can do it for G n over 2 twice, and then Gn over f for each of those twice, and go doing those Boolean operations on each. So A G of n equals A G of n over 2, applying this operator to A G n over 2. So you can just break it down in 2 each time so you get logarithmic number of problems that we have to do.
Now let's define another relation. G star is just called the walk relation of G. Basically, G star applies from u to v if there is a walk from u to v, no matter how long it is. If you can find some way to get from u to v, then it applies.
If you want to get the walk relation, you just get everything inside the graph and apply self-loops. So add in an edge that points back to itself for every vertice. We called this G less than or equal to. It's basically G and then add in these G0 self edges.
And G less than or equal to has a length n walk if G has a less than or equal to n walk. Now, think about that. If I can get from vertice x to vertice y in n minus some amount of steps in G, then I can get there in n steps in G less than or equal to because I can just loop around. If I want to get here from red to blue, I can get there in one step without those self-loops. But with the self-loops, I can just keep starting from red and go around to red as many times as I want, n minus 1 times, and then do this final step. So I can make a length n walk for any value of n greater than 1.
Now let's compute the walk relation using what we've just defined. So G has n vertices. So the length of paths are going to be less than or equal to n. If you just go in a straight line from one thing to another, passing through each possible vertice, at most you're going to get n minus one length. Because you're going to pass through n vertices, so there's n minus 1 edge that's connected there.
So G star, which is just the relation if there is a walk from u to v, is going to be this G less than or equal to n minus 1. So if we get G less than or equal to, add in all these self-loops, and then find all of the paths of length n minus 1 in there, which is basically all paths since G less than equal to n minus 1 is all paths less than or equal to n minus 1. But since G only has paths of less than or equal to n minus 1, that's just all the paths. It's just every single one of the vertices.
And so we've defined G star and that's how we get all connected vertice pairs. And we can do this in n squared log n time using that composition of the adjacency matrices.