- Tubelator AI
- >
- Videos
- >
- Film & Animation
- >
- (Spectral; Fall 23) 28 - How graph labeling naturally connects with distance matrices
(Spectral; Fall 23) 28 - How graph labeling naturally connects with distance matrices
Course site: https://www.stevebutler.org/spectral2023
Presenter: https://www.stevebutler.org/
We continue the discussion on distance matrices and the graph labeling problem and show how these are naturally connected to one another.
Install Tubelator On Chrome
Video Summary & Chapters
No chapters for this video generated yet.
Video Transcript
Paw graph, here we go.
So, as I draw the paw graph,
and I'll use green to number these vertices,
and I don't know why I chose zero, one, two, three,
but okay, somebody who spends too much time programming.
And we'll do the distance matrix.
Okay.
And we're really lucky we can even get the distance on our first try.
And that's not too bad. So there's our distance matrix.
Okay, so does anybody have a nice labeling in mind for our paw graph?
This one turns out not to be too bad.
In fact, I claim you can do it with length 2.
All right, so you said 00, 01.
Maybe you can't do length 2, but you can do it length 3 for sure.
Well, you can make this one a 11.
I think maybe we need length 3.
All right, apparently we definitely can't do it in 2, but that's all right.
D, D, 0, 1.
There we go.
All right, good.
Three is good.
Three is better than two.
Now.
Two is better than four.
Oh, we're doing an induction argument.
Okay.
Well, so here's the idea.
I want to show how a labeling relates to the distance matrix.
And the way we'll do it is we're just going to grab one entry at a time.
So let's go to all the first entries.
And we're going to make a little matrix that corresponds to our first entries.
And just to help us, I'm going to use the actual labels.
I'll put them on the side.
0011, 0011.
Now, think about the labeling problem.
When do we get a contribution to a distance between two labels?
Well, there has to be no D and.
And they're different.
And they're different, right?
So what you can do is you compare the label on the row
to the label on the column.
So if one of them is zero and the other is one,
or vice versa, then in terms of the distance in the graph,
that means you would increase that by one.
So what we'll do is we'll do that here.
So we say, well, it's not gonna be very exciting,
but I can think about how the first index
is affecting the distance between labels.
All right, so that's what we have there.
Now, what's the second thing we should look at?
