advertisement

Königsberg, Euler and the origins of graph theory

33 %
67 %
advertisement
Information about Königsberg, Euler and the origins of graph theory
Education

Published on February 15, 2014

Author: pupbroeders

Source: slideshare.net

Description

A slidecast explaining the origins of graph theory and the solution to the 7 bridges problem of Königsberg. I discuss some modern applications of graph theory too.
advertisement

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Summary & further reading K¨nigsberg, Euler and the origins of graph theory o Philip Puylaert February 2014

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Summary & further reading K¨nigsberg, East Prussia o capital of East Prussia (1457–1945) Pregel river university birth place of Immanuel Kant, David Hilbert, K¨the Kollwitz a destroyed at the end of World War II

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Nowadays: Kaliningrad Applications of graph theory Summary & further reading

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Nowadays: Kaliningrad Applications of graph theory Summary & further reading

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Nowadays: Kaliningrad Applications of graph theory Summary & further reading

History of K¨nigsberg o The 7 bridges of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Summary & further reading

History of K¨nigsberg o The 7 bridges of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Summary & further reading

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Leonhard Euler Basel 1707 – St.-Petersburg 1783 professor at 20 enormously productive influence found everywhere in math and physics most famous formula: 1 + e iπ = 0 Summary & further reading

History of K¨nigsberg o The 7 bridges of K¨nigsberg o The 7 bridges problem Applications of graph theory Summary & further reading

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Summary & further reading The 7 bridges problem A B C D

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Summary & further reading The 7 bridges problem A B C Definitions graph vertices (singular: vertex) — edges order of a vertex D

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory When can you take the desired walk? 1 4 A 2 3 vertex of even order Summary & further reading

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Summary & further reading When can you take the desired walk? 1 4 A 1 2 3 A 3 2 vertex of odd order vertex of even order

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Summary & further reading When can you take the desired walk? 1 4 A 1 2 A 3 3 2 vertex of odd order vertex of even order The graph is traversable if all vertices have even order → Euler tour, a closed walk if exactly 2 vertices have odd order → use them to start and finish your walk

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Examples of traversable graphs The graph is traversable if all vertices have even order → Euler tour, a closed walk if exactly 2 vertices have odd order → use them to start and finish your walk A 1 3 C 2 B Summary & further reading

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Summary & further reading Examples of traversable graphs The graph is traversable if all vertices have even order → Euler tour, a closed walk if exactly 2 vertices have odd order → use them to start and finish your walk A 1 3 C 2 1 B 4 A 5 2 D 3 C B

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Back to the 7 bridges problem A B C D Summary & further reading

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Summary & further reading Back to the 7 bridges problem the order of A is 3 A the order of B is 4 the order of C is 3 the order of D is 3 B C D

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Summary & further reading Back to the 7 bridges problem the order of A is 3 A the order of B is 4 the order of C is 3 the order of D is 3 B D C Conclusion The graph of the 7 bridges problem is not traversable. It’s impossible to take a walk crossing every bridge exactly once.

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Application 1: traffic Applications of graph theory Summary & further reading

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Application 2: social networks Applications of graph theory Summary & further reading

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Application 2: social networks Applications of graph theory Summary & further reading

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Summary & further reading Application 3: ranking of search results by Google each vertex represents a web page arrow D → A means: page D contains a link to page A

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Summary & further reading Summary What have you learned in this slidecast? basic concepts of graph theory: graph, vertex, edge, order of a vertex you and Euler solved the 7 bridges problem by proving when a graph is traversable the K¨nigsberg graph is not traversable o some applications of graph theory, e.g. traffic, social networks

History of K¨nigsberg o The 7 bridges of K¨nigsberg o Applications of graph theory Summary & further reading More information? Reinhard Diestel, Graph Theory (3rd edition), Springer Verlag, 2005 www.math.ubc.ca/~solymosi/2007/443/GraphTheoryIII.pdf Fred Buckley, A Friendly Introduction to Graph Theory, Prentice Hall, 2002 Glen Gray, Graph Theory 1 — Intro via Konigsberg Bridge www.youtube.com/watch?v=BK kYjFWWX0

Add a comment

Related presentations

Related pages

Königsberg, Euler and the origins of graph theory - Education

A slidecast explaining the origins of graph theory and the solution to the 7 bridges problem of Königsberg. I discuss some modern applications of graph ...
Read more

Graph Theory Origin and Seven Bridges of Königsberg ...

Graph Theory Origin and ... field of graph theory. He created first graph to ... to make the graph created from bridges of Königsberg, a Euler ...
Read more

Königsberg, Euler and the origins of graph theory - Education

Home; Education; Königsberg, Euler and the origins of graph theory; of 25 ×
Read more

Euler and the Königsberg Bridge Problem - Graph Theory History

Sharing the wonders of graph theory throughout history ... Euler and the Königsberg Bridge Problem. Hamilton and the Icosian Game. The Four Color Problem.
Read more

Early Writings on Graph Theory: Euler Circuits and The K ...

Yet from such deceptively frivolous origins, graph theory has grown into a powerful and ... ‘Euler circuit’ to a modern proof of the main result of the ...
Read more

Graph Theory/Introduction - Wikibooks, open books for an ...

Graph Theory /Introduction. From ... Map of Königsberg in Euler's time showing the actual ... Since the graph corresponding to historical Königsberg has ...
Read more

Seven Bridges of Königsberg - Wikipedia, the free encyclopedia

The Seven Bridges of Königsberg is a ... there are five bridges in Kaliningrad that were a part of the Euler's problem. In terms of graph theory, ...
Read more

Königsberg Bridge Problem -- from Wolfram MathWorld

The Königsberg bridge problem asks if the seven bridges ... and represented the beginning of graph theory. ... J. "Leonhard Euler and the Königsberg ...
Read more

Graph Theory - Google Slides

... graph theory is the study of graphs, ... Euler's formulation with ... and faces of a convex polyhedron was studied and generalized by others and is at ...
Read more