Tip:
Highlight text to annotate it
X
(male narrator) So here's a portion of a housing development
from Missoula, Montana.
And as a part of her job, the development's lawn inspector
has to walk down every street in the development
making sure that homeowners' lawns conforms
to the community recommendations.
Now...you can sort of understand that
if she has to do all this walking,
she's gonna wanna figure out
how to walk as little as possible--
uh...ideally being able to walk
the entire, uh...you know, development
without having to backtrack along any streets.
Uh...so if we're gonna analyze this
and start looking at it mathematically,
uh...looking at this big, huge picture here,
uh...is pretty complicated.
And so we might try sort of simplifying things.
Uh...and one way to do that is to say,
let's identify sort of junction points.
So let's identify places where...streets meet,
uh...or, you know, sort of where there's a corner.
And so we're gonna define all these points
where it looks like streets meet.
And we're gonna call those points "vertices"
of the...of what's gonna be called a graph.
Now this is not graphs like, you know,
your y equals x squared graphs from algebra.
This is graphs as
in a graphical representation, uh...of the situation.
So we introduce these vertices to represent the intersections,
and then we're gonna add the...some edges now
to represent the streets themselves.
So along each of these streets, we're going to draw an edge.
And when we put this all together,
we get a graph.
This graph represents the-the city.
Uh...sort of taking away the back picture now,
we would get something that looks like this.
And here is a set of vertices connected by edges,
and this defines a graph.
The idea here is that we're simplifying the problem down
from this sort of complicated picture,
uh...to just the important things--
the junction points and the edges themselves.
And it's interesting to note that the specific layout here,
uh...is not highly important.
Really, it's just the connection
and the length of those edges that matters.