邻居也疯狂rmvb下载:Konigsberg bridges(Seven bridges),Eulerian circuits and Eulerian path

Konigsberg bridges The Konigsberg bridge puzzle is universally acceptedas the problem that gave birth to graph theory. It was solved by the greatSwiss-born mathematician Leonhard Euler (1707—1783). The problemasked whether one could, in a single stroll, cross all seven bridges of thecity of Königsberg exactly once and return to a starting point. Followingis a sketch of the river with its two islands and seven bridges: a. State the problem as a graph problem.b. Does this problem have a solution? If you believe it does, draw such
a stroll; if you believe it does not, explain why and indicate the smallest
number of new bridges that would be required to make such a stroll
possible. Solution:
a. If we represent each of the river’s banks and each of the two islands byvertices and the bridges by edges, we will get the following graph: (This is, in fact, a multigraph, not a graph, because it has more than oneedge between the same pair of vertices. But this doesn’t matter for the issueat hand.) The question is whether there exists a path (i.e., a sequenceof adjacent vertices) in this multigraph that traverses all the edges exactlyonce and returns to a starting vertex. Such paths are called Eulerian circuits;if a path traverses all the edges exactly once but does not return toits starting vertex, it is called an Eulerian path.b. Euler proved that an Eulerian circuit exists in a connected (multi)graphif and only if all its vertices have even degrees, where the degree of a vertexis defined as the number of edges for which it is an endpoint. Also,an Eulerian path exists in a connected (multi)graph if and only if it hasexactly two vertices of odd degrees; such a path must start at one of thosetwo vertices and end at the other. Hence, for the multigraph of the puzzle,there exists neither an Eulerian circuit nor an Eulerian path becauseall its four vertices have odd degrees.If we are to be satisfied with an Eulerian path, two of the multigraph’svertices must be made even. This can be accomplished by adding one newbridge connecting the same places as the existing bridges. For example,a new bridge between the two islands would make possible, among others,the walk a − b − c − a − b − d − c − b − dIf we want a walk that returns to its starting point, all the vertices in thecorresponding multigraph must be even. Since a new bridge/edge changesthe parity of two vertices, at least two new bridges/edges will be needed.For example, here is one such “enhancement”:This would make possible a − b − c − a − b − d − c − b − d − a, amongseveral other such walks.