Königsberg Bridge Problem

 

The Königsberg bridge problem asks if the seven bridges of the city of Königsberg (left figure; Kraitchik 1942), formerly in Germany but now known as Kaliningrad and part of Russia, over the river Preger can all be traversed in a single trip without doubling back, with the additional requirement that the trip ends in the same place it began. This is equivalent to asking if the multigraph on four nodes and seven edges (right figure) has an Eulerian cycle. This problem was answered in the negative by Euler (1736), and represented the beginning of graph theory.

On a practical note, J. Kåhre observes that bridges  and  no longer exist and that  and  are now a single bridge passing above  with a stairway in the middle leading down to . Even so, there is still no Eulerian cycle on the nodes , , , and  using the modern Königsberg bridges, although there is an Eulerian path (right figure). An example Eulerian path is illustrated in the right figure above where, as a last step, the stairs from  to  can be climbed to cover not only all bridges but all steps as well.

---

REFERENCES

Biggs, N. L.; Lloyd, E. K.; and Wilson, R. J. Graph Theory 1736-1936. Oxford, England: Oxford University Press, 1976.

Bogomolny, A. "Graphs." http://www.cut-the-knot.org/do_you_know/graphs.shtml.Chartrand, G. "The Königsberg Bridge Problem: An Introduction to Eulerian Graphs." §3.1 in Introductory Graph Theory. New York: Dover, pp. 51-66, 1985.

Euler, L. "Solutio problematis ad geometriam situs pertinentis." Comment. Acad. Sci. U. Petrop. 8, 128-140, 1736.

Reprinted in Opera Omnia Series Prima, Vol. 7. pp. 1-10, 1766.

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 1-2, 1994.

Kåhre, J. "K:)nigsberg Bridges Solved." http://www.matheory.info/konigsberg/.Kraitchik, M. §8.4.1 in Mathematical Recreations. New York: W. W. Norton, pp. 209-211, 1942.

Newman, J. "Leonhard Euler and the Königsberg Bridges." Sci. Amer. 189, 66-70, 1953.

Pappas, T. "Königsberg Bridge Problem & Topology." The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra, pp. 124-125, 1989.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 192, 1990.

Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, pp. 256-259, 1999.Wilson, R. J. "An Eulerian Trail through Königsberg." J. Graph Th. 10, 265-275, 1986.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم الشؤون الطبية يقدم الخدمات الصحية والعلاجية لزائري مدينة سامراء

العتبة العباسية المقدسة تقدم خدماتها لزائري مرقد الإمامين العسكريين (عليهما السلام) في سامراء

المجمَع العلمي ووفد وزارة التربية يبحثان سبل التعاون المشترك

قسم الشؤون الفكرية يصدر العدد 192 من مجلة الرياحين للأطفال

المزيد

الآخبار الصحية

ثورة طبية.. الذكاء الاصطناعي يكشف سرطان الكلى في وقت قياسي

لتعزيز الطاقة والتغلب على التعب.. عليك بـ7 طرق بسيطة

لتحسين الهضم والتحكم في الشهية.. ما أفضل وقت لتناول التمر؟

خبراء يكشفون تأثير الاستحمام في الظلام على جودة النوم !

المزيد

الآخبار التكنلوجية

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

نظائر الهيليوم مقياس لاكتشاف رواسب الذهب.. كيف ذلك؟

الصين تطلق أول ناقلة نفط خام ذكية في العالم تعمل بالميثانول

الزمن على المريخ أسرع من الأرض.. دراسة علمية تكشف الفوارق

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength