Define:
An Eulerian trail.
A semi-Eulerian trail.
State the conditions required for a graph to contain an Eulerian trail.
State the conditions required for a graph to contain a semi-Eulerian trail.
In order to traverse a graph which has an Eulerian trail, which vertex should one start at?
In order to traverse a graph which has a semi-Eulerian trail, which vertex should one start at?
Consider G, a very large network, with 400 vertices, each of even degree.
Is network G traversable?
Does an Eulerian trail exists for G? Explain your answer.
State whether it is possible to draw an Eulerian trail on the following networks:
For each of the given networks, answer the following:
State the degree of each vertex.
State whether the network contains an Eulerian trail.
State whether the tables below represent an Eulerian network, semi-Eulerian network or neither:
| Vertex | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| Degree | 2 | 2 | 2 | 4 | 2 | 2 |
| Vertex | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| Degree | 2 | 3 | 2 | 4 | 1 | 2 |
| Vertex | A | B | C | D | E |
|---|---|---|---|---|---|
| Degree | 2 | 2 | 2 | 4 | 2 |
State whether the following graphs are Eulerian graphs:
State whether the following graphs are semi-Eulerian graphs:
For each of the following traversable networks:
State whether the network is Eulerian or semi-Eulerian.
If possible, list the Eulerian or semi-Eulerian trail, starting with vertex B.
For each of the following tables:
State whether the table represents an Eulerian network or a semi-Eulerian network.
Construct a network that represents the information in the table.
| Vertex | A | B | C | D | E |
|---|---|---|---|---|---|
| Degree | 2 | 3 | 2 | 3 | 2 |
| Vertex | A | B | C | D |
|---|---|---|---|---|
| Degree | 2 | 2 | 2 | 2 |
Luigi wishes to traverse the following network:
From which vertex is it possible to start?
Write a semi-Eulerian trail for the network
Sandy wishes to traverse the following network:
From which vertex can she start?
Sandy starts to trace a semi-Eulerian trail through the graph, by moving along the vertices B, C, D. List the vertices that complete Sandy's trail.
Dylan wishes to traverse the following network:
From which vertex or vertices can an Eulerian circuit start?
Dylan starts to trace an Eulerian circuit through the network, by moving along the vertices B, A, D, E, C, D, G. List the vertices that complete the Eulerian trail for Dylan.
Explain the difference between the terms "Hamiltonian cycle" and "Hamiltonian path".
State whether it is possible to draw a Hamiltonian path on the following graphs:
Write a Hamiltonian path for the following graphs by listing the vertices:
State whether the following graphs have Hamiltonian cycles:
For each of the following graphs, write the Hamiltonian cycle starting with vertex A:
State whether the following graphs are Hamiltonian:
Determine which of the following graphs are semi-Hamiltonian:
A neighborhood watch group wants to plan their security route using the network below:
The neighborhood watch wants their route to be fuel efficient, by covering every street only once before moving to the next area.
Is such a route possible?
The group wants to start at Brian's residence, then pick up Evan, and finish at Colin's residence. Write a semi-Eulerian trail for this.
A street cleaning crew was using the following map to plan the route they will follow:
The street cleaning crew wants to plan an efficient run by going over every street only once, starting and ending at the same point. Is such a route possible?
Write a circuit that satisfies their conditions for an efficient route.
A team of workers is to repair seven bridges that cross the river running through town, as shown in the image below:
After repairing each bridge (which involves crossing the bridge), the workers close it off for 24 hours.
Given that they start in the bottom-left area of the town (where the truck is in the image), can the workers repair all seven bridges in one day without going back over a closed bridge?
After repairing all seven bridges, which road do the workers leave by: top left, bottom left, top right or bottom right?
A mail man is planning his route using the graph below:
| Vertex | Residence |
|---|---|
| A | \text{William} |
| B | \text{Ivan} |
| C | \text{Vincent} |
| D | \text{Sean} |
| E | \text{Kenneth} |
| F | \text{Noah} |
Starting at William's house, and passing each house only once, list a path that the mailman could follow.
Kate draws the following mudmap to represent all the houses she has to visit during her milk run:
| Vertex | Residence |
|---|---|
| A | \text{Kate} |
| B | \text{Xanthe} |
| C | \text{Ursula} |
| D | \text{Lisa} |
| E | \text{Ellie} |
Kate wants to plan a route that is time efficient by visiting each house only once, starting and finishing at her own residence. List a route that Kate could follow.
A mailman was allocated an area to deliver the mail to. The following table represents the routes and times between the houses:
Draw a graph representing the area using the information in the table.
List the quickest route for the mailman to take, starting at house D with first delivery to house E and passing by each house only once.
| Starting House | Ending House | Time |
|---|---|---|
| A | B | 11 |
| A | F | 9 |
| A | G | 3 |
| B | F | 5 |
| B | C | 10 |
| C | E | 8 |
| C | G | 6 |
| D | E | 5 |
| D | G | 5 |
| E | G | 7 |
A few colleagues decided to carpool on the way to work. The following map displays the routes between their homes:
Starting from house A, list the shortest path that visits every house exactly once.
Calculate the length of this path.
A courier business has to make multiple pick-ups from several stores. The following map displays the routes between the stores:
Stores A and E need immediate pick up. Starting from store A, and then travelling to E, list the shortest path to take if visiting every store only once.
Calculate the length of this path.
A canned goods company has to make drops at every store in an area. The following map displays the routes between the stores:
Starting from store B, list the shortest path to take if passing by every store only once.
Calculate the length of this path.
The local newsagent drops a newspaper at every house in a certain area. The following graph shows the map of that area:
The newsagent wants to be time efficient. If he enters the area at house B and leaves at house G, list the shortest path for him to travel passing by each house only once.
Calculate the length of this path.
