第七章图的基本概念ppt课件.ppt

《第七章图的基本概念ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章图的基本概念退出8/4/20211图论是近年来发展迅速而又应用广泛的一门新兴学科,皆在解决离散型的优化问题。它最早起源于一些数学游戏的难题研究，如1736年欧拉（Euler解决的哥尼斯堡七桥问题），以及如迷宫问题，匿门博奕问题，棋盘上马的行走路线问题等在民间广泛流传的一些游戏难题。这些古老的难题，当时吸引了很多学者的注意，在这些问题研究的基础上又继续提出了著名的四色猜想，哈密尔顿环游世界数学难题。1847年，克希霍夫（Kirchhoff）用图论分析电路网络，这是图论最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控

2、制论，博奕论以及计算机科学等各个领域的问题时，显示出越来越大的效果。图论在各种物理学科，工程领域，社会科学和经济问题的广泛应用，使它受到数学和工程界的特别重视。如通讯网络的优化设计，交通站点的合理布局，生产组织的健全架构和工程作业的有效控制等问题，用图论的方法解决十分方便图论是计算机及其相关专业的重要基础课。通过图论学习可以为数据结构、数据库、操作系统、编译程序及人工智能等后续课程的学习奠定基础。哥尼斯堡（Konigstberg，现加里宁格勒）城市有一条横贯全城的普雷格尔（Pregel）河，河中有2个岛，河上有7座桥与城市的各部分联接，如下图所示，

3、每逢假日，城中居民进行环城逛游。不知何时何日何人提出下面问题，能不能设计一次“遍游”．使得从某地出发对每座跨河桥只走一次，而在通历了七桥之后却又能回到原地。哥尼斯堡七桥问题哥尼斯堡七桥问题反复的奔走试行和失败，使人们对成功的可能发生疑惑，猜想问题无解，但又谁也说不清其中道理，于是有好事者去请教年轻的数学家欧拉(Euler)，刚开始欧拉也看不出这是一个数学问题,1736年，29岁的欧拉把这一问题化成数学问题，严格地论证了上述“七桥问题”无解，并由此开创了图论与拓扑学的思维方式和诸多概念与理论，1736年遂被公认为图论学科的历史元年，欧拉被尊为图论与拓

4、扑学之父.欧拉回路简单图多重图表示实际呼叫的呼叫图可以非常大。如AT研究的一个呼叫图，大约有2亿9千万个顶点和40亿条边。伪图有向简单图有向多重图7.1无向图及有向图什么是图?可用一句话概括，即：图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型。因为它显得太抽象，不便于理解，所以有必要给出把图作为代数结构的一个定义。无向图的基本概念无向图G：一个有序二元组(V,E),记为G=(V,E)G的点集合：（例如：图（1）中的V=（1，2，3，4，5）是一个无向图的点的集合）G的边集合：E={eij}且eij={vi,vj}为右图无序二

5、元组eij的端点：有eij={vi,vj}，则称vi和vj为eij的端点，且称eij连接点vi和vj。若vi≠vj，称eij与vi（或vj）的关联次数为1；若vi＝vj，称eij与vi的关联次数为2；若vi不是eij的端点，称eij与vi的关联次数为0；环：两个端点重合为一点的边孤立点：不与任何边关联的点34512关联：一条边的端点称为这条边的关联相邻：与同一条边关联的端点称为是相邻的，同时如果两条边有一个公共端点，则称这两条边是相邻的分类设G=〈V，E〉为一个图。1）按结点的个数分类（1）若

6、V(G)

7、,

8、E(G)

9、都是有限集合，则称G是有限图。

10、（2）若

11、V(G)

12、=n,则称G为n阶图。（3）E(G)=,则称G为零图。若

13、V(G)

14、=0,称G为空图；若

15、V(G)

16、=1,称G为平凡图，而

17、V(G)

18、=n,称G为n阶零图2）按同一对结点间的边数分类：平行边：（1）在无向图中，关联一对顶点的无向边如果多于一条，则称这些边为平行边，平行边的条数称为重数。（2）在有向图中，关联一对顶点的有向边如果多于一条，并且这些边的始点与终点相同（即方向相同），则称这些边为平行边。定义7.1.1在图G=中，如果任何两结点间不多于一条边(对于有向图中，任何两结点间不多于一条同向弧)，并且任何结点无环，则

19、图G称为简单图；若两结点间多于一条边(对于有向图中，两结点间多于一条同向弧)图G称为多重图。3）按图的边旁有无（字母，数量）特征分类：定义7.1.2给每条边或弧都赋予权的图G=，称为加权图，记为G=，其中W表示各边之权的集合。加权图在实际中有许多应用，如在输油管系统图中权表示单位时间流经管中的石油数量；在城市街道中，权表示表示通行车辆密度；在航空交通图中，权表示两城市的距离等等。4）按图的任意两个结点间是否有边连接分类：定义7.1.3无向完全图：设G为n阶无向简单图，若D中每个顶点均与其余的n-1个顶点相邻，则称G为n阶无向

20、完全图，简称n阶完全图，记作Kn定义7.1.4有向完全图：设D为n阶有向简单图，若D中每个顶点都邻接到其余的n-1个顶点，