Consider the following networks:
State the weight of the edge from S to Q.
Calculate the weight of the entire network.
State the weight of the edge connecting Q and S.
Calculate the weight of the entire network.
Calculate the weight of the following paths in this network:
Path Y-E-D
Path A-B-Z-X
Path X-C-A-B-Z
Find the weight of the following subnetworks, highlighted in green:
Calculate the weight of the following paths in this network:
Path from Y to X
Path from Z to C
Path from B to X
A group is organizing a tour for the elderly in a park, ending with a picnic. The given graph displays the map of the park:
Calculate the path which gives the shortest distance from the start of the park at vertex A, to the picnic area at vertex J.
The given map shows all possible routes in Mohamad's town. Mohamad travels from his home to his friend's house on a daily basis.
If Mohamad's house is vertex C, and his friend's house is vertex I, determine the shortest path between the two houses.
A grocery store is known for its fast deliveries across the town as shown in the following map:
If the store is at vertex A, and a delivery has to be made to vertex H, determine the shortest path the driver should take.
The police department receives a call about a robbery in progress at a grocery store. The given graph shows the map of the town:
If the nearest police car is located at vertex D and the grocery store is at vertex I, determine the shortest route the police should take.
A firefighting department received an emergency call about a house fire across the town represented in the following graph:
If the firefighting department is located at vertex L, and the house is at vertex A, determine the shortest route the firemen should take.
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 from 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.
