An Introduction to Graph Theory with Karima Nigmatulina
http://techtv.mit.edu/videos/1969-blossoms—taking-walks-deli vering-mail-an-introduction-to-graph-theory-with-karima-nigmatulina
Listen to and watch the first part of the video and answer these questions.
1) Which branch of maths is the speaker going to discuss?
2) Where and when was the graph theory first discussed?
3) Where was Königsberg situated?
4) How many parts of the town and how many bridges were there?
5) What was the game the citizens wanted to play?
Listen to the second part and try to fill in the missing words.
1) The mathematician who solved this problem was................
2) The first step was to figure out..................through the city.
3) Euler came with a different approach than........................
4) Euler proposed that every single landmass be represented as a .
5) Bridges would be represented by.........................
6) Lower case letters represent..............................
Seven Bridges of Königsberg
From Wikipedia, the free encyclopedia
Read the first part of the text and try to fill in the missing words.
The Seven Bridges of Königsberg is a notable historical 1..............in mathematics. Its negative
resolution by Leonhard Euler in 1735 laid the foundations of 2...............and presaged the idea of
topology.
The city of Königsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel
3..........., and included two large islands which were 4..............to each other and the mainland by
seven bridges.
The problem was to find a walk through the city that would 5...........each bridge once and only once.
The islands could not be reached by any 6..............other than the bridges, and every bridge must
have been crossed completely every time (one could not walk half way onto the bridge and then turn around and later cross the other half from the other side).
Read the second part of the text and do exercises.
1) There are some specialist terms related to graph theory. Give their explanation.
Eulerianpath ... Eulerian circuit
Vertex
Edge .. Graph
The degree of a node.
2) Decide whether these statements are T or F. Correct the false ones.
a) The shape of the graph is not important.
b) Only the number and direction of the edges matter.
c) When one enters a bridge, one must also leave it.
d) The necessary condition is that there are no nodes of odd degree.
e) Königsberg has too many nodes of odd degree.
f) Eulerian circuit exists only if the graph is connected.
Euler's analysis
Euler proved that the problem has no solution.
To start with, Euler pointed out that the choice of route inside each landmass is irrelevant. The only important feature of a route is the sequence of bridges crossed. This allowed him to reformulate the problem in abstract terms (laying the foundations of graph theory), eliminating all features except the list of land masses and the bridges connecting them. In modern terms, one replaces each land mass with an abstract "vertex" or node, and each bridge with an abstract connection, an "edge", which only
serves to record which pair of vertices (land masses) is connected by that bridge. The resulting mathematical structure is called a graph.
Since only the connection information is relevant, the shape of pictorial representations of a graph may be distorted in any way without changing the graph itself. Only the existence (or lack) of an edge between each pair of nodes is significant. For example, it does not matter whether the edges drawn are straight or curved, or whether one node is to the left or right of another.
Next, Euler observed that (except at the endpoints of the walk) whenever one enters a vertex by a bridge, one leaves the vertex by a bridge. In other words, during any walk in the graph, the number of times one enters a non-terminal vertex equals the number of times one leaves it. Now if every bridge is traversed exactly once it follows that for each land mass (except possibly for the ones chosen for the start and finish), the number of bridges touching that land mass is even (half of them, in the particular traversal, will be traversed "toward" the landmass, the other half "away" from it). However, all the four land masses in the original problem are touched by an odd number of bridges (one is touched by 5 bridges and the other three by 3). Since at most two land masses can serve as the endpoints of a putative walk, the existence of a walk traversing each bridge once leads to a contradiction.
In modern language, Euler shows that the existence of a walk in a graph which traverses each edge once depends on the degrees of the nodes. The degree of a node is the number of edges touching it. Euler's argument shows that a necessary condition for the walk of the desired form to exist is that the graph be connected and have exactly zero or two nodes of odd degree. This condition turns out also to be sufficient ~ a result stated by Euler and later proven by Carl Hierholzer. Such a walk is now called an Eulerian path or Euler walk in his honor. Further, if there are nodes of odd degree, all Eulerian paths start at one of them and end at the other. Since the graph corresponding to historical Königsberg has four nodes of odd degree, it cannot have an Eulerian path.
An alternative form of the problem asks for a path that traverses all bridges and also has the same starting and ending point. Such a walk is called an Eulerian circuit or an Euler tour. Such a circuit exists if and only if the graph is connected and there are no nodes of odd degree at all. All Eulerian circuits are also Eulerian paths, but not all paths are also circuits.
Word study.
There are some words called antonyms in the text. Can you find them?
a) left and.............. b) lack and........................
c) enter and........... d) odd and.......................
e) finish and............ f) away and......................
g) curved or
h) endpoint and