From Puzzles to Programming

1. Suppose you have 4 islands connected with bridges as shown in the figure below.

 

Would you be able to visit each of these islands in a way that you cross each bridge only once and return to home island (the starting point island)?

Answer

It is not possible. There are 3 bridges connected to each island. Once you reach an island from an entry bridge, you have to exit it from another bridge. There will be one bridge remaining to connect the island with the rest of islands. If you reenter the island through this remaining bridge, it is not possible to exit the island again without crossing any of the 3 bridges as they have already been used.

 

2. If there are 5 islands, would you be able to cross each bridge only once to visit the islands and return back to home island?

Answer

It is possible. One path is (AB,BC,CA,AD,DB,BE,EC,CD,DE,EA) The number of bridges per each island is 4. This is an even number. Any time you reach the island by an entry bridge then you can get out of it by an exit bridge.

If the number of bridges connecting an island is even, then there will be solution for the problem. If it is an odd number then there will be no solution for the problem. This is in accordance to "Euler Circuit" which necessitate that all vertices must have an even degree (the degree of a vertex is the number of edges connected to that vertex).

 

4. Find a path for the edges of the figure below in such a way that each edge is passed only once.

 

First, does the graph satisfy Eulerian circuit principle? Answer is No since there are vertices B and C each of which has an uneven degree (each of B and C is connected by 3 edges). In this question, however, we are not concerned in going back to the starting vertex. Hence, One possible path is (bc, ca, ad, de, ea, ab, bd, dc) as shown below. Here all edges are passed each once but the initial vertex is B while the final vertex is C.

 

On the contrary, there is no path to cross each edge exactly once in the graph below:

 

5. In the connected cities (a,b,c,d, and e), can you find a closed path that visit each city exactly once, and return back to the home city?

Answer

Note that in this question, we are concerned in visiting each city only once regardless of the number of times you go through the bridges or connections. A bridge ( or edge) may not be visited at all. In this graph, there is no such path because city "e" has to be visited at least two times in any path you make to visit all the cities. Finding a closed path that uses every vertex (city) of the graph exactly once, except for the last vertex, which duplicates the first vertex is called a Hamilton Circuit.

However, note that the above graph does have an Euler circuit.

Some graphs can have many Hamilton circuits and no Euler circuit. Examples:

 

 

 

6. In the figure below, the numbers represent distances between cities. Connect these cities by pipelines using the minimum number of pipelines.

 

Answer

One way is to arrange the distances (the weights) from the lowest to the highest. This will be e1, e2, e3, e4, e5, e6, e7, and e8. Then select the edges with these distances in order and we reject any edge that makes a cycle. For example, as we go in order, e1, e2, e3, e4 are selected but e5 is rejected because it make a cycle with e2 and e4. In the same way, e7, and e8 are rejected.

The graph with this "minimal path" will look like:

 

 

 

 

                            The famous network of the Kdnigsberg bridges. The nodes of the network represent the land; the edges (lines) represent the bridges.

 

The Koniigsberg bridges problem was Euler’s first theorem in topology—indeed, the world’s first. Euler showed that for any drawn graph on a flat surface, if V is the total number of nodes), if E is the total number of edges (or connect) and if F is the total number of “faces” (i.e., regions formed or enclosed by two or more edges), then the following simple formula V—E+F=1

In Euler’s own network for the Konigsberg bridges V=4,  E=7, and F= 4, so V—E+F = 4—7+4=1

 

The Proof:

If you are eliminating a terminal node (a node connected with only one edge) then V decreases by 1 and E decreases by 1 and the V-E+F remains the same. If you eliminate an edge of a closed loop (an edge not going to a terminal node) then you are loosing also one face i.e. both E and F are decreasing by 1 and the value of V-E+F remains the same. You keep removing edge or terminal node until you reach last edge connected by 2 points. Removing that edge makes the V-E+F = 2-1+0 = 1. But the value of V-E+F was the same through out the process.

Hence, V-E+F = 1