Question

A city is built on the banks of a river and some islands in the river. The map below shows the bridges connecting the various land masses. Draw a graph that models the connecting relationships in the map below. The vertices represent the land masses and the edges represent bridges connecting them. Is it possible to find a circuit through the city that uses each bridge once? If so, enter the sequence of land masses(vertices) visited, for example ABDEA. If it is not possible, enter DNE. Use Fleury's algorithm and show all work and the graph as demonstrated in class.

Answer 1

We can graph the model as:

The Fleury's algorithm start with any vertex, and then select an edge that start from this vertex and go to another vertex. Then we pick another edge that starts from the last vertex, and so on. The condition is that all the vertices in the graph are always connected to each other: that is, there is always a path to conect any two vertices.

We start with A.

We can go to C, then B, then D, then E, then A.

After this part, we are left with these edges:

As the last vertex was A, we start from there.

We go to D, then to B, then to C, then to A again and we end in E.

We are never able to go back to the vertex we start (A), so there is no possible sequence.

Answer: DNE