1-图论模型(看一笔画).ppt

第九章 图论模型 在生产生活中，人们常常用图或网络来刻画、解释和处理某些实际问题,常见的如车辆流通图、电路网络图、赛事安排图和工程进度管理图等.这种表示方式不仅使实际问题变得直观、简洁、明了，而且也为实际问题的研究提供了一种有效的方法 .近几十年来，随着运筹学、信息论和计算机科学的发展，人们对图论和网络的研究也越来越广泛和深入，并且迅速地产生了一门新兴的数学分支—图论.在这一章里，我们将简略地介绍一些与此有关的实际问题以及解决这些问题的巧妙方法. 9.1 一笔画问题 9.1.1 七桥问题 18世纪，东普鲁士的哥尼斯堡是一座景致迷人的城市，普勒格尔河横贯其境，并在这儿形成两条支流，把整座城市分割成4个区域 （如图） 河的两岸(C和D），河中的岛(A)和两条支流之间的半岛(B).当时有7座桥横跨普勒格尔河及其支流， 把河岸、半岛和河心岛连接起来.有趣的桥群和哥城4区域的的迷人景色吸引了众多的的游客.有人在游览时提出这样的问题：能否从某个地方出发，穿过所有的桥各一次后再回到出发点？很多人做了尝试，但没有一个人成功.是否存在成功的可能性呢？人们既拿不出成功的方案，又找不到否定的理由.后来这个令人困惑的问题被年轻的瑞士数学家欧拉（Leonhard Eular）知道了，他在1736年向圣彼得堡学院递交的一篇论文中巧妙的解决了这个问题. 他是怎么解决这个问题的呢？ 他首先把哥尼斯堡的4个区域分别用A,B,C,D表示， 7座桥表示成7条连接这4个点的线，于是哥尼斯堡七桥的情形就转化为下图的情形 这个由4个点和7条连线（也叫边）组成.问题相应地变为：在上述模拟图中，从A,B,C,D中任何一点出 发，笔不离纸，但又不能重复任何一条边地画出模拟图，且起点与终点重合，这样的画法存在吗？这就是众所周知的“一笔画”问题. 接下来，欧拉研究了能够“一笔画”的图形所应具有的性质.他注意到，这类图中的点倘若不是“一笔画”的起点和终点，那它作为“一笔画”的“中途点”应该具有这样的特性：笔沿着某条边“进入”点后，必定要沿着另一条边“出去”.于是， “中途点”的边必定成对出现.也就是说，与“中途点”相连的边的条数必是偶数. 我们把与点v相连接的边的条数称为该点的度数， 记作d（v）.d（v）为偶数时，点v称为偶点，否则称为奇点.按欧拉的分析，能“一笔画”的图的“中途点”的度数为偶点，而奇点只能作为“一笔画”的起点或终点.当起点和终点重合时，该图不存在奇点.概括起来，就是这样一个结论：如果一个图形可以“一笔画”，那么其奇点个数必为0（起点和终点重合）或2（起点和终点不重合）. 9.1.2 有关图的基本概念 为了便于说明，我们简要的介绍一下图的基本概念及其性质. 我们经常遇到这样一些问题，他们仅包含两方面的内容：一是一些“对象”（如七桥问题中的岛和河岸），二是这些对象之间的某种关系（如岛与岛、岛和河岸之间是否有桥连接，有几座桥连接）.为表示这些对象和它们之间的关系，可以在纸上画一些点，每一点代表一个对象，称这些点为顶点，如果两个对象之间有所讨论的关系，就在相应的两点之间连一条线，这些线称为边，这样有若干个点和若干条边就构成了一个图. 由若干个不同的顶点与连接其中某些顶点的边所组成的图形称为图.通常用G来表示图.用V表示图中所有顶点的集合，用 E表示所有边的集合，并且记为G=(V,E).图G中顶点的个数|V|称为G的阶. 图的基本性质： 设G是n阶图，则G中n个顶点的度数之和等于边数的两倍. 证明： 所有顶点的度数之和表示以每一顶点为端点的边的总数.由于一条边有两个端点，因此每条边在顶点的度数之和中都被记入两次，所以顶点的度之和应为边数的两倍. 推论： 对于任意的图G，奇点的个数是偶数. 在图G中，有一个不同的边组成的序列： e1, e2, …, em，如果其中边, ei=(vi-1，vi),i=1,2,3…m.则称这个序列是从v0到vm的链. 如果一条链的始点v0和终点vm重合，则称这条链为圈. 如果对于图G中的任意两个顶点u和v，都有一条从u到v的链，则称这样的图G是连通的，否则称G是不连通的. 经过图G的每条边的链，称为G的欧拉链.经过图G的每条边的圈称为G的欧拉圈.一个图若包含欧拉圈，则称这个图为欧拉图. 直观的讲，欧拉图就是从某一顶点出发而每边恰通过一次又能回到出发点的图. 9.1.3 一笔画定理及其证明 在七桥问题的讨论中，我们得到了一个结论:如果一个图形可以“一笔画”，当且