Describe a Hamiltonian cycle.
Describe a Hamiltonian path.
State whether the following graphs contain a Hamiltonian path:
State whether the following graphs contain a Hamiltonian cycle:
State a Hamiltonian path for each of the following graphs:
Start the path at vertex A for the following graph:
List a Hamiltonian cycle, starting with vertex A, for each of the following graphs:
Kate draws the mudmap below 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 mail man is planning his route in a certain area using the graph below:
| Vertex | Residence |
|---|---|
| A | \text{William} |
| B | \text{Ivan} |
| C | \text{Vincent} |
| D | \text{Sean} |
| E | \text{Kenneth} |
| F | \text{Noah} |
The mail man starts his route at William's residence. He wants his route to be time efficient by passing by each house only once. List the path the mailman should follow.
A private school bus is to pick up students from a certain area. The following map shows the routes connecting the students' houses:
The bus driver wants to save as much time as possible on his route. If he starts his route at vertex D, what is the shortest path that visits each house exactly once?
A few colleagues decided to carpool on the way to work. The following map displays the routes between their homes:
Starting from house A, determine the shortest path that visits every house exactly once.
A rock band is planning a tour across several cities. The following table represents the routes and distance between the cities at which they will be performing:
Construct a graph that represents the table.
Hence, find the shortest route for the rock band to take if they start at city A and passing by each city only once.
| Starting City | Ending City | Distance |
|---|---|---|
| A | C | 9 |
| A | F | 6 |
| B | E | 11 |
| B | F | 5 |
| C | D | 3 |
| C | F | 7 |
| E | D | 5 |
| E | F | 8 |
A mailman was allocated an area to deliver the mail to. The following table represents the routes and times between the houses:
Construct a graph based on the table.
Hence, find the quickest route for the mailman to take if he starts at house D, makes the first delivery to house E, and passes 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 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, determine the shortest path to take if visiting every store only once.
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, determine the shortest path to take if passing by every store only once.
The delivery man has to drop a newspaper at every house in a certain area. The following graph shows the map of that area:
The delivery man wants to be time efficient. If he enters the area at house B and leaves at house G, find the shortest path for him to travel if he passes by each house only once.
