The site below will provide additional information regarding the Konigsberg Bridge Problem. The problem is described from the perspective of Euler. You will also find an applet that you can use to experiment with some basic concepts of Network Analysis (print and complete the worksheet below). You may enjoy looking at other puzzles that may be accessed through the attached links. Solutions to each of these puzzles can be related to network analysis.
http://www.cut-the-knot.com/do_you_know/graphs.htm
NAME:__________________________
PART I
Using the applet from the website or by hand using paper and pencil, draw the network and fill in the table below.
Draw cycles of order 3, order 4, order 5 and order 6.
| Order | Edges (Links) |
| 3 | _ |
| 4 | _ |
| 5 | _ |
| 6 | _ |
How many edges (links) do you think a cycle of order 7 will have?
Find a general rule that gives the number of edges(links) for a cycle
of order n.
PART II
Using the applet from the website or by hand using paper and pencil, draw the network and fill in the table below.
Draw complete networks of order 3, order 4, order 5, order 6.
| Order | Edges (Links) | Vertex Degree | Total Degrees |
| 3 | _ | _ | _ |
| 4 | _ | _ | _ |
| 5 | _ | _ | _ |
| 6 | _ | _ | _ |
Which of these complete networks contain Euler Circuits? Why?
Find a pattern for the number of edges as a function of the order of
the complete network and predict the number of edges for a complete network
of order 7, 8, and 9.
Can you figure out a formula that can be used to find the number of
edges if the complete network is of order n?
Looking at the table, what relationship can you discover about
the number of edges in a network and the total degrees?