For each of the following networks, state a valid walk that crosses each vertex once:
For the graphs below, list the vertices that represent the described walk:
A closed walk with 4 edges, starting from W.
A closed walk with 3 edges, starting from H.
Consider the graph below:
State the shortest possible closed walk which includes the vertices S and Q.
State the shortest possible closed walk which includes the vertices R and T.
State a trail from A to E with 4 edges that does not go through D for the given graph:
State the shortest possible trail from E to A through D and C for the given graph:
For each of the following graphs, state the shortest possible closed trail using the information provided:
The trail starts at H.
The trail starts at T and includes S and R but does not include Q.
For each of the following, state the longest possible closed trail using the information provided:
The trails starts with vertices F, D, C in order.
The trails starts with vertices P, R, T in order.
For each of the following networks, state a valid circuit:
State the definition of a path in regard to graph theory.
For each of the following graphs, state a valid path:
Determine the number of unique paths from B \text{ to } D without passing over the same vertex twice.
State a path that satisfies the given information for each of the following networks:
The path starts at B and ends at X.
The path starts at H, goes through 4 other vertices, and then ends at B.
The path starts at Q, has length 3, and ends at P.
The path starts at P and ends at Q
For the following network:
State whether each of the following are valid walks:
State whether each of the following are valid paths:
List a sequence of vertices, starting from A, that represents a cycle of 5 edges in the given network:
For the following network:
State the correct term for this sequence of vertices:
X, H, Y, Q, B, W, Q, Y, X
State a cycle with 3 edges that starts at X.
For each of the following graphs, find the shortest path for the given start and end point and state its length:
Start at vertex F and end at vertex E.
Start at vertex E and end at vertex B.
Start at vertex E and end at vertex B.
Start at vertex X and end at vertex V.
Start at vertex T and end at vertex Z.
Consider the graph which shows the time in hours taken to travel between various country towns:
Find the least amount of time needed to travel between towns P and X.
State the route that would achieve this by listing the vertices in order.
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.
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 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.
A mailman was allocated an area to deliver the mail to. The table represents the mail route and times in minutes between the houses:
Draw a graph to represent the information in the table.
Find the fastest time to cycle from house A to house E.
State the fastest route by listing the vertices in order.
| 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 rock band is planning a tour across several cities. The table represents the routes and distance between the cities at which they will be performing in kilometres:
Draw a graph to represent the information in the table.
Find the shortest distance for the rock band to travel from city A to city E.
State the shortest route by listing the vertices in order.
| 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 |