资源描述：
《离散数学图论部分.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第四部分图论图论问题的起源18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块,它们通过七座桥相互连接,如下图.当时该城的市民热衷于这样一个游戏:“一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点？”SNAB陆地岛屿岛屿陆地哥尼斯堡七桥问题如何不重复地走完七桥后回到起点？。。。。ABCD当时人们热衷于这样的游戏：设想从任一个地方出发通过每座桥一次且仅一次后回到原地,这是否可能?但多次实践都发现不行。1727年欧拉的朋友向欧拉提出了这个问题是否有解？1736年欧拉用图论的方法解决了这个问题,写了第一篇图论的论文,成为图论的创始人。后来称此问题为哥
2、尼斯堡七桥问题。但在此之后100年间，没有大的进展。直到Kirchhoff(克希霍夫)用树的理论解决了电网络问题。这些结果引起了人们的重视,图论的研究进入了一个发展时期。直到1920年,科尼格(Konig)撰写了许多图论方面的论文。在1936年科尼格(Konig)发表了第一本图论书籍《有限图与无限图理论》,总结了200年来图论研究的主要成果。此后的50年,图论经历了一场爆炸性的发展,成为数学科学中一门独立的学科。几十年来图论在理论上和应用上都得到很大的发展,特别是在近30多年来由于计算机的广泛应用而又得到飞跃的发展。在计算机科学、运筹学、化学、物理和社
3、会科学等方面都取得了不少成果，对计算机学科中的操作系统研究、编译技术、人工智能和计算机网络等方面都有广泛的应用。这里主要讨论图的基本概念和算法,为今后的学习和研究打下基础。本章首先给出图、简单图、完全图、子图、路和图的同构等概念，接着研究了连通图性质和规律，给出了邻接矩阵、可达性矩阵、连通矩阵和完全关联矩阵的定义。最后介绍了欧拉图与哈密尔顿图。图的定义例画出下列图形。G=,其中V={v1,v2,v3,v4,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v1,v5),(v2,v5),(v4,v5)}。v1v2v
4、3v4v5e1e2e3e4e5e6例：画出下列图形。(2)D=,其中V={v1,v2,v3,v4},E={,,,,,,}。v1v2v3v4e1e2e3e4e5e6e7图相关的概念和规定设G=为一有向图或无向图。V、E分别表示G的顶点集、边集，
5、V
6、、
7、E
8、分别表示G的顶点数、边数。若
9、V
10、=n,则称G为n阶图。(2)若
11、V
12、、
13、E
14、均为有限数，则称G为有限图这是本书讨论的重点。(3)在图G中，若E=,则称G为零图。此时若
15、V
16、=n，则
17、称G为n阶零图，记作Nn。若
18、V
19、=1，则称G为平凡图。(a)图(b)零图(c)完全图没有任何边的图称为零图；只有一个点，没有边的图称为平凡图；任意两点之间都有边的图称为完全图。v1v2v3v4v5e1e2e3e4e5e6在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数。例：下图中e4与e5是平行边。v1v2v3v4v5e2e3e4e5e6e7e8在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点与终点相同(即方向相同)，则称这些边为平行边。例：下图中e3与e4是平行边,e7与e8不是平行边（因为e7与
20、e8方向不同）含平行边的图称为多重图；既不含平行边也不含环的图称为简单图。本书主要讨论简单图的相关结论。设G=为无向图，ek=∈E,则称vi,vj为ek的端点，ek与vi或ek与vj是彼此关联的。无边关联的顶点称为孤立点。若一条边所关联的两个顶点重合，则称此边为环。vi≠vj，则称ek与vi或ek与vj的关联次数为1，若vi=vj，则称ek与vi的关联次数为2；若vi不是ek的端点，则称ek与vi的关联次数0。设G=为无向图，vi,vj∈V,ek,el∈E,若存在一条边e以vi,vj端点，即e=(vi,vj)则称vi与
21、vj是彼此相邻的。简称相邻的。(2)若ek与el至少有一个公共端点，则称ek与el是彼此相邻的。简称相邻的。设D=为有向图,vi,vj∈V,ek,el∈E,若ek=,除称vi,vj是ek的端点外，还称vi为ek的起点，vj为ek的终点，并称vi邻接到vj,vj邻接于vi。顶点的度设G=为一无向图，vi∈V,称vi作为边的端点的次数之和为vi的度数，简称为度，记作deg(vi)（或d(vi)）。设D=为一有向图，vj∈V,称vj作为边的始点的次数之和,为vj的出度，记作d+(vj);称vj作为边的终点的次数之和
22、,为vj的入度，记作d-(vj);称d+(vj)+d-(vj)为vj的度数，记作d(vj)。称
