Tip:
Highlight text to annotate it
X
(male narrator) So for another example of sort of how graphs come into things,
uh...consider this.
Back in the 18th century,
uh...there was a Prussian city called Konigsberg,
uh...where a river-- you can see here--
ran through the city.
Uh...the river forks,
Uh...and-and there were seven bridges that connected,
uh...that crossed the various forks in the river.
And as a weekend amusement,
people would see if they could find a route
that would take them across every bridge once
uh...and then return them to where they started.
And, uh...uh...Leonhard Euler, uh...was sort of the father
of this branch of mathematics called "graph theory."
And he analyzed this problem
uh...and kind of like we're doing
introduced a, uh...graph into this situation.
So let's see if we can do that here.
So really what's important?
What we really care about is the bridges.
You know, if I start here and...whoops...yeah,
if I start here and walk across this bridge,
and then I'm gonna walk across this bridge,
I don't really care how far I have to walk here.
That's not relevant to this question.
Right?
All that matters is that I went from this island to this side,
and then maybe walked back across this bridge to really...
we walked back to this side
of the...of-of...to go back to the island.
And then if I walk across this bridge
and then walk back across to the island,
I'm really treating all of this island as one location.
So really we have sort of the-the whole...
the whole north bank area up here.
We have our-our island here...
and, uh...we have our whole south bank here,
and-and our whole sort of east bank, uh...over here.
And we have two bridges
connecting the north bank to the island,
two bridges connecting the south bank to the island,
one bridge connecting the island to the east bank,
one bridge collecting...
connecting the north bank to the east bank,
and one bridge connecting the east bank to the south bank.
And this picture starts getting at sort of the core notion,
but again, it doesn't really matter
where in the north bank we are.
So what we could do is shrink this entire north bank down
to a single vertex.
And the island could be represented
by a single vertex,
and the south bank can be represented
by a single vertex,
and the east bank can be represented
by a single vertex.
And there are two routes to get
from the north bank to the island.
Two routes to get
from the south bank to the island.
One route here, one route here, and one route here.
And so here is a simplified graph
that represents this scenario.
And by looking at this graph,
it makes it a little easier to look at the question
of, you know, is it possible to walk over every bridge--
in this case, that would mean crossing over every edge once--
and return to your starting location?
In other words, return to your starting vertex.