7.04e Route inspection: Chinese postman, pairing odd nodes

3 A local council is responsible for gritting roads. The diagram shows the length, in miles, of the roads that have to be gritted. \includegraphics[max width=\textwidth, alt={}, center]{76bccb26-f2ec-4798-bb6b-89c922f9651a-03_671_686_488_669} Total length \(= 87\) miles The gritter is based at \(A\), and must travel along all the roads, at least once, before returning to \(A\).

1. Explain why it is not possible to start from \(A\) and, by travelling along each road only once, return to \(A\).
2. Find an optimal 'Chinese postman' route around the network, starting and finishing at \(A\). State the length of your route.

4 The following network shows the times, in minutes, taken by a policeman to walk along roads connecting 12 places, \(A , B , \ldots , L\), on his beat. Each day, the policeman has to walk along each road at least once, starting and finishing at \(A\). \includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-08_1141_1313_461_360} The total of all the times in the network is 224 minutes.

1. Find the length of an optimal Chinese postman route for the policeman.
2. State the number of times that the vertex \(J\) would appear in a route corresponding to the length found in part (a).

3 The following network shows the lengths, in miles, of roads connecting nine villages, \(A , B , \ldots , I\). A delivery man lives in village \(A\) and is to drive along all the roads at least once before returning to \(A\). \includegraphics[max width=\textwidth, alt={}, center]{d666b2d9-cb14-4d29-a842-8c87f1b25dbd-06_1072_1027_548_502}

1. Find the length of an optimal Chinese postman route around the nine villages, starting and finishing at \(A\).
2. For an optimal Chinese postman route corresponding to your answer in part (a), state:
   1. the number of times village \(E\) would be visited;
   2. the number of times village \(I\) would be visited.

5 The diagram shows a network of sixteen roads on a housing estate. The number on each edge is the length, in metres, of the road. The total length of the sixteen roads is 1920 metres. \begin{figure}[h] \end{figure}

1. Chris, an ice-cream salesman, travels along each road at least once, starting and finishing at the point \(A\). Find the length of an optimal 'Chinese postman' route for Chris.
2. Pascal, a paperboy, starts at \(A\) and walks along each road at least once before finishing at \(D\). Find the length of an optimal route for Pascal.
3. Millie is to walk along all the roads at least once delivering leaflets. She can start her journey at any point and she can finish her journey at any point.
   1. Find the length of an optimal route for Millie.
   2. State the points from which Millie could start in order to achieve this optimal route.

4 The diagram opposite shows a network of roads on a housing estate. The number on each edge is the length, in metres, of the road. Joe is starting a kitchen-fitting business.

1. Joe delivers leaflets advertising his business. He walks along all of the roads at least once, starting and finishing at \(C\). Find the length of an optimal Chinese postman route for Joe.
2. Joe gets a job fitting a kitchen in a house at \(T\). Joe starts from \(C\) and wishes to drive to \(T\). Use Dijkstra's algorithm on the diagram opposite to find the minimum distance to drive from \(C\) to \(T\). State the corresponding route. \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-08_1791_1705_916_155}
   (b) \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-09_2395_1602_312_260}

5 A council is responsible for gritting main roads in a district. The network shows the main roads in the district. The number on each edge shows the length of the road, in kilometres. The gritter starts from the depot located at point \(A\), and must drive along all the roads at least once before returning to the depot. \includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-10_1294_923_525_555}

1. Find the length of an optimal Chinese postman route around the main roads in the district, starting and finishing at \(A\).
2. Zac, a supervisor, wishes to inspect all the roads. He leaves the depot, located at point \(A\), and drives along all the roads at least once before finishing at his home, located at point \(C\). Find the length of an optimal route for Zac.
3. Liz, a reporter, intends to drive along all the roads at least once in order to report on driving conditions. She can start her journey at any point and can finish her journey at any point.
   1. Find the length of an optimal route for Liz.
   2. State the points from which Liz could start in order to achieve this optimal route.
      \includegraphics[max width=\textwidth, alt={}]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-11_2486_1714_221_153}

5 The network below shows some streets in a town. The number on each edge shows the length of that street, in metres. Leaflets are to be distributed by a restaurant owner, Tony, from his restaurant located at vertex \(B\). Tony must start from his restaurant, walk along all the streets at least once, before returning to his restaurant. \includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-10_643_1353_625_340} The total length of the streets is 2430 metres.

1. Find the length of an optimal Chinese postman route for Tony.
2. Colin also wishes to distribute some leaflets. He starts from his house at \(H\), walks along all the streets at least once, before finishing at the restaurant at \(B\). Colin wishes to walk the minimum distance. Find the length of an optimal route for Colin.
3. David also walks along all the streets at least once. He can start at any vertex and finish at any vertex. David also wishes to walk the minimum distance.
   1. Find the length of an optimal route for David.
   2. State the vertices from which David could start in order to achieve this optimal route.

5 The network on the page opposite shows the times, in minutes, taken by police cars to drive along roads connecting 12 places, \(A , B , \ldots , L\). On a particular day, there are three police cars in the area at \(A , E\) and \(J\). There is an emergency at \(G\) and all three police cars drive to \(G\).

1. 1. Use Dijkstra's algorithm on the network, starting from \(\boldsymbol { G }\), to find the minimum driving time for each of the police cars to arrive at \(G\).
   2. For each of the police cars, write down the route corresponding to the minimum driving time in your answer to part (a)(i).
2. Each day, a police car has to drive along each road at least once, starting and finishing at \(A\). For an optimal Chinese postman route:
   1. find the driving time for the police car;
   2. state the number of times that the vertex \(B\) would appear.
      \includegraphics[max width=\textwidth, alt={}]{77c4efd4-a905-48f3-a6f7-36b0e47dbc6d-13_2486_1709_221_153}

7 [Answer this question on the insert provided.]
The network below represents a simplified map of the centre of a small town. The arcs represent roads and the weights on the arcs represent distances, in units of 100 metres. \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-06_725_1259_495_443}

1. 1. Use Dijkstra's algorithm on the diagram in the insert to find the length of the shortest route from \(A\) to each of the other vertices. You must show your working, including temporary labels, permanent labels and the order in which the permanent labels were assigned. State the shortest route from \(A\) to \(E\) and the shortest route from \(A\) to \(J\), and give their lengths. [7]
   2. The shortest route from \(E\) to \(J\) that passes through every vertex can be treated as being made up of two parts, one from \(E\) to \(A\) and the other from \(A\) to \(J\). Use your answers to part (i) to write down the length of the shortest such route. List the vertices in the order that they are visited in travelling from \(E\) to \(J\) using this route.
   3. Explain why a similar approach to that used in parts (a)(i) and (a)(ii) would not give the shortest route between \(G\) and \(H\) that passes through every vertex.
2. By considering pairings of odd nodes, find the length of the shortest route that starts at \(A\) and ends at \(E\) and uses every arc at least once. \section*{OXFORD CAMBRIDGE AND RSA EXAMINATIONS} Advanced Subsidiary General Certificate of Education Advanced General Certificate of Education MATHEMATICS
   4736
   Decision Mathematics 1
   INSERT for Questions 4 and 7
   Wednesday

6 The network represents a railway system. The vertices represent the stations and the arcs represent the tracks. The weights on the arcs represent journey times between stations, in minutes. The sum of all the weights is 105 minutes. \includegraphics[max width=\textwidth, alt={}, center]{8f17020a-14bf-4459-9241-1807b954a629-5_981_1215_468_477} Norah wants to travel around the system visiting every station. She wants to start and end at \(A\) and she wants to complete her journey in the shortest possible time.

1. Apply the nearest neighbour method starting at \(A\) to find two suitable tours and calculate the journey time for each of these tours. Which of these answers gives the better upper bound for Norah's journey time?
2. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting vertex \(G\) and all the arcs that are directly joined to \(G\). Draw a diagram to show the arcs in your tree. Hence calculate a lower bound for Norah's journey time. Norah now decides that she wants to use every section of track in her journey. She still wants to start and end at \(A\) and to complete her journey in the shortest possible time.
3. Calculate the journey time for Norah's new problem. Show your working; quickest times between stations may be found by inspection. State which arcs Norah will have to travel twice and how many times she will pass through station \(D\).

1 In the network below, the arcs represent the roads in Ayton, the vertices represent roundabouts, and the arc weights show the number of traffic lights on each road. Sam is an evening class student at Ayton Academy ( \(A\) ). She wants to drive from the academy to her home ( \(H\) ). Sam hates waiting at traffic lights so she wants to find the route for which the number of traffic lights is a minimum. \includegraphics[max width=\textwidth, alt={}, center]{bb7fb141-ef42-42af-b052-d8e20d6e5157-02_786_1097_482_523}

1. Apply Dijkstra's algorithm to find the route that Sam should use to travel from \(A\) to \(H\). At each vertex, show the temporary labels, the permanent label and the order of permanent labelling. In the daytime, Sam works for the highways department. After an electrical storm, the highways department wants to check that all the traffic lights are working. Sam is sent from the depot ( \(D\) ) to drive along every road and return to the depot. Sam needs to pass every traffic light, but wants to repeat as few as possible.
2. Find the minimum number of traffic lights that must be repeated. Show your working. Suppose, instead, that Sam wants to start at the depot, drive along every road and end at her home, passing every traffic light but repeating as few as possible.
3. Find a route on which the minimum number of traffic lights must be repeated. Explain your reasoning.

3 The total weight of the arcs in the network below is 230 . \includegraphics[max width=\textwidth, alt={}, center]{012e87d3-d157-485c-a8bc-2c59c0862f87-3_545_1394_310_331}

1. Apply Dijkstra's algorithm to the copy of the network in the answer book to find the least weight path from \(A\) to \(H\). Give the path and its weight. In the remainder of this question, any least weight paths required may be found without using a formal algorithm.
2. The arc \(A D\) is removed. Apply the route inspection algorithm, showing your working, to find the weight of the least weight closed route that uses every arc (except \(A D\) ) at least once.
3. Suppose, instead, that the arc \(A D\) is available, but \(\operatorname { arcs } A C\) and \(C D\) are both removed. Apply the route inspection algorithm, showing your working, to find the weight of the least weight closed route that uses every arc (except \(A C\) and \(C D\) ) at least once.

4 [Answer this question on the insert provided.] \includegraphics[max width=\textwidth, alt={}, center]{9aa57bb0-3d88-4858-a348-ff95592fa659-3_918_1242_351_443} In this network the vertices represent towns, the arcs represent roads and the weights on the arcs show the lengths of roads in kilometres.

1. Use Dijkstra's algorithm on the diagram in the insert to find the length of the shortest path from \(A\) to each of the other vertices. You must show your working, including temporary labels, permanent labels and the order in which the permanent labels were assigned. Find the route of the shortest path from \(A\) to \(G\). The total weight of the arcs is 120 kilometres.
2. By using an appropriate algorithm, find the length of a shortest route that uses every road starting and ending at \(A\). You should explain your method.
3. Find the length of a shortest route that uses every road starting at \(A\) and ending at \(G\). You should explain your method.

4 The network below represents a small village. The arcs represent the streets and the weights on the arcs represent distances in km . \includegraphics[max width=\textwidth, alt={}, center]{7ca6d572-d776-4ad7-a0ed-9ec43c975585-04_503_1179_324_482}

1. Use Dijkstra's algorithm to find the shortest path from \(A\) to \(G\). You must show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Write down the route of the shortest path from \(A\) to \(G\). Hannah wants to deliver newsletters along every street; she will start and end at \(A\).
2. Which standard network problem does Hannah need to solve to find the shortest route that uses every arc? The total weight of all the arcs is 3.7 km .
3. Hannah knows that she will need to travel \(A B\) and \(E F\) twice, once in each direction. With this information, use an appropriate algorithm to find the length of the shortest route that Hannah can use. Show all your working. (You may find the lengths of shortest paths between vertices by inspection.) There are street name signs at each vertex except for \(A\) and \(E\). Hannah's friend Peter wants to check that the signs have not been vandalised. He will start and end at \(B\). The table below shows the complete set of shortest distances between vertices \(B , C , D , F\) and \(G\).

   	\(B\)	\(C\)	\(D\)	\(F\)	\(G\)
   \(B\)	-	0.2	0.1	0.3	0.75
   \(C\)	0.2	-	0.3	0.5	0.95
   \(D\)	0.1	0.3	-	0.2	0.65
   \(F\)	0.3	0.5	0.2	-	0.45
   \(G\)	0.75	0.95	0.65	0.45	-

4. Apply the nearest neighbour method to this table, starting from \(B\), to find an upper bound for the distance that Peter must travel.
5. Apply Prim's algorithm to the matrix formed by deleting the row and column for vertex \(G\) from the table. Start building your tree at vertex \(B\). Draw your tree. Give the order in which vertices are built into your tree and calculate the total weight of your tree. Hence find a lower bound for the distance that Peter must travel.

6 The arcs in the network represent the tracks in a forest. The weights on the arcs represent distances in km . \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-7_535_1267_395_440} Richard wants to walk along every track in the forest. The total weight of the arcs is \(26.7 + x\).

1. Find, in terms of \(x\), the length of the shortest route that Richard could use to walk along every track, starting at \(A\) and ending at \(G\). Show all of your working.
2. Now suppose that Richard wants to find the length of the shortest route that he could use to walk along every track, starting and ending at \(A\). Show that for \(x \leqslant 1.8\) this route has length \(( 32.4 + 2 x ) \mathrm { km }\), and for \(x \geqslant 1.8\) it has length \(( 34.2 + x ) \mathrm { km }\). Whenever two tracks join there is an information board for visitors to the forest. Shauna wants to check that the information boards have not been vandalised. She wants to find the length of the shortest possible route that starts and ends at \(A\), passing through every vertex at least once. Consider first the case when \(x\) is less than 3.2.
3. (a) Apply Prim's algorithm to the network, starting from vertex \(A\), to find a minimum spanning tree. Draw the minimum spanning tree and state its total weight. Explain why the solution to Shauna's problem must be longer than this.
   (b) Use the nearest neighbour strategy, starting from vertex \(A\), and show that it stalls before it has visited every vertex. Now consider the case when \(x\) is greater than 3.2 but less than 4.6.
4. (a) Draw the minimum spanning tree and state its total weight.
   (b) Use the nearest neighbour strategy, starting from vertex \(A\), to find a route from \(A\) to \(G\) passing through each vertex once. Write down the route obtained and its total weight. Show how a shortcut can give a shorter route from \(A\) to \(G\) passing through each vertex. Hence, explaining your method, find an upper bound for Shauna's problem.

5 Jess and Henry are out shopping. The network represents the main routes between shops in a shopping arcade. The arcs represent pathways and escalators, the vertices represent some of the shops and the weights on the arcs represent distances in metres. \includegraphics[max width=\textwidth, alt={}, center]{ccb12789-cd5f-40dc-9f10-f8bb45399580-6_586_1084_367_495} The total weight of all the arcs is 1200 metres.
The table below shows the shortest distances between vertices; some of these are indirect distances.

1. Use a standard algorithm to find the shortest distance that Jess must travel to cover every arc in the original network, starting and ending at \(M\).
2. Find the shortest distance that Jess must travel if she just wants to cover every arc, but does not mind where she starts and where she finishes. Which two points are her start and finish? Henry suggests that Jess only needs to visit each shop.
3. Apply the nearest neighbour method to the network, starting at \(M\), to write down a closed tour through all the vertices. Calculate the weight of this tour. What does this value tell you about the length of the shortest closed route that passes through every vertex? Henry thinks that Jess does not need to visit shop \(W\). He uses the table of shortest distances to list all the possible connections between \(M , N , P , R , S\) and \(V\) by increasing order of weight. Henry's list is given in your answer book.
4. Use Kruskal's algorithm on Henry's list to find a minimum spanning tree for \(M , N , P , R , S , T\) and \(V\). Draw the tree and calculate its total weight. Jess insists that they must include shop \(W\).
5. Use the weight of the minimum spanning tree for \(M , N , P , R , S , T\) and \(V\), and the table of shortest distances, to find a lower bound for the length of the shortest closed route that passes through all eight vertices.

5 This question uses the same network as question 4. The total weight of the arcs in the network is 224. \includegraphics[max width=\textwidth, alt={}, center]{dbefedb2-b398-45e8-92eb-eb510ff16def-5_618_1415_310_319}

1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest route from \(A\) to \(G\).
2. Dijkstra's algorithm has quadratic order (order \(n ^ { 2 }\) ). It takes 2.25 seconds for a certain computer to apply Dijkstra's algorithm to a network with 7 vertices. Calculate approximately how many hours it will take to apply Dijkstra's algorithm to a network with 1400 vertices.
3. How much shorter would the path \(C E\) need to be for it to become part of a shortest path from \(A\) to \(G\) ? Following a landslip, the paths \(A C\) and \(C E\) become blocked and cannot be used. A warden needs to travel along all the remaining paths to check that there are no more landslips.
4. Find the shortest distance that the warden must travel, assuming that she starts and ends at vertex \(C\). Show your working.

4 The network below represents a treasure trail. The arcs represent paths and the weights show distances in units of 100 metres. The total length of the paths shown is 4200 metres. \includegraphics[max width=\textwidth, alt={}, center]{cdad4fbe-4b94-4c8f-bb42-24d20eeaab4d-4_681_1157_450_459}

1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest distance (in metres) from \(A\) to each of the other vertices. Alex wants to hunt for the treasure. His current location is marked on the network as \(A\). The clues to the location of the treasure are located on the paths. Every path has at least one clue and some paths have more than one. This means that Alex will need to search along the full length of every path to find all the clues.
2. Showing your working, find the length of the shortest route that Alex can take, starting and ending at \(A\), to find every clue. The clues tell Alex that the treasure is located at the point marked as \(H\) on the network.
3. Write down the shortest route from \(A\) to \(H\). Zac also starts at \(A\) and searches along every path to find the clues. He also uses a shortest route to do this, but without returning to \(A\). Instead he proceeds directly to the treasure at \(H\).
4. Calculate the length of the shortest route that Zac can take to search for all the clues and reach the treasure.

5 The network below represents the streets in a small village. The weights on the arcs show distances in metres. The total length of all the streets shown is 2200 metres. \includegraphics[max width=\textwidth, alt={}, center]{372c062a-793f-4fb8-a769-957479f5fce7-07_499_1264_367_402}

1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest route from \(A\) to \(H\).
2. Write down the shortest route from \(A\) to \(E\) and the shortest route from \(A\) to \(G\). Sheng-Li needs to travel along every street to deliver leaflets. He will start and finish at \(A\).
3. Explain why Sheng-Li will need to repeat some streets.
4. Showing your working, find the length of the shortest route that Sheng-Li can take, starting and ending at \(A\), to deliver leaflets to every street. The streets have houses on both sides. Sheng-Li does not want to keep crossing the streets from one side to the other. His friend Nadia offers to help him. They decide that they will work together and set off from \(A\), with Sheng-Li delivering to one side of \(A B\) and Nadia delivering to the other side. Each street will have to be travelled along twice, either by both of them travelling along it once or by one of them travelling along it twice. Nadia and Sheng-Li travel \(A - B - C - E\). At this point Sheng-Li is called back to \(A\). He travels along \(E - C - A\), delivering leaflets on one side of \(C A\). Nadia completes the leaflet delivery on her own.
5. Calculate the minimum distance that Nadia will need to travel on her own to complete the delivery. Explain how your answer was achieved and how you know that it is the minimum possible distance.
   [0pt] [4]

6 [Answer part (i) of this question on the insert provided.]
The diagram shows a simplified version of an orienteering course. The vertices represent checkpoints and the weights on the arcs show the travel times between checkpoints, in minutes. \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-4_483_931_461_630}

1. Use Dijkstra's algorithm, starting from checkpoint \(\boldsymbol { A }\), to find the least travel time from \(A\) to \(D\). You must show your working, including temporary labels, permanent labels and the order in which permanent labels were assigned. Give the route that takes the least time from \(A\) to \(D\).
2. By using an appropriate algorithm, find the least time needed to travel every arc in the diagram starting and ending at \(A\). You should show your method clearly.
3. Starting from \(A\), apply the nearest neighbour algorithm to the diagram to find a cycle that visits every checkpoint. Use your solution to find a path that visits every checkpoint, starting from \(A\) and finishing at \(D\).

5. A clothes manufacturer has a trademark "VE" which it wants to embroider on all its garments. The stitching must be done continuously but stitching along the same line twice is allowed. Logo 1: \includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-06_524_1338_495_296} Logo 2: \begin{figure}[h] \end{figure} The weighted networks in Figure 4 represent two possible Logos.
The weights denote lengths in millimetres.

1. Calculate the shortest length of stitch required to embroider Logo 1 .
2. Calculate the shortest length of stitch required to embroider Logo 2.
3. Hence, determine the difference in the length of stitching required for the two Logos.

5. \begin{figure}[h] \end{figure} The network in Figure 2 represents the streets near Randolph Square in Newtown, Edinburgh. The weightings represent the average time, in seconds, taken to travel along each road in either direction. The large values for the roads \(C D\) and \(J L\) are due to traffic lights. In the course of his work, a van driver must travel along each road at least once each day. He starts and finishes at his depot, \(F\), and wishes to minimise the total time that this takes.

1. Describe an appropriate algorithm that can be used to find this minimum time.
   (3 marks)
2. Apply this algorithm to find a route that the driver can take and state the total time he can expect to spend on this journey each day.
   (5 marks)
   The section of road \(A B\) is to be turned into a pedestrian precinct.
3. Assuming that the driver must still travel along all the other roads at least once each day, find the modified time he can expect to spend on his daily journey Comment on your answer.
   (3 marks)

5. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 2 shows a weighted network representing the paths in a certain part of St. Andrews. The numbers on the arcs represent the lengths of the paths in metres.

1. Use Dijkstra's algorithm to find a route of minimum length from \(P\) to \(F\). You do not need to consider routes via vertex \(Q\). You must show clearly:
   1. the order in which you labelled the vertices,
   2. how you found a route of minimum length from your labelling. Each night a security guard walks along each of the paths in Figure 2 at least once.
2. The security office is at vertex \(A\), so she must start and finish her inspection at \(A\). Find the minimum distance that she must walk each night.
   (4 marks)

4

1. When investigating three network flow problems, a student finds:
   1. a flow of 50 and a cut with capacity 50 ;
   2. a flow of 35 and a cut with capacity 50 ;
   3. a flow of 50 and a cut with capacity 35 . In each case, write down what the student can deduce about the maximum flow.
2. The diagram below shows a network. The numbers on the arcs represent the minimum and maximum flow along each arc respectively. By considering the flow at an appropriate vertex, explain why a flow is not possible through this network. \includegraphics[max width=\textwidth, alt={}, center]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-10_1189_1559_1105_246}
   (2 marks)

8 The network below represents a system of pipes. The capacity of each pipe, in litres per second, is indicated on the corresponding edge. \includegraphics[max width=\textwidth, alt={}, center]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-22_743_977_404_536}

1. Find the maximum flow along each of the routes \(A B E H , A C F H\) and \(A D G H\) and enter their values in the table on Figure 4 opposite.
2. 1. Taking your answers to part (a) as the initial flow, use the labelling procedure on Figure 4 to find the maximum flow through the network. You should indicate any flow-augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
   2. State the value of the maximum flow and, on Figure 5 opposite, illustrate a possible flow along each edge corresponding to this maximum flow.
3. Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4}

   Route	Flow
   \(A B E H\)
   \(A C F H\)
   \(A D G H\)

   \end{table} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-23_746_972_397_845}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-23_739_971_1311_539}
   \end{figure}
   \includegraphics[max width=\textwidth, alt={}]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-24_2253_1691_221_153}