Slides in this set

Slide 1

Preview of page 1

Route Inspection
Which of these can be drawn without taking your pencil off
the paper and without going over the same line twice?
If we introduce a vertex where two lines meet and make the
lines edges, then we can model these problems as graphs.
If we can find a path that goes over all the edges of the graph without
repeating an edge then the graph is said to be traversable.…read more

Slide 2

Preview of page 2

Route Inspection
Whether or not a graph is traversable depends on the number
of edges that meet at the vertices. The number of edges that
meet at a vertex is called the degree of that vertex.
Degree 3
Odd
Degree 2
Even Even
Degree 2
Degree 3
Odd
An odd vertex is one with an odd degree.
An even vertex is one with an even degree.…read more

Slide 3

Preview of page 3

Route Inspection
A graph with only even vertices is traversable and we can start and
finish at the same vertex. Such a graph is called Eulerian.
All vertices even ­
Eulerian graph.…read more

Slide 4

Preview of page 4

Route Inspection
A graph with exactly 2 odd vertices is traversable as long as we
start on one of the odd vertices and finish at the other one. Such a
graph is called Semi-Eulerian.
2 odd vertices ­ All vertices even ­
Semi-Eulerian Eulerian graph.…read more

Slide 5

Preview of page 5

Route Inspection
A graph with more than two odd vertices is not traversable.
4 odd vertices ­
not traversable
2 odd vertices ­ All vertices even ­
Semi-Eulerian Eulerian graph.…read more

Slide 6

Preview of page 6

Route Inspection
Which type of graph is the one on the far right?
4 odd vertices ­
not traversable
2 odd vertices ­ All vertices even ­ Two odd vertices
Semi-Eulerian Eulerian graph. - Semi-Eulerian…read more

Slide 7

Preview of page 7
Preview of page 7

Slide 8

Preview of page 8
Preview of page 8

Slide 9

Preview of page 9
Preview of page 9

Slide 10

Preview of page 10
Preview of page 10

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all resources »