《我要讲的图论3课件》由会员分享，可在线阅读，更多相关《我要讲的图论3课件（109页珍藏版）》请在金锄头文库上搜索。
1、图论初步,1.图的基本概念 2.最小树问题,本 章 内 容,引言,图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。 哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸连接起来。问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次
2、，再回到起点。,哥尼斯堡七桥示意图,问题1:七桥问题 能否从任一陆地出发通过每座桥恰好一次而 回到出发点？,例：七桥问题,问题：能否从某一点开始一笔画出这个图形，最后回到原点，而不重复。,欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。,例：中国邮路问题,一个邮递员送信，要走完他所负责的全部街道分送 信件，最后返回邮局。邮递员都会本能地以尽可能少的 行程完成送信任务。,问题：他如何走？,点：路口； 边：两路口之间道路，第i条道路长ei
3、。,问题：求一个圈，过每边至少一次，并使圈的长度最 短。,例：四色猜想,能否用四种颜色给地图染色，使相邻的国家有不同的颜色。,点：国家； 边：两个国家有公共边界。,问题：能否用四种颜色给平面图的点染色，使有公共 边的点有不同的颜色。,四色问题又称四色猜想、四色定理，是世界近代三大 数学难题之一。地图四色定理(Four color theorem)最 先是由一位叫古德里（FrancisGuthrie）的英国大学生 提出来的。,电子计算机问世以后，由于演算速度迅速提高，加之人机 对话的出现，大大加快了对四色猜想证明的进程。美国 伊利诺大学哈肯在1970年与阿 佩尔合作编制一个很好的程序。就在197
4、6年6月，他们 在美国伊利诺斯大学的两台不同的电子计算机上，用了 1200个小时，作了100亿判断，终于完成了四色定理的证 明，轰动了世界。,有二十个顶点标以二十个城市的名字，要求游戏者找一条从某一城市出发的路线，它经过每一个城市恰好一次，并且最后回到出发点。 点：城市 边：城市之间的道路 问题：游戏者怎么走才能恰好每个城市走一次，而 且不重复？如图：,例： Hamilton,(哈密尔顿图、 环球旅行游戏),有15盒饼干，其中14盒的质量相同，另有1盒少了几块， 如果用天平称，至少几次保证可以找出这盒饼干？,第一节 图的基本概念,点：研究对象（陆地、路口、国家、球队）；,点间连线：对象之间的特
5、定关系（陆地间有桥、路口 之间道路、两国边界、两球队比赛及结果)。,对称关系：桥、道路、边界；,用不带箭头的连线表示，称为边。,非对称关系：甲队胜乙队，用带箭头的连线表示， 称为弧。,图：点及边（或弧）组成。,例：有甲、乙、丙、丁、戊五个球队，各队之间比赛 情况如表：,5.1 图论的基本概念,图论中的“图”并不是通常意义下的几何图形或物体的形状图, 而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统.,定义1 一个有序二元组(V, E ) 称为一个图, 记为G = (V, E ), 其中, V称为G的顶点集, V, 其元素称为顶点或结点, 简称点; E称为G的边集, 其元素称为边
6、, 它联结V 中的两个点, 如果这两个点是无序的, 则称该边为无向边, 否则, 称为有向边. 如果V = v1, v2, , vn是有限非空点集, 则称G为有限图或n阶图.,如果E的每一条边都是无向边, 则称G为无向图(如图1); 如果E的每一条边都是有向边, 则称G为有向图(如图2); 否则, 称G为混合图.,图 1,图 2,并且常记,V = v1, v2, , vn, |V | = n ; E = e1, e2, , em(ek=vivj ) , |E | = m.,称点vi , vj为边vivj的端点. 在有向图中, 称点vi , vj分别为边vivj的始点和终点.,例：四个城市：v1、
7、v2、v3、v4，其中v1和v2、v1 和v4，v2和v3间有直达的高速公路相连，写出其集 合并画出此图。,解：,G=(V,E),V=(v1,v2,v3,v4),E=(l1,l2,l3),其中：,l1=(v1,v2),l2=(v1,v4),l3=(v2,v3),1. 简单图与多重图,某条边两个端点相同，称这条边为环。 若两点之间有多于一条的边，称这些边为多重边。,无环、无多重边的图称为简单图。,多重图：无环、但允许有多重边。,二、图论中常用术语,简单图,任意两点均相邻的简单图称之为完全图。 n 个点的完全图记为 Kn，图 6.2.4 中给出的分别是 K2，K3，K4。,2. 相邻与关联,若两条
8、边有一个公共的端点，则称这两条边相邻接。,点与边关联,点与点相邻,边与边相邻接,3. 次与悬挂点、孤立点,图G中以点v为端点的边的数目，称为v在G中的次， 记为d（v）。,d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1,次为1 的点为悬挂点，悬挂点的关联边称为悬挂边，次为零的点称为孤立点。,定理1 图G=（V，E）中，所有点的次之和为边数 的两倍， 即,3. 奇点与偶点,次为奇数的点称为奇点，否则称为偶点。,定理2 任一图中奇点的个数为偶数。,5. 链与圈,给定一个图G=（V，E），G中的一个点、边交错序列（vi1，ei1，vi2，ei2，vik-1，eik-1，vik），如果
9、满足eit=vit，vit+1（t=1，2，k-1），则称为一条联接vi1和vik的链，记为=（vi1，vi2，vik）。,链（vi1，vi2，vik）中，若vi1=vik ，称之为一个圈，记为C= （vi1，vi2，vik-1， vi1 ） 。,初等链：链中点都不同。 简单链：链中边都不同。,简单链：1=（v2，v1，v3，v6，v4，v3，v5）,初等链：2=（v2，v1，v3，v5）,简单圈：C1=（v1，v2，v4，v3，v5，v6，v3 ，v1 ）,初等圈：C2=（v1，v2，v4，v6，v5，v3 ，v1 ）,有向图中，不考虑弧的方向，有类似链（圈）的定义。当链（圈）上弧的方向一致
10、时，称为路（回路）。,用图论思想求解以下各题,例1、一摆渡人欲将一只狼，一头羊，一篮菜从 河西渡过河到河东，由于船小，一次只能带一物 过河，并且，狼与羊，羊与菜不能独处，给出渡 河方法。,解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0),共有24 =16 种状态.在河东岸的状态类似记作.,由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的,从而对应状态(1,0,0,1), (1,1,0,0), (1,0,0,0)也是不允许的. 以可允许的10个状态向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图. 根据此图便可找到
11、渡河方法.,(1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0) (0,0,0,0) (0,0,0,1) (0,0,1,0) (0,1,0,0) (0,1,0,1),(0,1,0,1) (0,1,0,0) (0,0,1,0) (0,0,0,1) (0,0,0,0) (1,0,1,0) (1,0,1,1) (1,1,0,1) (1,1,1,0) (1,1,1,1) 河西=(人,狼,羊,菜) 河东=(人,狼,羊,菜),将10个顶点分别记为A1, A2, , A10 ,则渡河问题化为在该图中求一条从A1到A10的路. 从图中易得到两条路： A1 A6 A
12、3 A7 A2 A8 A5 A10; A1 A6 A3 A9 A4 A8 A5 A10.,由图，有两个解都是经过7次运算完成，均为最优解,例3、证明：在任意6人的集会上，总有3人互相认 识，或总有3人互相不认识。,3. 连通图,给定图G=（V，E），任何两点间至少有一条链，则称G是连通图，否则为不连通图。,若G是不连通的，它的每个连通部分称为G的连通分图。,三 、一些特殊图类,1.平凡图 节点数n=1,边数m=0的图。,2.零图 边数m=0的图。,5. 完备图,无向图的完备图：任何两点之间有一条边；,有向图的完备图：任何两点u与v之间有两条有向边（u，v）及（v，u）。,基本图：把有向图的每条
13、边除去方向得到的无向图。,4.树 无圈连通图。,7.网络,若对图G=（V，E）中每条边vi，vj赋予一个数wij，则称wij为边vi，vj的权，并称图G为网络（或赋权图）。,网络：无向网络、有向网络。,6.正则图 如果G中每个点的次数都相同，则G叫做正则图。,通过图（无向图或有向图）中所有边一次且仅一次行遍图 中所有顶点的通路称为欧拉通路，通过图中所有边一次且 仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路 的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉 回路的图称为半欧拉图。,欧拉回路要求边不能重复，结点可以重复. 笔不离开纸， 不重复地走完所有的边，且走过所有结点，就是
14、所谓的 一笔画.,简单说欧拉通路就是首尾不相接，而欧拉回路要求首尾 相接。,无向图是否具有欧拉通路或回路的判定:,欧拉通路:图连通；图中只有2个度为奇数的节点 (就是欧拉通路的2个端点),欧拉回路:图连通；图中所有节点度均为偶数,有向图是否具有欧拉通路或回路的判定:,欧拉通路:图连通；除2个端点外其余节点入度=出度； 1个端点入度比出度大1；一个端点入度比出度小1,欧拉回路:图连通；所有节点入度=出度,判断下列图形是否是欧拉图,欧拉通路:图连通；图中只有2个度为奇数的节点 (就是欧拉通路的2个端点),欧拉回路:图连通；图中所有节点度均为偶数,（1）,（2）,（3）,（1）即不是欧拉图，也不存在
15、欧拉通路。,（2）不是欧拉图，但存在欧拉通路。,（3）是欧拉图,a,b,c,蚂蚁比赛问题,甲、乙两只蚂蚁分别位于结点a、b处。 设图中边长度是相等的。甲、乙进行比赛： 从它们所在的结点出发，走遍图中的所有边 最后到打结点c。如果它们的速度相同， 问谁先到达目的地？,(甲),（乙）,判断下列图形是否是欧拉图,有向图是否具有欧拉通路或回路的判定:,欧拉通路:图连通；除2个端点外其余节点入度=出度； 1个端点入度比出度大1；一个端点入度比出度小1,欧拉回路:图连通；所有节点入度=出度,哈密顿回路,通过图G的每个顶点一次且仅一次的回路称为哈密顿回路。,具有哈密顿回路的图称为哈密顿图。,哈密顿通路是通过
16、图G的每个顶点一次且仅一次的通路。,欧拉图和哈密顿图的区别在于 欧拉回路是简单回路（边不重复，点重复）， 而哈密顿图是基本回路。 欧拉图遍历边，而哈密顿图遍历顶点。,它们之间几乎没有什么联系。,五、图的矩阵表示,图的矩阵表示方法有：邻接矩阵、关联矩阵、可达矩阵、权矩阵等。,1.邻接矩阵,邻接矩阵用于描述两个顶点之间是否有边（弧）相连。,对于有n个顶点的无向图G=(V,E) ，定义邻接矩阵(B=bij)nn 。其中，,对于有几个顶点的有向图G=(V,A) ，定义邻接矩阵(B=bij)nn 。其中，,(讲究 方向),例题1 已知无向图所示，求其邻接矩阵。,则,显然，无向图的邻接矩阵是关于对角线的对称矩阵。,例 2 已知：图所示，求其邻接矩阵。,则：,v1 v2 v3 v4 v5 v6 v1 0 1 1 0 0 0 v2 0 0 1 1 1 0 v3 0 0 0 1 0 0 v4 0 0 0
