• Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month

Networks - Konigsberg Bridge Problem.

Extracts from this document...

Introduction

image07.png

  • image01.png
    Shan Goonewardenaimage00.png
  • May 25, 2008
  • Math, Grade 10
  • Networks

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.image08.png

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.

...read more.

Middle

defghijklmnop
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
  • 2
  • 2
  • 2
  • 2
  • 4
  • 4
  • 4
  • 4
  • 6
  • 4
  • 3
  • 1
  • 2
  • 5
  • 6
  • 4
  • 2
  • 4
  • 3
  • 1
  • 0
  • 1
  • 2
  • 3
  • 0
  • Traversable
  • Traversable
  • Traversable
  • Traversable
  • Traversable
  • Traversable
  • Traversable
  • Traversable
  • Traversable
  • Traversable
  • Traversable
  • Not Traversable
  • Not Traversable
  • Not Traversable
  • Not Traversable
  • Not Traversable

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.
...read more.

Conclusion

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.image03.png

image15.png

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.

image16.png

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.

...read more.

This student written piece of work is one of many that can be found in our International Baccalaureate Maths section.

Found what you're looking for?

  • Start learning 29% faster today
  • 150,000+ documents available
  • Just £6.99 a month

Not the one? Search for your essay title...
  • Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month

See related essaysSee related essays

Related International Baccalaureate Maths essays

  1. Extended Essay- Math

    Vr��B�*,:*�(c)��H�Gp�Ôg .��9�յk�j��'~fk�VÄ¿q�X-DaK� ���z��<���4$KX'Ô��aj�$Ó�k'M1��X)��Ê�$��B(r)|bE �Å%"3(���qe���#���4��!)'& )S+V9c��Ñ�R�&�Z+W�)�9FVA_"?(�Vj�#���ڤ�:e����D��"O��9+A�6D�(tm)��nF1��#�+.\I7...�"�i M�L�%K-"nrɧC�hF�J"��#�PVG�3/4'�;H� �S+ k@�qVoG�"w/(c)g�1/4&�N���...YlV��C��usqVTc���(c)S 7���["�m(g1/2:1 ��/(c)\�׿pU��ʵ�2]���" '2�D��mw�Ν;s��<���Gge�k�RÖ&"VV LH�v(c)r,����߿�8"Hm�f!VoG�+k�%��Y�ݭ޸ -Y���)���_���O�\(tm)�4k� H�$C�1/2x� |w�s"ѺM�Y��s�=W��!*���G��X���%�ÅS�r���i;Ñ��� { &O�s x�'[Z���9"�B���'�}��� PlZ�gmpb�v hU��%M@�@{�d�(6�����Q�hd A��UV �-Ò¬v+���#ZU��vz��42gųJ� ��ң��-"�s 3GZE�Hh��'Kk(c)�^�"ɱ3/4�{괳��W[�rV^'��� ��p��"FE}�*Vl X��1�x�Ö�K�NW�lL1�� �Ê9-����u ��Z�A@��e+,"Ê"'O(r)""-4��K��[x8 '�z��$VVÆkxGK�>n..."�3�Ñ�P{��G%i�"M"�E����4tHh(be=(�re� �(c)*X�×OM�:2"�A@?'B+��'D�U��u "�d:��& Z �^91 ��B��wh7�,��-,o.�n�%-�8�1/2 @Q;d!�b�kj�ר3/47v�+<b�����ڨ����X �3Ç�xh��)�.]woG����kn]+*\P�1/4�l ..."� 8"Jy'N�j�UV2� ���y� A1/2E1W,e�*_o9��-#f� Ö� /�:8OOl�o�(tm)s>�e�-Y�"0�Z��L�&�9���t�R3cÕ���]nb% gÏ$֢�,w�Ú)š@�-3/4�:6�k�U;+���(c)

  2. Mathematics (EE): Alhazen's Problem

    Nowadays, this problem is often referred to as the "Billiard Problem" because it involves locating the point on the edge of a circular billiard table at which a cue ball at a given point must be aimed in order to carom (bounce)

  • Over 160,000 pieces
    of student written work
  • Annotated by
    experienced teachers
  • Ideas and feedback to
    improve your own work