《离散数学第7章+图论1图的基本概念》由会员分享，可在线阅读，更多相关《离散数学第7章+图论1图的基本概念（39页珍藏版）》请在金锄头文库上搜索。
1、第7章 图论,胡 敏,合肥工业大学计算机与信息学院,计算机应用研究所,第七章 图论,引言 7.1 图的基本概念 7.2 路与连通 7.3 图的矩阵表示 7.4 最短路径问题 7.5 图的匹配 8.1 Euler图和Hamilton图 8.2 树 8.3 生成树 8.4 平面图,目的,(1) 掌握图论的基本问题、理论与方法,(3) 了解图论在信息学科中的应用以及在数学竞赛、数 学建模中的应用,(2) 初步掌握运用图论的理论和方法解决实际问题的能 力,为什么要学习图论？ 图论计算机问题求解的描述工具。 可以采用图论的成果和方法； 最重要的是： 可以培养我们思考问题和解决问题的能力。,引言,应用背景
2、 图论在现代科学技术中有着广泛的应用，如：网络设计、计算机科学、信息科学、密码学、DNA的基因谱的确定和计数、工业生产和企业管理中的优化方法等都广泛的应用了图论及其算法。 计算机网络,引言,某学校网络架构图,应用背景 计算机网络 电路模拟,引言,例：Pspice、Cadence 、ADS,Pspice,Cadence,应用背景 计算机网络 电路模拟 交通网络,引言,航空网络!,捷運路線图！,引言,应用背景 有向图,有单行道的街道！,行程表！,引言,应用背景 Social Network,High School Dating,corporate e-mail,Reference: Bearman
3、, Moody and Stovel, 2004 image by Mark Newman,Reference: Adamic and Adar, 2004,引言,应用背景 The Internet,The Internet as mapped by The Opte Project http:/www.opte.org,net, ca, us com, org, mil, gov, edu jp, cn, tw, au de, uk, it, pl, fr br, kr, nl,引言,More Applications Hypertexts 网页包含到其他网页的超链接。整个Web是一个图.
4、搜索引擎需要图处理算法。 Matching 职位招聘，如何有效将职位与应聘者匹配？ Schedules 工程项目的任务安排，如何满足限制条件，并在最短时间内完成？ Program structure 大型软件系统，函数（模块）之间调用关系。编译器分析调用关系图确定如何最好分配资源才能使程序更有效率。,引言,图论的产生和发展 1.哥尼斯堡七桥问題(Bridges of Koenigsberg),问题 能否从某一块陆地出发，走遍每一座桥，且每一座桥只能走一次，最后回到出发点。,引言,欧拉路径：解決哥尼斯保七桥问題,数学家欧拉(Euler, 1707-1783) 于1736年严格的证明了上述哥尼斯堡
5、七桥问题无解，并且由此开创了图论的典型思维方式及论证方式,原來是一笔画问题啊！,问题：是否能从四块陆地中的任一块开始，通过每座桥恰好一次再回到起点？,是否能从任意一个顶点开始，通过每条边恰好一次再回到起点？,转化,包含两个要素：对象（陆地）及对象间的二元关系（是否有桥连接）,引言,2.四色猜想 在任何平面或球面上的地图，只用四种颜色涂色，就可使得相邻区域涂上不同颜色。,1976年，Appel, Haken 和 Koch 利用计算机辅助证明了四色猜想，但其数学证明仍不理想。,引言,3. Hamilton周遊世界问題,哈密頓路径至今尚无有效方法來解決！,正十二面体有二十个顶点表示世界上20个城市各
6、经每个城市一次最后返回原地,投影至平面,反映到图论上就是判断一个给定的图是否存在一条含所有顶点的回路。,引言,4.最短路径问題 (Shortest Path Problem),最快航線,最快的routing,引言,最短路径算法Dijkstra算法,可以求出從某一点到图上其他任一点的最短路径,引言,5.走迷宫与深度优先搜索(Depth-First Search),老鼠走迷宮深度优先搜索,一直往前走 碰壁就回头換条路找 沿途要记录下走过的路线,两点之间有无道路可通？有多少条道路可通？哪条路最短？,引言,图论的重要地位 图论在计算机科学领域中有着重要地位 操作系统进程演变状态图和目录树搜索。 人工智
7、能图搜索策略和知识的表示 数据结构的二大类非线性结构：树和图 数据库系统的实体-联系模型和文件组织 自动机理论,引 言,图论的发展 1847年基尔霍夫运用图论解决了电路理论中求解联立方程的问题，引进了“树”概念。 1857年Cayley非常自然在有机化学领域发现了一种重要的图，称为“树”，解决了计算饱和氢化物同分异构体的数目。 1936年,哥尼格的第一本图论专著问世,才使得图论成为一门独立的数学学科. 1946年,随着世界上第一台计算机的问世,使图论的发展突飞猛进.,引言,图论相关的交叉研究 代数图论 拓扑图论 化学图论 算法图论 随机图论 极值图论 网络图论 模糊图论 超图论 以往数学家习惯
8、将纯数学应用于其它学科，Gowers将图论和组合数学中的Ramsey理论应用于泛函分析的研究，获得了1998年的Fields奖。,7.1 图的基本概念,1.图的定义 图论中讨论的“图”，不是微积分、解析几何、几何学中讨论的图 形，而是客观世界中某些具体事物间联系的一个数学抽象。如二元关系的关系图，就不考虑点的位置及连线的长短曲直，而只关心哪些点之间有连线。这种数学抽象就是图论中“图”的概念。,一堆顶点和边的组合！ Set of vertices connected pairwise by edges.,7.1 图的基本概念,1. 图的定义 定义7.1.1：所谓图(graph)G是一个三元组，记
9、作G，其中 （1）图G的结点 组成的结点集(vertex set)记作V(G)v1,v2,vn, (V(G) ) （2）图G的边 组成的边集(edge set)记作 ，且ei为 (vj,vt )或 。若ei(vj,vt )，称ei为以vj和vt为端点(end vertices)的无向边 (undirected edge)；若ei，称ei为以vj为起点(origin)，vt为终点(terminus) 的有向边(directed edge)。 （3） (G)：EVV称为关联函数(incidence function）。,注：这里,的交叉点不是我们研究的顶点。,与,点集合人 边集合朋友关系,7.1
10、图的基本概念,当图的顶点集和边集被给定时，可以省去，可以将图简记为 G= 。 无向边 若边e i的两个顶点vj, vk，不能区分起点和终点，则称该边为无向边。无向边e 用无序偶（vj , vk）表示。 有向边 若边的一起始顶点为vj，另一终止顶点为vk，则称该边为有向边。有向边用有序偶 表示。 无向图 每一条边都是无向边的图称无向图 。 有向图 每一条边都是有向边的图称有向图 。 混合图 一些边是有向边，另一些边是无向边的图，称为混合图 。 邻接边 关联于同一顶点的两条边，被称为邻接边。 邻接点 若两个顶点由同一条边关联，则这两个顶点被称为是邻接点。 孤立顶点 不与任何顶点相邻接的顶点，被称为
11、孤立顶点。 零图 仅由若干孤立顶点组成的图，被称为零图 。 阶 图G的顶点个数称为图G的阶,7.1 图的基本概念,图形表示如右：,图形表示如右：,7.1 图的基本概念,平凡图 仅由一个孤立顶点构成的图，被称为平凡图。 自回路或环 关联于同一顶点的一条边，被称为自回路或闭环。 平行边 若有两条有向边，他们的起点和终点相同，称他们为有向平行边。 我们把联结于一对顶点间的多条边称为平行边。 简单图 不含有任何平行边和自回路的图，被称为简单图。 多重图 任何含有平行边的图 ，被称为多重图。 完全图 简单图G=中，若每对顶点间都有边相连，则称该图为完全图。 无向完全图 有n个顶点的无向完全图 记作Kn。
12、 Kn 的边数 n个顶点的无向完全图Kn的边数为 n (n-1)/2. 对称有向图对于无向图G，将G中的每条边用两条与e有相同端点的对称边e和e 来代替后得到的一个有向图 。 有向完全图 对Kn中每条边任意确定一个方向，称该图为n顶点的有向完全图。 有向完全图的边数 n个顶点的有向完全图边数也为n(n-1)/2 。 完全有向图 完全图的对称有向图称为完全有向图(complete digraph），记作 。,7.1 图的基本概念,2.图的顶点度数 (简称度),顶点的入度、出度,最大度,最小度,相应地还有,，,，,，,设D是有向图,7.1 图的基本概念,如例1的(2)中，,，,。,7.1 图的基本
13、概念,3.握手定理,定理1：,定理2：,7.1 图的基本概念,4.度数序列 例3 是否可以画出一个简单的无向图，使得各点度数与下列的序列一致。 （1）2,2,2,2,2,2 （2）2,2,3,4,5,6 （3）1,2,3,4,4,5 解：（1）可以，如图7.1.5的G1或G2。 （2）不可以。在6个结点的简单无向图中，其中每个结点最多与其余5个结点相邻，即(G)5。 （3）不可以。任何图中，度数为奇数的结点只能有偶数个。,提示： 根据握手定理，非负整数序列能够构成无向图的度数序列的充要条件是 其和为偶数，即奇数度顶点的数目为偶数个。但这些无向图未必一定是简单图。,7.1 图的基本概念,例4 下
14、列各组数中，哪些能够构成无向图的度数序列? 哪些能够构成简单无向图的度数序列?,1，1，1，2，3 2，2，2，2，2 3，3，3，3 1，2，3，4，5 1，3，3，3,7.1 图的基本概念,5.图的同构,定义：,设两个无向图,，,，,若存在一一对应的映射函数,，使得对于任意的,，当且仅当,并且,与,重数相同，则称,与,同构，,记作,。,换句话说，当两个简单图同构时，两个图的结点之间具有保持相邻关系的一一对应。 目前，判断两个图是否同构，还只能根据定义。也就是说，两个图是否同构还没有很简单的判别方法。 两图同构的必要条件是：（1）两图结点数相等。（2）边数相等。（3）度数相同的结点个数相等。
15、但这仅是必要条件，不是充分条件。,7.1 图的基本概念,5.图的同构,例2、,7.1 图的基本概念,6.图的运算,（1）子图定义：,设,是两个图，若,，,，且,，则称,是,的子图，,是,的母图，记作,。,7.1 图的基本概念,6.图的运算,导出子图,非空,，以,为顶点集，,以两端均在,中的边的全体为边集的,的,子图，称,的导出子图，记做G 。,非空,，以,为边集，以,中边关联的顶点的全体为顶点集,的子,图，称,的导出子图，记作G 。,7.1 图的基本概念,例3、,上图中，(1)(6)都是(1)的子图，,其中(2)(6)为真子图，,(1)(5)为生成子图。,7.1 图的基本概念,(2)并图、交图
16、、差图和环和图定义,设G1和G2都是图G的子图,。,仅由G1和G2中所有边与结点组成的图称为G1和G2的并(union），记作G1G2。,仅由G1和G2的公共边组成的图称为G1和G2的交（cap），记作G1G2。,仅由G1中去掉G2中的边组成的图称为G1和G2的差（difference），记作G1G2。,在G1和G2的并中去掉G1和G2的交所得到的图称为G1和G2的环和（ring sum），记作G1 G2，即 G1 G2(G1G2)(G1G2)(G1G2 )(G1 G2 ),7.1 图的基本概念,(3)补图定义,如例3中,概念巩固,例1： 是否可以画出一个简单的无向图，使得各点度数与下列的序列一致。 （1）2,2,2,2,2,2 （2）2,2,3,4,5,6 （3）1,2,3,
