Euler-哥尼斯堡七桥问题
Early Writings on Graph Theory:
Euler Circuits and The K¨o nigsberg Bridge Problem
An Historical Project
Janet Heine Barnett
Colorado State University-Pueblo
Pueblo,CO81001-4901
janet.barnett@https://www.wendangku.net/doc/6516931325.html,
8December2005
In a1670letter to Christian Huygens(1629-1695),the celebrated philosopher and mathematician Gottfried W.Leibniz(1646-1716)wrote as follows:
I am not content with algebra,in that it yields neither the shortest proofs nor
the most beautiful constructions of geometry.Consequently,in view of this,I
consider that we need yet another kind of analysis,geometric or linear,which
deals directly with position,as algebra deals with magnitude.[1,p.30]
Known today as the?eld of‘topology’,Leibniz’s study of position was slow to develop as a mathematical?eld.As C.F.Gauss noted in1833,
Of the geometry of position,which Leibniz initiated and to which only two geome-
ters,Euler and Vandermonde,have given a feeble glance,we know and possess,
after a century and a half,very little more than nothing.[1,p.30]
The‘feeble glance’which Leonhard Euler(1707-1783)directed towards the geometry of position consists of a single paper now considered to be the starting point of modern graph theory in the West.Within the history of mathematics,the eighteenth century itself is
1
commonly known as‘The Age of Euler’in recognition of the tremendous contributions that Euler made to mathematics during this period.Born in Basel,Switzerland,Euler studied mathematics under Johann Bernoulli(1667-1748),then one of the leading European mathematicians of the time and among the?rst—along with his brother Jakob Bernoulli (1654-1705)—to apply the new calculus techniques developed by Leibniz in the late seventeenth century to the study of curves.Euler soon surpassed his early teacher,and made important contributions to an astounding variety of subjects,ranging from number theory and analysis to astronomy and optics to mapmaking,in addition to graph theory and topology.His work was particularly important in re-de?ning calculus as the study of analytic functions,in contrast to the seventeenth century view of calculus as the study of curves.Amazingly,nearly half of Euler’s nearly900books,papers and other works were written after he became almost totally blind in1771.
The paper we examine in this project appeared in Commentarii Academiae Scientiarum Imperialis Petropolitanae in1736.In it,Euler undertakes a mathematical formulation of the now-famous K¨o nigsberg Bridge Problem:is it possible to plan a stroll through the town of K¨o nigsberg which crosses each of the town’s seven bridges once and only once?Like other early graph theory work,the K¨o nigsberg Bridge Problem has the appearance of being little more than an interesting puzzle.Yet from such deceptively frivolous origins,graph theory has grown into a powerful and deep mathematical theory with applications in the physical,biological,and social sciences.The resolution of the Four Color Problem—one of graph theory’s most famous historical problems—has even raised new questions about the notion of mathematical proof itself.First formulated by Augustus De Morgan in a1852 letter to Hamilton,the Four Color Problem asks whether four colors are su?cient to color every planar map in such a way that regions sharing a boundary are colored in di?erent colors.After a long history of failed attempts to prove the Conjecture,Kenneth Appel(1932 -)and Wolfgang Haken(1928-)published a computer-assisted proof in1976which many mathematicians still do not accept as valid.At the heart of the issue is whether a proof that can not be directly checked by any member of the mathematical community can really be considered to be a proof.
This modern controversy highlights the historical fact that standards of proof have always varied from century to century,and from culture to culture.This project will highlight one part of this historical story by examining the di?erences in precision between an eighteenth century proof and a modern treatment of the same result.In particular,we wish to contrast Euler’s approach to the problem of?nding necessary and su?cient conditions for the exis-tence of what is now known as an‘Euler circuit’to a modern proof of the main result of the paper.
In what follows,we take our translation from[1,pp.3-8],with some portions elimi-nated in order to focus only on those most relevant to Euler’s reformulation of the‘bridge crossing problem’as a purely mathematical problem.De?nitions of modern terminology are introduced as we proceed through Euler’s paper;modern proofs of two lemmas used in the proof of the main result are also included in an appendix.
2
SOLUTIO PROBLEMATIS AD GEOMETRIAM SITUS PERTINENTIS 1In addition to that branch of geometry which is concerned with magnitudes,and which has always received the greatest attention,there is another branch,pre-
viously almost unknown,which Leibniz?rst mentioned,calling it the geometry
of position.This branch is concerned only with the determination of position
and its properties;it does not involve measurements,nor calculations made
with them.It has not yet been satisfactorily determined what kind of problems
are relevant to this geometry of position,or what methods should be used in
solving them.Hence,when a problem was recently mentioned,which seemed
geometrical but was so constructed that it did not require the measurement of
distances,nor did calculation help at all,I had no doubt that it was concerned
with the geometry of position—especially as its solution involved only position,
and no calculation was of any use.I have therefore decided to give here the
method which I have found for solving this kind of problem,as an example of
the geometry of position.
2The problem,which I am told is widely known,is as follows:in K¨o nigsberg in Prussia,there is an island A,called the Kneiphof;the river which surrounds it
is divided into two branches,as can be seen in Fig.[1.2],and these branches
are crossed by seven bridges,a,b,c,d,e,f and g.Concerning these
bridges,it was asked whether anyone could arrange a route in such a way that
he would cross each bridge once and only once.I was told that some people
asserted that this was impossible,while others were in doubt:but nobody would
actually assert that it could be done.From this,I have formulated the general
problem:whatever be the arrangement and division of the river into branches,
and however many bridges there be,can one?nd out whether or not it is possible
to cross each bridge exactly once?
[Figure1.2]
Notice that Euler begins his analysis of the‘bridge crossing’problem by?rst replacing the map of the city by a simpler diagram showing only the main feature.In modern graph theory, we simplify this diagram even further to include only points(representing land masses)and line segments(representing bridges).These points and line segments are referred to as
3
‘vertices’(singular:vertex)and‘edges’respectively.The collection of vertices and edges together with the relationships between them is called a‘graph’.More precisely,a graph consists of a set of vertices and a set of edges,where each edge may be viewed as an ordered pair of two(usually distinct)vertices.In the case where an edge connects a vertex to itself, we refer to that edge as a‘loop’.
?Question A.Sketch the diagram of a graph with5vertices and8edges to represent the following bridge problem.
3As far as the problem of the seven bridges of K¨o nigsberg is concerned,it can be solved by making an exhaustive list of all possible routes,and then?nding
whether or not any route satis?es the conditions of the problem.Because of
the number of possibilities,this method of solution would be too di?cult and
laborious,and in other problems with more bridges it would be impossible.
Moreover,if this method is followed to its conclusion,many irrelevant routes
will be found,which is the reason for the di?culty of this method.Hence I
rejected it,and looked for another method concerned only with the problem
of whether or not the speci?ed route could be found;I considered that such a
method would be much simpler.
4My whole method relies on the particularly convenient way in which the crossing of a bridge can be represented.For this I use the capital letters A,B,C,D,
for each of the land areas separated by the river.If a traveller goes from A
to B over bridge a or b,I write this as AB—where the?rst letter refers to
the area the traveller is leaving,and the second refers to the area he arrives
at after crossing the bridge.Thus,if the traveller leaves B and crosses into D
over bridge f,this crossing is represented by BD,and the two crossing AB and
BD combined I shall denote by the three letters ABD,where the middle letter
B refers to both the area which is entered in the?rst crossing and to the one
which is left in the second crossing.
5Similarly,if the traveller goes on from D to C over the bridge g,I shall represent these three successive crossings by the four letters ABDC,which should be taken
4
to mean that the traveller,starting in A,crosses to B,goes on to D,and?nally
arrives in C.Since each land area is separated from every other by a branch of
the river,the traveller must have crossed three bridges.Similarly,the successive
crossing of four bridges would be represented by?ve letters,and in general,
however many bridges the traveller crosses,his journey is denoted by a number
of letters one greater than the number of bridges.Thus the crossing of seven
bridges requires eight letters to represent it.
After rejecting the impractical strategy of solving the bridge-crossing problem by making an exhaustive list of all possible routes,notice that Euler again reformulates the problem in terms of sequences of letters(vertices)representing land masses,thereby making the diagram itself unnecessary to the solution of the problem.Today,we say that two vertices joined by an edge in the graph are‘adjacent’,and refer to a sequence of adjacent vertices as a‘walk’. Technically,a walk is a sequence of alternating(adjacent)vertices and edges v0e1v1e1...e n v n in which both the order of the vertices and the order of the edges used between adjacent vertices are speci?ed.In the case where no edge of the graph is repeated(as required in a bridge-crossing route),the walk is known as a‘path’.If the initial and terminal vertex are equal,the path is said to be a‘circuit’.If every edge of the graph is used exactly once(as desired in a bridge-crossing route),the path(circuit)is said to be a‘Euler path(circuit)’.
?Question B.For the bridge problem shown in Question A above,how many letters (representing graph vertices)will be needed to represent an Euler path?
Having reformulated the bridge crossing problem in terms of sequences of letters(ver-tices)alone,Euler now turns to the question of determining whether a given bridge crossing problem admits of a solution.As you read through Euler’s development of a procedure for deciding this question in paragraphs7-13below,pay attention to the style of argument employed,and how this di?ers from that used in a modern textbook.
7The problem is therefore reduced to?nding a sequence of eight letters,formed from the four letters A,B,C and D,in which the various pairs of letters occur
the required number of times.Before I turn to the problem of?nding such a
sequence,it would be useful to?nd out whether or not it is even possible to
arrange the letters in this way,for if it were possible to show that there is no
such arrangement,then any work directed toward?nding it would be wasted.I
have therefore tried to?nd a rule which will be useful in this case,and in others,
for determining whether or not such an arrangement can exist.
[Figure1.3]
5
8In order to try to?nd such a rule,I consider a single area A,into which there lead any number of bridges a,b,c,d,etc.(Fig.[1.3]).Let us take?rst the
single bridge a which leads into A:if a traveller crosses this bridge,he must
either have been in A before crossing,or have come into A after crossing,so
that in either case the letter A will occur once in the representation described
above.If three bridges(a,b and c,say)lead to A,and if the traveller crosses
all three,then in the representation of his journey the letter A will occur twice,
whether he starts his journey from A or not.Similarly,if?ve bridges lead to A,
the representation of a journey across all of them would have three occurrences
of the letter A.And in general,if the number of bridges is any odd number,
and if it is increased by one,then the number of occurrences of A is half of the
result.
?Question C.In paragraph8,Euler deduces a rule for determining how many times a vertex must appear in the representation of the route for a given bridge problem for the case where an odd number of bridges leads to the land mass represented by that vertex.Before reading further,use this rule to determine how many times each of the vertices A,B,C and D would appear in the representation of a route for the K¨o nigsberg Bridge Problem.Given Euler’s earlier conclusion(paragraph5)that a solution to this problem requires a sequence of8vertices,is such a sequence possible? Explain.
9In the case of the K¨o nigsberg bridges,therefore,there must be three occurrences of the letter A in the representation of the route,since?ve bridges(a,b,c,d,e)
lead to the area A.Next,since three bridges lead to B,the letter B must occur
twice;similarly,D must occur twice,and C also.So in a series of eight letters,
representing the crossing of seven bridges,the letter A must occur three times,
and the letters B,C and D twice each-but this cannot happen in a sequence
of eight letters.It follows that such a journey cannot be undertaken across the
seven bridges of K¨o nigsberg.
10It is similarly possible to tell whether a journey can be made crossing each bridge once,for any arrangement of bridges,whenever the number of bridges
leading to each area is odd.For if the sum of the number of times each letter
must occur is one more than the number of bridges,then the journey can be
made;if,however,as happened in our example,the number of occurrences is
greater than one more than the number of bridges,then such a journey can
never be accomplished.The rule which I gave for?nding the number of occur-
rences of the letter A from the number of bridges leading to the area A holds
equally whether all of the bridges come from another area B,as shown in Fig.
[1.3],or whether they come from di?erent areas,since I was considering the
6
area A alone,and trying to?nd out how many times the letter A must occur.
11If,however,the number of bridges leading to A is even,then in describing the journey one must consider whether or not the traveller starts his journey from
A;for if two bridges lead to A,and the traveller starts from A,then the letter
A must occur twice,once to represent his leaving A by one bridge,and once
to represent his returning to A by the other.If,however,the traveller starts
his journey from another area,then the letter A will only occur once;for this
one occurrence will represent both his arrival in A and his departure from there,
according to my method of representation.
12If there are four bridges leading to A,and if the traveller starts from A,then in the representation of the whole journey,the letter A must occur three times if
he is to cross each bridge once;if he begins his walk in another area,then the
letter A will occur twice.If there are six bridges leading to A,then the letter
A will occur four times if the journey starts from A,and if the traveller does
not start by leaving A,then it must occur three times.So,in general,if the
number of bridges is even,then the number of occurrences of A will be half of
this number if the journey is not started from A,and the number of occurrences
will be one greater than half the number of bridges if the journey does start at
A.
13Since one can start from only one area in any journey,I shall de?ne,correspond-ing to the number of bridges leading to each area,the number of occurrences
of the letter denoting that area to be half the number of bridges plus one,if
the number of bridges is odd,and if the number of bridges is even,to be half
of it.Then,if the total of all the occurrences is equal to the number of bridges
plus one,the required journey will be possible,and will have to start from an
area with an odd number of bridges leading to it.If,however,the total number
of letters is one less than the number of bridges plus one,then the journey is
possible starting from an area with an even number of bridges leading to it,
since the number of letters will therefore be increased by one.
Notice that Euler’s de?nition concerning‘the number of occurrences of the letter denoting that area’depends on whether the the number of bridges(edges)leading to each area(vertex) is even or odd.In contemporary terminology,the number of edges incident on a vertex V is referred to as the‘degree of vertex V’.
?Question D.Suppose v is a vertex of degree n in a graph G.State Euler’s de?nition for‘the number of occurrences of the letter denoting that area’as a function o(n) using modern https://www.wendangku.net/doc/6516931325.html,ment on how a proof that this‘de?nition’gives a correct rule in a modern textbook would di?er from the argument that Euler presents for the correctness of this rule in paragraphs9-12.
7
14So,whatever arrangement of water and bridges is given,the following method will determine whether or not it is possible to cross each of the bridges:I?rst denote by the letters A,B,C,etc.the various areas which are separated from one another by the water.I then take the total number of bridges,add one,and write the result above the working which follows.Thirdly,I write the letters A, B,C,etc.in a column,and write next to each one the number of bridges lead-ing to it.Fourthly,I indicate with an asterisk those letters which have an even number next to them.Fifthly,next to each even one I write half the number, and next to each odd one I write half the number increased by one.Sixthly,I add together these last numbers,and if this sum is one less than,or equal to, the number written above,which is the number of bridges plus one,I conclude that the required journey is possible.It must be remembered that if the sum is one less than the number written above,then the journey must begin from one of the areas marked with an asterisk,and it must begin from an unmarked one if the sum is equal.Thus in the K¨o nigsberg problem,I set out the working as follows:
Number of bridges7,which gives8Bridges
Bridges
A,53
B,32
C,33
D,32
Since this gives more than8,such a journey can never be made.
15Suppose that there are two islands A and B surrounded by water which leads to four rivers as shown in Fig.[1.4].
[Figure1.4]
Fifteen bridges(a,b,c,d,etc.)cross the rivers and the water surrounding the islands,and it is required to determine whether one can arrange a journey which crosses each bridge exactly once.First,therefore,I name all the areas
8
separated by water as A,B,c:D,E,F,so that there are six of them.Next,I
increase the number of bridges(15)by one,and write the result(16)above the
working which follows.
16
A*,84
B*,42
C*,42
D,32
E,53
F*,63
16
Thirdly,I write the letters A,B,C,etc.in a column,and write next to each
one the number of bridges which lead to the corresponding area,so that eight
bridges lead to A,four to B,and so on.Fourthly,I indicate with an asterisk
those letters which have an even number next to them.Fifthly,I write in the
third column half the even numbers in the second column,and then I add one
to the odd numbers and write down half the result in each case.Sixthly,I add
up all the numbers in the third column in turn,and I get the sum16;since this
is equal to the number(16)written above,it follows that the required journey
can be made if it starts from area D or E,since these are not marked with an
asterisk.The journey can be done as follows:
EaFbBcFdAeFfCgAhCiDkAmEnApBoElD,
where I have written the bridges which are crossed between the correspond-
ing capital letters.
?Question E.Apply Euler’s procedure to determine whether the graph representing the‘bridge-crossing’question in Question A above contains an Euler path.If so,?nd one.
In paragraphs16and17,Euler makes some observations intended to simplify the proce-dure for determining whether a given bridge-crossing problem has a solution.As you read these paragraphs,consider how to reformulate these observations in terms of‘degree’.
16In this way it will be easy,even in the most complicated cases,to determine whether or not a journey can be made crossing each bridge once and once only.
9
I shall,however,describe a much simpler method for determining this which is
not di?cult to derive from the present method,after I have?rst made a few
preliminary observations.First,I observe that the numbers of bridges written
next to the letters A,B,C,etc.together add up to twice the total number
of bridges.The reason for this is that,in the calculation where every bridge
leading to a given area is counted,each bridge is counted twice,once for each
of the two areas which it joins.
17It follows that the total of the numbers of bridges leading to each area must be an even number,since half of it is equal to the number of bridges.This is
impossible if only one of these numbers is odd,or if three are odd,or?ve,and
so on.Hence if some of the numbers of bridges attached to the letters A,B,
C,etc.are odd,then there must be an even number of these.Thus,in the
K¨o nigsberg problem,there were odd numbers attached to the letters A,B,C
and D,as can be seen from Paragraph14,and in the last example(in Paragraph
15),only two numbers were odd,namely those attached to D and E.
?Question F.The result described in Paragraph16is sometimes referred to as‘The Handshake Theorem’,based on the equivalent problem of counting the number of hand-shakes that occur during a social gathering at which every person present shakes hands with every other person present exactly once.A modern statement of the Handshake Theorem would be:“The sum of the degree of all vertices in a?nite graph equals twice the number of edges in the graph.”Locate this theorem in a modern textbook,and comment on how the proof given there compares to Euler’s discussion in paragraph16.
?Question G.The result described in Paragraph17can be re-stated as follows:“Every ?nite graph contains an even number of vertices with odd degree.”Locate this theorem in a modern textbook,and comment on how the proof given there compares to Euler’s discussion in paragraph17.
Euler now uses the above observations to develop simpli?ed rules for determining whether a given bridge-crossing problem has a solution.Again,consider how you might reformulate this argument in modern graph theoretic terms;we will consider a modern proof of the main results below.
18Since the total of the numbers attached to the letters A,B,C,etc.is equal to twice the number of bridges,it is clear that if this sum is increased by2
and then divided by2,then it will give the number which is written above the
working.If,therefore,all of the numbers attached to the letters A,B,C,D,
etc.are even,and half of each of them is taken to obtain the numbers in the
third column,then the sum of these numbers will be one less than the number
written above.Whatever area marks the beginning of the journey,it will have
10
an even number of bridges leading to it,as required.This will happen in the
K¨o nigsberg problem if the traveller crosses each bridge twice,since each bridge
can be treated as if it were split in two,and the number of bridges leading into
each area will therefore be even.
19Furthermore,if only two of the numbers attached to the letters A,B,C,etc.
are odd,and the rest are even,then the journey speci?ed will always be possible
if the journey starts from an area with an odd number of bridges leading to it.
For,if the even numbers are halved,and the odd ones are increased by one,as
required,the sum of their halves will be one greater than the number of bridges,
and hence equal to the number written above.It can further be seen from this
that if four,or six,or eight...odd numbers appear in the second column,
then the sum of the numbers in the third column will be greater by one,two,
three...than the number written above,and the journey will be impossible.
20So whatever arrangement may be proposed,one can easily determine whether or not a journey can be made,crossing each bridge once,by the following rules:
If there are more than two areas to which an odd number of bridges lead,then such a journey is impossible.
If,however,the number of bridges is odd for exactly two areas,then the journey is possible if it starts in either of these areas.
If,?nally,there are no areas to which an odd number of bridges leads, then the required journey can be accomplished starting from any area.
With these rules,the given problem can always be solved.
21When it has been determined that such a journey can be made,one still has to ?nd how it should be arranged.For this I use the following rule:let those pairs
of bridges which lead from one area to another be mentally removed,thereby
considerably reducing the number of bridges;it is then an easy task to construct
the required route across the remaining bridges,and the bridges which have been
removed will not signi?cantly alter the route found,as will become clear after a
little thought.I do not therefore think it worthwhile to give any further details
concerning the?nding of the routes.
A complete modern statement of Euler’s main result requires one?nal de?nition:a graph is said to be‘connected’if for every pair of vertices u,v in the graph,there is a walk from u to v.Notice that a graph which is not connected will consist of several components,or subgraphs,each of which is connected.With this de?nition in hand,the main results of Euler’s paper can be stated as follow:
Theorem:A?nite graph G contains an Euler circuit if and only if G is connected
and contains no vertices of odd degree.
Corollary:A?nite graph G contains an Euler path if and only if G is connected
and contains at most two vertices of odd degree.
11
?Question H.Illustrate why the modern statement speci?es that G is connected by giving an example of a disconnected graph which has vertices of even degree only and contains no Euler circuit.Explain how you know that your example contains no Euler circuit.
?Question https://www.wendangku.net/doc/6516931325.html,ment on Euler’s proof of this theorem and corollary as they appear in paragraphs16—19.How convincing do you?nd his proof?Where and how does he make use of the assumption that the graph is connected in his proof??Question J.Below is the sketch of the proof of the‘if’direction of the main Theorem. Complete this proof sketch by?lling in the missing details.(Speci?c questions that you will need to address in your completed proof are indicated in italics.)
NOTE:You may make use of the lemmas that are provided(with proofs)in the Appendix of this project to do so.
CLAIM:
If G is connected and has no vertices of odd degree,then G contains an Euler circuit. PROOF:
Suppose G is connected and has no vertices of odd degree.
We show that G contains an Euler circuit as follows:
CASE I Consider the case where every edge in G is a loop
–Since every edge in G is a loop,G must contain only one vertex.
How do we know a connected graph in which every edge in G is a loop contains only one vertex?
–Since every edge in G is a loop on the single vertex V,G must contain an Euler circuit.
What will an Euler circuit in a connected graph on the single vertex v look like as
a sequence of alternating vertices and edges?
CASE II Consider the case where at least one edge in G is not a loop
–Choose any vertex v in G that is incident on at least one edge that is not a loop.
–Let u and w be any vertices adjacent to v.
How do we know two such vertices exist?
–Let W be a simple path from v to w that does not use the edge{vw}.
How do we know there is a walk from v to w that does not use this edge?
(You may wish to consider what happens in the case where every walk from v to w uses the edge{vw};what happens to the graph when the edge{vw}is removed?) Why can we assume that this walk is,in fact,a simple path?
12
–Use W to obtain a circuit C starting and ending at v.
How is this done?
–Consider the two cases:
?C uses every edge of G.
Why are we now done?
?C does not use every edge in G.
·Consider the graph G obtained by removing the edges of C from the
graph G along with any vertices that are isolated by doing so.Note that
G is connected and has only vertices of even degree.
How do we that G is connected and has only vertices of even degree?
·Select a vertex v in G which appears in C.
How do we know that such a vertex exists?
·Repeat the process outlined above to obtain a circuit C in G ,and com-
bine C with C to obtain a new circuit C1.
How do we combine the circuits C and C from our construction into
a single circuit?How do we know that the combined walk C1is a cir-
cuit?How do we know that the combined circuit C1does not contain any
repeated edges?
·Repeat this process as required until a circuit is obtained that includes
every edge of G.
How do we know this process will eventually terminate?
?Question K.Now write a careful(modern)proof of the‘only if’direction.Begin by assuming that G is a connected graph which contains an Euler circuit.Then prove that G has no vertices of odd degree.
?Question L.Finally,give a careful(modern)proof of the corollary. References
[1]Norman L.Biggs,E.Keith Lloyd&Robin J.Wilson,Graph Theory:1736-1936,Oxford:
Clarendon Press,1976.
[2]Ioan James,Remarkable Mathematicians:From Euler to von Neumann,Cambridge:
Cambridge University Press for The Mathematical Association of America,2002.
[3]Victor Katz,A History of Mathematics:An Introduction,New York:Harper Collins,
1993.
13
APPENDIX:Lemmas Used in Proving Euler’s Theorem
LEMMA I
For every graph G,if W is a walk in G that has repeated edges,then W has repeated vertices. PROOF
Let G be a graph and W a walk in G that has a repeated edge e.Let v and w be the endpoint vertices of e.
If e is a loop,note that v=w,and v is a repeated vertex of W since the sequence‘vev’must appear somewhere in W.
Thus,we need only consider the case where e is not a loop and v=w.In this case,one of following must occur:
1.The edge e is immediately repeated in the walk W
That is,W includes a segment of the form‘vewev’a segment of the form‘wevew’.
2.The edge e is not immediately repeated,but occurs later in the walk W and in the
same order
That is,either W includes a segment of the form‘vew...vew’or W includes a segment of the form‘wev...wev’.
3.The edge e is not immediately repeated,but occurs later in the walk W in the reverse
order
That is,either W includes a segment of the form‘vew...wev’or W includes a segment of the form‘wev...vew’.
Since one of the vertices v or w is repeated in the?rst case,while both the vertices v and w are repeated in the latter two cases,this completes the proof.
COROLLARY
For every graph G,if W is a walk in G that has no repeated vertices,then W has no repeated edges.
PROOF
This is the contrapositive of Lemma I.
14
LEMMA II
If G is a connected graph,then every pair of vertices of G is connected by a simple path.
PROOF
Let G be a connected graph.Let u and w be any arbitrary vertices in G.Since G is connected,we know G contains a walk W from u to w.Denote this walk by the sequence ‘v0e0v1e1...v n e n v n+1’,where e0,e1,...e n denote edges,v0,...,v n+1denote vertices with v0= u the starting vertex and v n+1=w the ending vertex.
Note that W may include repeated vertices.If so,construct a new walk W from u to w as follows:
?Let v be the?rst repeated vertex in the walk W.Then v=v i and v=v j for some i That is,replace v0 u e1v1e2...v i?1e i?1 v v i e i v i+1e i+1...e j?1v j?1e j v v j delete e j+1v j+1...v n?1e n?1v n e n v n+1 w by ue1v1e2...v i?1e i?1 v v i e j+1v j+1...v n?1e n?1v n e n w Since‘ve j+1’appeared in the original walk W,we know the edge e j+1is incident on the vertex v=v i.Thus,the new sequence of alternating edges and vertices is also a walk from u=v0to w=v n+1. (Also note that if j=n+1,then the repeated vertex was w=v n+1and the walk now ends at v i,where we know that v i=v j=v n+1=w;thus,the new walk also ends at w.) ?If the new walk W contains a repeated vertex,we repeat the above process.Since the sequence is?nite,we know that we will obtain a walk with no repeated vertices after a?nite number of deletions. In this way,we obtain a new walk S from u to w that contains no repeated vertices.By the corollary to Lemma I,it follows that S contains no repeated edges.Thus,by de?nition of simple path,S is a simple path from u to w.Since u and w were arbitrary,this completes the proof. 15 哥尼斯堡七桥问题体现的拓扑思想 摘要：七桥问题是1736年29岁的欧拉向圣彼得堡科学院递交《哥尼斯堡的七 座桥》论文时提出的，在解答问题的同时，开创了数学的一个新的分支——图论与几何拓扑，也由此展开了数学史上的新进程。由哥尼斯堡七桥问题出发，分析其蕴含的思想、方法，并引出其中的拓扑思想。 关键词：七桥问题；拓扑；思想； 拓扑学（英语：topology），几何拓扑学是十九世纪形成的一门数学分支，它属于几何学的范畴.拓扑学起源于哥尼斯堡七桥问题，以及与此相关的一笔画问题。它所研究的是几何形体在连续形变，精确地说，双方一一而且双方连续的变换（称为同胚）之下保持不变的性质。理解得广泛些，拓扑学是研究数学中连续性现象的学科。有关拓扑学的一些内容早在十八世纪就出现了，那时候发现一些孤立的问题，后来在拓扑学的形成中占着重要的地位。 一、哥尼斯堡七桥问题简介 哥尼斯堡七桥问题是欧拉用抽象的方法探究并解决实际问题的一个典型实例，对开创图论与拓扑学的研究具有重大意义. 18世纪的哥尼斯堡是德国的一个美丽的城市，布勒尔河穿城而过，它有两个支流，在哥尼斯堡城中心汇成大河，河中心有一个小岛，河上有七座桥，如图(1)岛上有一座古老的大学，还有哲学家康德的墓地及塑像.当地的居民，特别是大学生们常常到七桥附近散步，渐渐地大家热衷于一个问题:一个人是否能不重复地一次走遍这七座桥而返回出发点？很多人做过尝试，但都未能实现，这便产生了数学史上著名的“七桥问题”，1735年，一群大学生写信将这个难题交给了著名的数学家欧拉 二、问题的解决 欧拉解决这个问题的第一步是把它尽量简化。他发现，对于这个问题，岛的大小、陆地的面积、桥的长短与宽窄等都不影响答案。因此，他用点表示岛与陆地，用线表示桥。把“七桥图”简化为一个几何图形如图（2）。这样，原题就转化为一个几何问题：能否从图（2），A、B、C、D四点中的某一点出发，只通过每条路线一次，而把所有的7条路都走完？或者说，能否从图（2），A、B、C、D四点中的某一点开始，不重复地一笔画出这个图？弧连接的顶点叫奇顶点。如果一个网络图只有偶顶点，那么它一定可以一笔画，并回到起点；如果一个网络图只有两个奇顶点，那么它可以从一个奇顶点出发，到另一个奇顶点结束，一笔画完；如果一个网络图只有一个奇顶点或者多于2个奇顶点，那么它一定不能一笔画。 最后，欧拉把上述结论用于图2，由于它的顶点都是奇顶点，所欲它一定不能一笔画。也就是说，“七桥问题”的答案是否定的。 欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称之为“欧拉定理”。对于一个连通图，通常把从某结点出发一笔画成所经过的路线叫做欧拉路。人们又通常把一笔画成回到出发点的欧拉路叫做欧拉回路。具有欧拉回路的图叫做欧拉图。 一笔画的特征： ⒈凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。 ⒉凡是只有两个奇点的连通图(其余都为偶点)，一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。 ⒊其他情况的图都不能一笔画出。(奇点数除以二便可算出此图需几笔画成。) “七桥问题”的解决方案均是采用某种捆扎的概念（开集）使点集中的点与点之间发生关系。 “七桥问题”的解决归结为在七桥问题的图模型中寻找遍历每一条边恰好一次而回到原地的途径。欧拉解决这个问题开创了图论典型的思维方式和论证方式，反思欧拉解决“七桥问题”的思路有助于把握图论的本原思想，接受图论的思维方式和解题技巧。 三、体现的拓扑思想 欧拉为什么能抽象出图模型并据此解决七桥问题呢？是他利用特征抽象分析法与拓扑思考方式来考虑问题的结果。所谓特征抽象分析法就是把研究对象的本质特征抽取出来舍弃非本质特征的分析法。为了解决七桥问题，首先要给出问题的正确表征，尽量把问题简化，使得容易抓住问题的要点，对于七桥问题，陆地和岛的大小，桥的曲直长短是无关紧要的，只要关心点与点之间是否有线相连，故可用图来表征七桥问题的情景和结构。所谓拓扑思考方式就是只考虑图形中顶点和边线的个数而不考虑其大小和形状的思考方式。为了解决七桥问题，将图中顶点和边线的关联情况（顶点的度数）作为切入点，寻找有解的必要条件。在寻 世界数学难题——哥尼斯堡七桥问题 18世纪时，欧洲有一个风景秀丽的小城哥尼斯堡(今俄罗斯加里宁格勒)，那里的普莱格尔河上有七座桥。将河中的两个岛和河岸连结，城中的居民经常沿河过桥散步，于是提出了一个问题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？大家都试图找出问题的答案，但是谁也解决不了这个问题。这就是哥尼斯堡七桥问题，一个著名的图论问题。 1727年在欧拉20岁的时候，被俄国请去在圣彼得堡（原列宁格勒）的科学院做研究。他的德国朋友告诉了他这个曾经令许多人困惑的问题。 欧拉并没有跑到哥尼斯堡去走走。他把这个难题化成了这样的问题来看：把二岸和小岛缩成一点，桥化为边，于是“七桥问题”就等价于下图中所画图形的一笔画问题了，这个图如果能够一笔画成的话，对应的“七桥问题”也就解决了。 经过研究，欧拉发现了一笔画的规律。他认为，能一笔画的图形必须是连 通图。连通图就是指一个图形各部分总是有边相连的，这道题中的图就是连通图。 但是，不是所有的连通图都可以一笔画的。能否一笔画是由图的奇、偶点的数目来决定的。那么什么叫奇、偶点呢？与奇数（单数）条边相连的点叫做奇点；与偶数（双数）条边相连的点叫做偶点。如下图中的①、④为奇点，②、③为偶点。 1．凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。例如下图都是偶点，画的线路可以是：①→③→⑤→⑦→②→④→⑥→⑦→① 2．凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。例如下图的线路是：①→②→③→①→④ Early Writings on Graph Theory: Euler Circuits and The K¨o nigsberg Bridge Problem An Historical Project Janet Heine Barnett Colorado State University-Pueblo Pueblo,CO81001-4901 janet.barnett@https://www.wendangku.net/doc/6516931325.html, 8December2005 In a1670letter to Christian Huygens(1629-1695),the celebrated philosopher and mathematician Gottfried W.Leibniz(1646-1716)wrote as follows: I am not content with algebra,in that it yields neither the shortest proofs nor the most beautiful constructions of geometry.Consequently,in view of this,I consider that we need yet another kind of analysis,geometric or linear,which deals directly with position,as algebra deals with magnitude.[1,p.30] Known today as the?eld of‘topology’,Leibniz’s study of position was slow to develop as a mathematical?eld.As C.F.Gauss noted in1833, Of the geometry of position,which Leibniz initiated and to which only two geome- ters,Euler and Vandermonde,have given a feeble glance,we know and possess, after a century and a half,very little more than nothing.[1,p.30] The‘feeble glance’which Leonhard Euler(1707-1783)directed towards the geometry of position consists of a single paper now considered to be the starting point of modern graph theory in the West.Within the history of mathematics,the eighteenth century itself is 1 第二节哥尼斯堡七桥问题 教学目标 1.了解哥尼斯堡七桥问题的由来 2.理解欧拉解决哥尼斯堡七桥问题的方法 3.掌握一笔画问题的步骤 教学重点 掌握一笔画问题的技巧 教学过程 一、导入 哥尼斯堡七桥问题的由来 哥尼斯堡曾是东普鲁士的首府，现称加里宁格勒，在俄罗斯境内。在第二次是世界大战时，的军警哲理入侵波兰。后来，苏军也是从此地打进德国的。所以哥尼斯堡是一座历史名城。同时，在这里诞生和培养过许多伟大人物。如著名唯心主义哲学家康德，终生没有离开此城。在哥尼斯堡城中有一条布勒格尔河，横贯城中。河有两条支流，一条称新河，一条叫旧河，在城中心汇合成一条主流，在合流的地方中间有一座河心岛，这是城中繁华的商业中心。由于布勒格尔河的流过，使全城分成为四个地区： 岛区、北区、东区和南区。在布勒格尔河上，架了七座桥，其中五座将河 岛与河岸连接起来，另有两座架在二支流上。这一别致的桥群，吸引了众 多的哥尼斯堡居民和游人来此河边散步或去岛上买东西。 早在18世纪，就有人提出这样的问题：“能否在一次散步中每座桥都走一次， 而且只能走一次，最后又回到原来的出发点？”这个问题吸引了不少人去思考 实验。事实上，要走遍这七座桥的所有走法共有7！=5040种，要想一一验过，谈 何容易。是否在这5040中走法中存在着一条走遍七座桥而又不重复的路线呢？谁 也回答不了。因而形成了著名的“哥尼斯堡七桥问题”。 二、新授 哥尼斯堡七桥问题的解决 1735年，有几名大学生写信给当时正在俄国彼得堡科学院任职的天才数学家欧拉，请他帮忙解决。欧拉并未轻视生活小题，他似乎看到其中隐藏着某种新的数学方法。 经过一年的研究，29岁的欧拉于1736年向彼得堡科学院递交了一份题为《哥尼斯堡 的七座桥》的论文，圆满地解决了这一问题，同时开创了数学的一个新分支——图论。 问题的抽象——数学化 欧拉是如何将这生活的趣味问题转化为数学问题的呢？又是如何证明要想一次走 过这七座桥是不可能的呢？欧拉的方法十分巧妙：他用点A、B、C、D表示哥尼斯堡 城的四个地区B（岛区）、C（北区）、A（东区）、D（南区）；七座桥看成这四个点的连线，用f，d，a，c，b，e，g七个数字表示,如图3-1。 这样“七桥问题”就转化为是否能用一笔不重复地画出过此七点的图形。假设可以画出来，则图形中必有一个起点和一个终点，如果这两个点不重合，则与起点或终点 相交的线都必是奇数条（称奇点），如果起点与终点重合，则与之相交的线必是偶数 “哥尼斯堡七桥问题”教学实录 一、 创设情境，激趣引思 1. 故事引入 师：这节课，我们先来听一个数学小故事吧。（课件播放，如图1，教师相机板书课题） 师：这个问题困扰了当地居民很长时[司，大家纷纷来到小岛上试图找到答案，但都无功而返。因为根据计算，每次都走完七座桥的所有走法共有5040种，这么多怎么走得完呢?后来有人写信向当时公认的“天才数学家”欧拉请教。欧拉亲自来到小岛上实地考察，也未找到答案。但他是一个不向困难低头的人，经过—年的研究，终于解决了这个问题。原来他将七桥问题题转化为一笔画问题，才顺利找到答案的。 (教师板书：一笔画) 2．释疑。 师：谁能根据你的理解，来说一说什么是一笔画？ (教师请一个学生上台画图说明) 师：（利用课件动态演示）像长方形、正方形、三角形等都能够一笔画出。（并结合长方形介绍：两条线相交的点，叫做交点。如图2） 师：哥尼斯堡七桥问题，大家可能觉得有点复杂。我 们先从简单的图形人手，来探究一笔画中的学问。 二、自主探究，合作交流 (—)探究活动一。1．探究。 师：下面请二人小组合作，共同完成探究记录单，首先请看活动要求。(课件出示记录单和活动要求) 图2 交点交点 活动要求： （1）)试一试，在空白处画一画，判断图形能否一笔画出，并在相应的口里打“√”。 （2）对于能够一笔画出的图形，请沿不同交点出发，探索它有几种不同的画法。 (学生探究，教师巡视指导) 2．交流。 师：很多小组都已经有答案了，谁来汇报一下你们探究的结果？ 生1：1号图是不能一笔画出的，因为它们是分开的。 师：谁听懂了他的意思？ 生2：他是说1号图中的三个“口”没有连通起来。 师：是啊，像1号图这样，各个部分没有连通起来，就不可能一笔画出。这说明要能够一笔画出，它各个部分之间必须是连通的。 画出。 (板书：必须是连通图)接下来，谁继续汇报? 生3：2号图是可以一笔画出的。 师：是吗？你能到黑板上画一下吗?(学生上台画图， 教师提示他在起点处标上字母“A ”，如图3) 图3 师：很好！他刚才是从A 点出发，一笔画出了这个平行四边形。那么，只能从A 点出发吗？ 生4：从其他交点出发也可以。 (大家纷纷赞同) 师：你们都实验过吗？的确，这个平行四边形无论从哪个交点出发，都可以一笔画出来。那么3号图可以一笔画出来吗? 生5：可以的。 (教师请生5上台画图，教师给生5画的图各交点标上字母，如图4) 师：真厉害，他的确是一笔画出的。我发现他是从E 点出发画的。 那么这幅图还能从其他交点出发画出来吗？ 生6：我还可以从F 点出发，也可以一笔画出。 师：还有其他画法吗? 生7：我还可以从A 点出发。 (教师请生7上台画，生7尝试了多种路径，均未成功) 师：(摸着生7的头)我很佩服他，虽然他最后没有成功，但是他这种执着探索的勇气还是可嘉的。从A 点出发不可以，还有哪些点也会出现这样的状况呢? 生8：我认为，从B 、C 、D 点出发也是不能一笔画成的，因为它们和A 点所处的位置是相似的。 师：很好，你真是善于观察！那你们有没有想过，虽然2号图和3号图都能一笔画成，但是2号图可以从任意一点出发，而3号图只能从E 点和F 点出发B F 七桥问题 目录 七桥问题 故事背景 推断方法 最终成果 展开 编辑本段七桥问题 1736年29岁的欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的论文，在解答问题的同时，开创了数学的一个新的分支-----图论与几何拓扑。也由此展开了数学史上的新进程。问题提出后，很多人对此很感兴趣，纷纷进行试验，但在相当长的时间里，始终未能解决。七桥问题和欧拉定理。欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称之为“欧拉定理”。 编辑本段故事背景 七桥问题七桥问题Seven Bridges Problem 18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点?欧拉于1736年研究并解决了此问题，他把问题归结为如下右图的“一笔画”问题，证明上述走法是不可能的。 有关图论研究的热点问题。18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来(如左图上)。有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点后来大数学家欧拉把它转化成一个几何问题(如左图下)——一笔画问题。他不仅解决了此问题，且给出了连通图可以一笔画的重要条件是它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为0或2. 编辑本段推断方法 当Euler在1736年访问Konigsberg, Prussia(now Kaliningrad Russia)时，他发现当地的市民正从事一项非常有趣的消遣活动。Konigsberg城中有一条名叫Pregel的河流横经其中，这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。 Euler把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。 后来推论出此种走法是不可能的。他的论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地(或点)时，他(或她)同时也由另一座桥离开此 一、哥尼斯堡七桥问题 18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如图1所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。 图1 这个问题看起来似乎不难，但人们始终没有能找到答案，最后问题提到了大数学家欧拉那里。欧拉以深邃的洞察力很快证明了这样的走法不存在。欧拉是这样解决问题的：既然陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成A、B、C、D4个点，7座桥表示成7条连接这4个点的线，如图2所示。 图2 图3 于是“七桥问题”就等价于图3中所画图形的一笔画问题了。欧拉注意到，每个点如果有进去的边就必须有出来的边，从而每个点连接的边数必须有偶数个才能完成一笔画。图3的每个点都连接着奇数条边，因此不可能一笔画出，这就说明不存在一次走遍7座桥，而每座桥只许通过一次的走法。欧拉对“七桥问题”的研究是图论研究的开始，同时也为拓扑学的研究提供了一个初等的例子. 二、四色猜想 近代三大数学难题之一。四色猜想的提出来自英国。1852年，毕业于伦敦大学的弗南西斯.格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色。”这个结论能不能从数学上加以严格证明呢？他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠，可是研究工作没有进展。1852年10月23日，他的弟弟就这个问题的证明请教他的老师、著名数学家德.摩尔根，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家哈密尔顿爵士请教。哈密尔顿接到摩尔根的信后，对四色问题进行论证。但直到1865年哈密尔顿逝世为止，问题也没有能够解决。1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878～1880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。11年后，即1890年，数学家赫伍德 哥尼斯堡七桥问题与图论 大家公认，图论诞生于七桥问题．出生于瑞士的伟大数学家欧拉（Leonhard Euler，1707—1783）于1736年发表了论文《与位置几何有关的一个问题的解》，文中提出并解决了七桥问题，为图论的形成奠定了基础．今天，图论已广泛应用在计算机学科、运筹学、控制论、信息论等学科中，成为对现实世界进行抽象的一个强有力的数学工具． 七桥问题是这样描述的：17世纪的东普鲁士有一座哥尼斯堡城（现在叫加里宁格勒，在波罗的海南岸），城中有一座岛，普雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区4个区域，全城共有七座桥将4个城区连接起来，图1是这条河以及河上的两个岛和七座桥的草图．于是，产生了一个有趣的数学难题：一个人是否能在一次步行中穿越全部的七座桥后回到起点，且每座桥只经过一次， 为了解决哥尼斯堡七桥问题，欧拉用A、B、C、D表示4个城区，用7条线表示7座桥，将哥尼斯堡七桥问题抽象为一个图模型，如图2所示，从而将哥尼斯堡七桥问题抽象为一个数学问题：求经过图中每条边一次且仅一次的回路，后来人们称之为欧拉回路．欧拉论证了这样的回路是不存在的，并且将问题进行了一般化处理，即对于任意多的城区和任意多的桥，给出了是否存在欧拉回路的判定规则： （1）如果通奇数桥的地方多于两个，则不存在欧拉回路； （2）如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路； （3）如果没有一个地方通奇数桥，则无论从哪里出发，都能找到欧拉回路．在欧拉发现七桥问题之后的一个世纪，著名的爱尔兰数学家哈密顿（William Hamilton，1805—1865）提出了另一个著名的问题——哈密顿回路问题，他用正十二面体的20个顶点代表20个城市，要求从一个城市出发，经过每个城市恰好一次，然后回到出发城市．图3所示是一个正十二面体的展开图，按照图中的顶点编号所构成的回路，就是哈密顿回路的一个解． 哈密顿回路与欧拉回路看上去十分相似，但他们是两个不同的问题．哈密顿回路是访问每个顶点一次且仅一次，而欧拉回路是访问每条边一次且仅一次．对一个图是否存在欧拉回路已经给出充分必要条件，而对一个图是否存在哈密顿回路至今未找到充分必要条件． 哥尼斯堡七桥问题探究 欧拉对于《哥尼斯堡桥》一文进行了深入分析与研究，解开了“哥尼斯堡七桥问题”所蕴含的丰富数学思想。通过对七桥问题进行研究与分析，能够让我们对于数学领域中的相关知识予以深入掌握，带给我们更为丰富的数学视角与视野。 标签：哥尼斯堡桥七桥问题欧拉数学思想 一、哥尼斯堡七桥问题简述 “七桥问题”出现于18世纪哥尼斯堡城。在这个城市中有七座桥，当时居民十分热衷：一个散步者怎样将这七座桥走遍，并且每座桥都不重复。要想符合所提出的要求，应当与以下两个条件相适应： 第一，所谓的“不重复”指的是，每座桥只能走一次； 第二，所谓的“走遍”指的是，每座桥都应当走到不应当被落下。 这些问题的解决是欧拉所完成的，在很多的文献资料中，都提到了欧拉对七桥问题解决的方法，实际上，在欧拉的论文《问题解决与几何位置》中，只包括以下的三幅图与两个表格。 该问题主要包括两个特征： 第一，该问题全部来源于现实； 第二，该问题属于新数学领域范畴，欧拉的解答所具备的创新性非常突出，对数学教育工作的开展具有至关重要的启发作用。 二、欧拉对七桥问题的解答 第一步就是，对描述路线的简洁方法进行寻找。将河流分割的陆地区域分别用A、B、C 、D表示，地点A到达地点B需要对桥a或b进行跨越，记作AB，倘若再从地点B跨越桥f到达地点D，记作ABD，字母B不仅代表首次跨越的终点，也代表第二次跨越的起点，其余地点也根据这种方法进行类推。其发现： 第一，该表示方法与跨越的桥不存在任何关联； 第二，跨越n座桥的路线正好可以用n+1个字母来代表。 该问题就转变成符合条件的八个字母排列问题。在部分区中，所连接的桥不止一座，部分字母会多次出现，所以，应当对每个字母所出现的次数进行确定。 阅读材料]世界名题与小升初之： 哥尼斯堡七桥问题 --马到成功老师 在各类竞赛中，各类小升初考试中相关的世界名题出现的概率极高，这是由小升初与数学竞赛的特点决定，这特点便是：知识性，趣味性，思想性相结合。 历史上有名的七桥问题，是脍炙人口的应用数学去解 决实际问题的典范，在欧洲的普鲁士哥尼斯堡镇上有一个 小岛，普里格尔河蜿蜒其间，河岸与岛屿间有七座桥相连， 在18世纪，有人提出：能否不重复地一次接连通过每座桥？ 这个生活中的问题，引起人们浓厚的兴趣，市民、学生， 观光者，竞相“过桥”有人还画出地图，在图上游来走去， 还出现了梦游七桥的故事，但问题一直未获解决，被世人 谓之哥尼斯堡七桥问题，如图。 后来，问题传到了欧拉手中，欧拉当时才28岁，但已是远近闻名的瑞士数学家，他只用了几天思考，就找到了解答，办不到！ 欧拉解决问题采用了“数学模型”法，欧拉认为，既然岛与陆地时靠桥来接连的，那么不妨把4片陆地缩小（抽象）成4个点，并把七座桥表示 （抽象）成7条边，从而得到了七桥问题的模拟图，这样当然未改变问 题的实质，于是人们试图一次无重复地走过7座桥的问题就等价于一笔 画出模拟图型的问题，如图。 欧拉指出：这是办不到的，因为接连每点的线都是奇数条（这样 的点，称为奇顶点）而每通过顶点一次，一入一出要用去2条线（因不 许重复），只有在起点，有一次只出不入，或在终点，有一次只入不出， 因此，要想一笔画出一个图，这个图的奇顶点就不能多于2个（没有或 恰有2个奇顶点）而模拟图奇顶点个数为4，故不能一笔画，欧拉还给 出了一般结论： ①接连奇数座桥的陆地仅有一个或超过两个以上，不能实现一笔画。 ②接连奇数座桥的陆地仅有两个小时，则从两者任一陆地出发，可以实现一笔画而停在另一陆地。 ③每个陆地都接连有偶数座桥时，可以从任一陆地出发都能实现一笔画，而回到出发地。 1736年，欧拉的《哥尼斯堡七桥问题》论文问世，开创了“图论”和“拓扑学”的先河。欧拉解决七桥问题，对我们有什么启示呢？首先，欧拉对问题作了抽象，它用一张点线图代替了七桥图，用“一笔画”代替了过桥问题，当欧拉对点线图进行分析时，发现了“过桥”同“一笔画”的等价性，而且发现了“一笔画”同图中顶点的奇偶性之间的关系，他同时证明了有关定理。在欧拉的抽象过程中，他舍弃了河岸，岛屿的形状、高低、大小等外部特征，而把它们抽象成一个个表示位置的点，舍弃了一座座造型各异，结构不同，长短不等的桥的外部特征，而把它们抽象成连结相应点的弧线，进而他又舍弃了河流、桥、河岸于岛屿的实际位置，而只保留它们原来过桥问题的要求抽象成了“一笔画”的条件，即每条弧线恰好画一次，而一笔连续画出。 【小学数学】课堂实录《哥尼斯堡七桥问题》“哥尼斯堡七桥问题”教学实录 一、创设情境，激趣引思 1. 故事引入 师:这节课，我们先来听一个数学小故事吧。(课件播放，如图1，教师相机板书课题) 师:这个问题困扰了当地居民很长时[司，大家纷纷来到小岛上试图找到答案，但都无功而返。因为根据计算，每次都走完七座桥的所有走法共有5040种，这么多怎么走得完呢?后来有人写信向当时公认的“天才数学家”欧拉请教。欧拉亲自来到小岛上实地考察，也未找到答案。但他是一个不向困难低头的人，经过—年的研究，终于解决了这个问题。原来他将七桥问题题转化为一笔画问题，才顺利找到答案的。 (教师板书:一笔画) 2(释疑。 师:谁能根据你的理解，来说一说什么是一笔画, (教师请一个学生上台画图说明) 师:(利用课件动态演示)像长方形、正方形、三角形等都能够一笔画出。(并结合长方形介绍:两条线相交的点，叫做交点。如图2) 交点交点 师:哥尼斯堡七桥问题，大家可能觉得有点复杂。我 们先从简单的图形人手，来探究一笔画中的学问。 二、自主探究，合作交流交点交点 (—)探究活动一。1(探究。图2 师:下面请二人小组合作，共同完成探究记录单，首先请看活动要求。(课件出示记录单和活动要求) 1 活动要求: (1))试一试，在空白处画一画，判断图形能否一笔画出，并在相应的口里打“?”。 (2)对于能够一笔画出的图形，请沿不同交点出发，探索它有几种不同的画法。 (学生探究，教师巡视指导) 2(交流。 师:很多小组都已经有答案了，谁来汇报一下你们探究的结果, 生1:1号图是不能一笔画出的，因为它们是分开的。 师:谁听懂了他的意思,哥尼斯堡七桥问题体现的拓扑思想
世界数学难题—哥尼斯堡七桥问题
Euler-哥尼斯堡七桥问题
第二章 第二节 哥尼斯堡七桥问题
哥尼斯堡七桥问题教学实录
七桥问题
哥尼斯堡七桥问题
哥尼斯堡七桥问题与图论
哥尼斯堡七桥问题探究
哥尼斯堡七桥问题
【小学数学】课堂实录《哥尼斯堡七桥问题》