资源描述：
《第9章图论(10.5).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、电子科技大学应用数学学院张先迪图论第9章图论简介现实生活中许多问题都可归结为由点和线组成的图形的问题，例如，铁路交通图，公路交通图，市区交通图，自来水管网系统，甚至电路图在研究某些问题时也可简化为由点和线组成的图形，如：图论就是研究这些由点和线组成的图形的问题1.七桥问题18世纪东普鲁士有一个城市称为个普尼斯堡，它位于普雷格尔河畔，河中有两个小岛，通过七座桥彼此相联（如图）。当时有人提出：能否从某个地点出发经过每个桥一次且仅一次然后返回出发点？图论起源于18世纪，是一门较为年青的数学分支。但在历史上遗留了许多著名
2、的图论问题，例如：ABCDEuler的解：2.Hamilton周游世界问题1859年Hamilton提出这样一个问题：一个正十二面体有20个顶点，它们代表世界上20个重要城市。正十二面体的每个面均为五边形，若两个顶点之间有边相连，则表示相应的城市之间有航线相通。Hamilton提出“能否从某城市出发经过每个城市一次且仅一次然后返回出发点？”3.四色问题1840年数学家茂比乌斯（Möbius）提出一个猜想：任何平面地图，总可以把它的一个国家用四种颜色的一种着染，使相邻国家着不同色。这就是著名的四色猜想。如：1890
3、年希五德（Heawood）指出“4换为5”猜想成立。1976年两位数学家在三台百万次的电子计算机上花了1200小时证明了猜想成立。猜想成为定理。4.中国邮路问题1962年中国数学家管梅谷提出：一个邮递员从邮局出发递送邮件，要求对他所负责的辖区的每条街至少走一次，问如何选取路程最短的路线？这个问题称为中国邮路问题。该问题可用专门的算法来求解。图论的应用范围很广，它不但能应用于自然科学，也能应用于社会科学。它非但广泛应用于电信网络、电力网络、运输能力开关理论、编码理论、控制论、反馈理论、随机过程、可靠性理论、化学化合
4、物的辨认、计算机的程序设计、故障诊断、人工智能、印刷电路板的设计、图案识别、地图着色、情报检索，也应用于语言学、社会结构、经济学、运筹学、遗传学等。图论作为一个数学分支，有一套完整的体系和广泛的内容，在这里我们只准备介绍图论的初步知识，其目的是今后在其它有关学科的学习和研究时，可以用图论的基本知识作为工具。§9.2图论的基本概念9.2.1-5图的定义-分类定义1一个图是一个序偶,记为G＝，其中：1)V＝{v1,v2,v3,…,vn}是一个有限的非空集合,vi(i＝1,2,3,…,n)称为结点
5、,简称点,V为结点集；2)E＝{e1,e2,e3,…,em}是一个有限的集合，ei（i＝1,2,3,…,m）称为边,E为边集，E中的每个元素都有V中的结点对与之对应。1.定义及相关概念说明：（1）若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e＝(u，v)，这时称u，v是边e的两个端点；可用图形表示为：（2）若边e与有序结点对相对应，则称边e为有向边(或弧)，记为e＝，这时称u是边e的始点(或弧尾).v是边e的终点(或弧头)，统称为e的端点.可用图形表示为euveuv(3)图除用集
6、合表示(定义)外,还可用图形表示:用小圆圈表示V中的结点，用由u指向v的有向线段或曲线表示有向边，无向线段或曲线表示无向边(u,v).例1设V={v1,v2,v3,v4}，E={e1,e2,e3,e4,e5}，满足e1=v1v2，e2=v2v3，e3=v2v3，e4=v3v4，e5=v4v4则G=是一个图。v1v2v3v4e1e2e3e4e5图中边集E的边也可直接由点对表示，而将E作为多重集（即允许E中有相同元素的集合）。例2设V={v1,v2,v3,v4}，E={v1v2,v1v2,v2v3
7、}，则H=是一个图。v1v2v3v4图可分为：（1）无向图－每边均为无向边的图，如上图；（2）有向图－每边均为有向边的图，如下图；（3）混合图－既有无向边又有有向边的图。图中，同一条边的两个端点称为相邻；若两条边有一个共同的端点，则这两条边也称为相邻；若点u是边e的端点，则称u与e相关联。称两个端点相同的边为环，不与任何边相关联的点称为孤立点。若图中n条不同的边e1,e2,…，en,（n≥2）中的每一条边的两个端点均为u和v，则这些边称为平行边（或n重边，简称为重边）。不是重边的边称为单边。2.点边间的
8、关系及一些特殊点与边简单图无边且仅有一个点的图称为平凡图。有平行边的图称为多重图；非多重图称为线图：既无平行边又无环的图称为简单图。零图：E＝的图；（n，m）图：n个点m条边的图多重图例如：平凡图3.一些特殊的图4.图的矩阵表示定义9.2.2设图G=，其中V={v1,v2,…,vn}，并假定结点已经有了从v1到vn的次序，则n阶方阵AG=(aij)nxn称为G
