Networks - Konigsberg Bridge Problem.
- May 25, 2008
- Math, Grade 10
In the country of Germany, the river Pregel divides the town of Kaliningrad into four separate land masses, A, B, C, and D. Seven bridges connect the various parts of town, and the problems is if it is possible to take a journey across all seven bridges without having to cross any bridge more than once, mathematical we are trying to find if this network is traversable or not. On the right side is a diagram of the situation and the dotted letters are the four zones, mathematically referred as nodes (I will talk about this later on). To overcome this problem, I not only going to find the solution to this problem but also state a rule, which will tell if a network is traversable or not.
The worksheet helped me a lot in solving this problem and basically the worksheet consisted of three parts. Firstly, the worksheet provides a list of networks and we asked to find if the networks as traversable or not. With these results, we had to create a table with the number of even and odd nodes, which is very important. A Node is a point in a network at which lines intersect or branch.
For example: This network has nine nodes (the dots) but
it has 5 even nodes and 4 odd nodes, because for each
node, there is a different number of lines intersecting. When we find the number lines branching out of each
node, we count all the even numbers as 1 so in this case, 5
even nodes and the same for the odd nodes. Now that you
know a thing about nodes, let me continue with the explanation of worksheet.
After you fill in the table, we are left to find a pattern in the table and the importance of even and odd nodes are very essential at that stage. Then in the second part, we test out our rule or check if we have to start with an even or odd node. All these will be better explained when I tell what the rule is. And finally in the third section, there is another map of the bridges in Kaliningrad except with two more bridges across the Pregel. For this part, I have to apply my rule and tell if the network is traversable.
This is a preview of the whole essay
For the first part, the table was the most beneficial but the networks provided the information, which was later added to my table. I didn’t know the rule at first so to check if the network is traversable, I drew the whole network in one movement, without lifting the writing utensil and also without going over the same part twice. At first, I didn’t get the point of the nodes but I was wrong, the nodes are pretty much the focal point of the rule.
Below are the networks, which were asked if traversable.
The networks from letters a to k were traversable and the remaining weren’t. After I counted the even and odd nodes, I put it in the table and there was a very distinct pattern in these results.
Above is the table with the nodes and if the network is traversable.
- From the table, I found out that when a network if traversable, then the network has two odd nodes or less (it is not possible to has one odd node). The even nodes should be greater if the network there are zero odd nodes and it doesn't matter if there are 2 odd nodes because it automatically qualifies as a traversable network. So basically, the odd nodes tells if the network is traversable or not.
- When traversing a network, the nodes at which you must start with are very important. If the network had only even nodes, then you can start from any node you want to. But, if the network has any odd nodes and if you know its traversable, then you must start with an odd node.
- Here are some examples, where I will apply both of these rules:
- a. This network has all even nodes with zero odd nodes, so the network would be traversable. Since it had more even nodes than odd nodes and the odd nodes were less than two, the network became traversable. This network can be traversed with any node because as i mentioned before, if it has only even nodes, then it doesn't matter at which node you start at.
- b. This network has two odd nodes and two even nodes, so this network would be traversable. Since it has two odd nodes, the network is traversable. The network can only be traversable if started with an odd node because as I mentioned before, if the network has odd nodes and it is traversable, then you have to start at an odd node.
- c. This network has eight odd nodes and one even node, which will make this network not traversable. There are more odd nodes than even nodes and in my rule; it says the odd nodes must be less than two, which in this case are eight so that is definitely not traversable.
In the second part of the worksheet, they have given me networks, which are traversable but asked me for each network at which node to start.
- Below are the networks.
These ones have to be started by the odd nodes, because there are odd nodes in the network and they are traversable.
- Any even nodes can start this network because this network has only even nodes.
For the third part, the new map looked familiar but it had two extra bridges. The question asked if this network is traversable and to answer this problem, I first had to create a network with all the nodes attached . The problem got so much easier after the network was completed, it had two odd nodes and two even nodes and by this I know the network is traversable. But it is only possible, if you start at an odd node, on this case, letters B and C. Below are diagrams to better explain the problem.
So, from the worksheet, I found a rule which allows me to find if a network is traversable or not and I also found out that there is a particular node to start at when traversing the network. The rule is when a network is traversable, then there are two or less odd nodes and if the odd nodes are less than two then there should be more even nodes. When traversing a network a network, and all the nodes are even, it doesn't matter at which even node you start at but if it is traversable and it has odd nodes, then you must start at the odd nodes or else it won't work. This is what learned out of this worksheet.
These results can help me solve the original problem because using the rule I can tell if the original problem is traversable. I will first have to draw a network for the problem and then find how many even and odd nodes there are and then I can find out if the network is traversable or not.
- Below is the network for the Konigsberg Bridge Problem.
The network has zero even nodes and four odd nodes and the Konigsberg Bridge is not traversable and a solution for this problem without changing or adding bridges is impossible. Since there are more odd nodes than even nodes, the network will not new traversable and so if the network were to be traversable, you would have to add some bridges or change the network like the nine bridges over the Pregel, in the worksheet. If there were nine bridges instead of seven, it would have been traversable. I am now going to give two networks, which will be traversable by adding or removing bridges.
Below are the two networks with a map for the extensions of the original problem
1. This network is traversable because it has two odd nodes and two even nodes, which make it traversable. The original network became traversable by just adding one more bridge and this bridge balance the even and odd nodes. The diagram of the network and the map are below. The network will be travered with any of the 2 odd nodes.
2. The second network is also traversable by just removing one bridge to the original network. And this networks is traversable because like the first one, it has two odd nodes and one even node. But the network has to be started with an odd node to be traversable. Since there are two odd nodes, the new network is traversable. The network and the map are below.
It is impossible to have a solution to the original problem if it is not possible to add or remove bridges. I learned a lot from this report and also found rules by looking at patterns and at first trying out a lot of networks, but know I can use the rule and it so much more simpler. Even though the original problem was impossible, I enjoyed doing this problem because it allowed me to go further into and traversable networks.