# Chapter 4 Route Inspection Flashcards

What are the 3 types of graphs that all graphs can be organised into?

Eulerian, semi Eulerian or neither

What is a Eulerian graph or network?

An Eulerian graph or network is one which contains a trail that includes every edge and starts and finishes at the same vertex

What is an Eulerian graph called?

Eulerian circuit

What is a quick way to check that a graph is Eulerian?

If all of the vertices have even degrees and the graph is connected then it is an Eulerian graph

What is a semi Eulerian graph or network?

A semi Eulerian graph or network is one which contains a trail that includes every edge but starts and finishes at different vertices

What is a quick way to check if a graph is semi Eulerian?

What do you know about the graph?

Any connected graph with exactly 2 odd vertices is semi Eulerian

Where the trail will start and end at those 2 odd vertices

What do Eulerian and semi Eulerian graphs both include?

Both include a trail that includes every edge

What are Eulerian circuits sometimes called?

Eulerian cycles

Why may a Eulerian cycle as a name be misleading?

Eulerian cycles may not be a true cycle as some nodes may be visited more than once

What is a trail?

A trail is a walk in which no edge is visited more than once

What is a cycle?

A cycle is a walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once

(A path that starts and ends in the same place)

What is a good way to check that a graph is eulerian or semi eulerian?

You can draw a semi Eulerian and an Eulerian graph without taking your pen off the page and without repeating any arcs

What is a quick way to tell if a graph is neither Eulerian non semi Eulerian?

If it is not connected or if it doesn’t have exactly 2 odd vertices it is neither

What is an easy way to draw a non Eulerian and non semi Eulerian graph/

You can just draw 2 vertices which aren’t connected

(No arcs just 2 nodes)

What are the 2 different names for the same route inspection algorithm?

The route inspection algorithm

Chinese postman algorithm