Opening Problem

Below is a map showing the key locations Eve and Heidi plan to visit during their holiday in Paris, including their hotel and showing the roads connecting those locations.

1.) Evan wants to plan a route starting at ending at the hotel that will visit every landmark exactly once. Is it possible? Can you help Evan?

2.) Heidi is more interested in the journey than the sights. She wants to plan a route starting and ending at the hotel that will walk along every road exactly once. Is it possible? Can you help Heidi? What if she wanted to end at the Eiffel tower instead of the hotel?

Graphs

A graph or network is a structure which shows the physical connections or relationships between things of interest.

We use points (which we call vertices) to represent the things of interest and lines (which we call edges) to represent the connections or relationships.

An edge is named according to the vertices at either end, for instance the blue edge in the graph below is called BC. An edge from a vertex to itself is called a loop.

Undirected Graphs

In an undirected graph we can move in either direction along the edges of the graph. Vertices connected by an edge are called adjacent vertices. Edges which share a common vertex are called adjacent edges. The degree of a vertex is the number of edges connected to it. Note that a loop contributes 2 to the degree of a vertex.

Directed graphs

A directed graph, as shown above, contains arrows indicating the direction that it is permitted to move along the edges.

In a directed graph, the in degree of a vertex is the number of edges coming in to the vertex and the out degree of a vertex is the number of edges going out from the vertex.

Exercise

Answers