Question

Discrete Mathematics! I need the right answer and the correct explanation. So I can learn this.

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. 1) 11-) B 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.

Answer 1

The map can be modeled with the following graph:

o 1 TTI cs cannel with CamScarler

Here the vertices represent the land masses and the edges represent the bridges. In the problem we need to find an Euler circuit which is a circuit which traverses each edge exactly once. It starts and ends at the same vertex.

For a graph to have an Euler circuit the degree of all the vertices must be even. Let's prove this. For every vertex v in the graph G, each edge having v as an end point shows up exactly once in euler circuit C. The circuit C enters v the same number of times that it leaves v(say n times), so v has degree 2n.

In the above graph every vertex has an even degree so the euler circuit exists.

An Euler Circuit in the above graph will be:

ACAEABCBEDBDA

It can be observed that the circuit starts and ends at vertex A.

Hope this helped. Please do upvote and if there are any queries please ask in comments section.