数学欣赏-06数学之妙-c七桥问题与图论

数学欣赏Mathematics

Appreciation数学欣赏F数学之妙TheConsummateskillof

Mathematics名人说……从十分清楚明白、根本无法怀疑的东西、最简单最容易认识的对象开始，一点一点逐步上升到对复杂对象的认识。

——R.DESCARTES名人说……数学是什么？大致说来，数学和其它科学一样，它的发展基于两个原因：（一）奇怪的现象；（二）数学结果的应用。——陈省身数学之妙出神入化数学，虽然极其抽象，但却被广泛而有效的应用于人类社会的各个领域，其根本原因不仅是其对象为万物之本，更在于其思想方法的深刻性与普适性.由于人类生理的原因，人类能够准确认识的对象只能是有限的、静止的、平直的、离散的，但现实中人们又无法避免无限的、运动的、弯曲的、连续的.数学方法为人类认识这些对象提供了有效的可靠手段，奇妙无比，威力无限.InthisChapter数学归纳法原理1抽屉原理与聚会认友

2七桥问题与图论

3数学与密码4SZU第三节七桥问题与图论BDCA背景18世纪，位于现立陶宛内的哥尼斯堡镇，有一条河流叫普雷格尔河。河中有两个相邻的小岛，岛与岛、岛与陆地之间建有七座桥BDCA问题：一个人能否一次无重复地走遍所有的七座桥，最后回到出发点？这就是著名的“七桥问题”。1736年，一位小学教师写信给当时的著名数学家欧拉（Euler），请教对七桥问题的解答。欧拉用数学方法对七桥问题进行了深入的研究。欧拉的解答

——七桥问题的数学模型欧拉研究后发现：(1)这不是一个代数问题（代数问题研究量的大小、关系）;(2)这也不是一个平面几何问题（平面几何问题研究角度的大小、线段的曲直、长短等）。BDCA在这里，陆地、岛屿的大小、形状均是无关紧要的，桥梁的曲直、长短也对问题的解答没有影响；该问题的解仅依赖于陆地、岛屿、桥梁等的具体个数及其相互位置关系。因此，可以将一块陆地或一个岛屿看作一个“点”，将一座桥梁看作一条连接两点的“线”。（如下页图）BDCABACD按照欧拉的思想，七桥问题转化为：一笔画问题在右图中，能否从图上某一点开始，笔不离纸、不重复地画出整个图形？BACD这一重要思想，成为近代数学之一——图论的基础，同时也是近代数学——拓扑学（位置几何学）的奠基。

图的基本概念

与基本结论1.图—

点（称为顶点）和将它们之间的某些点两两连接起来的线（称为边）的集合，叫做图。一个图记为G（Graph）;一条边记为e（edge），边的集合记为E（Edge）；一个顶点记为v（vertex），顶点的集合记为V（Vertex）。DACB顶点边环2重边相邻顶点图的基本概念(1)2.顶点的次数：顶点v处引出的边的条数叫做顶点v的次数，记为

d（v）。结论次数总和等于边数总和的2倍(偶数)。图的基本概念(2)4阶完全图孤立点简单图3次顶点2次顶点3.奇点、偶点——顶点次数为奇（偶）数的顶点叫奇（偶）点。

结论：奇点数必为偶数。

偶点：边线有进有出，进出对应；

奇点：有一条只进不出或只出不进的边线。4.连通图——任意两点之间都有链相连的图叫做连通图。

图的基本概念(3)链，连通图奇点偶点圈一笔画定理

——

七桥问题的解决

1.一笔画定理定理（一笔画）

一个图G可以一笔画的充要条件是：G是连通的，并且奇点的个数为0或2。当奇点数为2时，一个奇点为起点，另一个奇点为终点；当奇点个数为0时，任取一个顶点，它是起点，也是终点。证明思想：(1)必要性若G能一笔画，则G必是连通的，而且只有在起点处的边才可能只出不进（奇点），也只有在终点处的边才有可能只进不出（奇点）。故G是连通的，且没有奇点或只有两个奇点。(2)充分性若G是连通的，并且奇点的个数为0或2。我们通过对顶点的总次数n=2k(偶数)用数学归纳法来证明G可以一笔画。

n=2时，G是一条有两个顶点（端点）的线段，或是一条有一个顶点的圆圈。因此可以一笔画。

假设n=2k时结论成立，考虑n=2(k+1)=2k+2的情况。

如果该图没有奇点，则从中任意去掉一条边.设此边的两端点分别为v0,v1,此时，该图仍然是连通的（因为其任一顶点处至少有两条边通过，去掉一条后，还至少有一条边与其它顶点相连），而且，其顶点的次数总和为2k,其中奇点数最多为2。此时剩余图可以从v0出发到v1结束一笔画，再从v1到v0,即可将原图一笔画。

如果该图有两个奇点v0,v1,

去掉v0出发的一条边。

若d(v0)>1,则剩余图是一个奇点个数为0或2、顶点次数总和为2k的连通图,因而可以一笔画，从而原图也可以一笔画。若d(v0)=1，则剩余图是一个奇点个数为0或2、顶点次数总和为2k的非连通图，除去v0点后，该图是连通图，可以一笔画，因此原图也可以一笔画