图论PPT学习教案

1、会计学1图论图论第2页1. 图论的产生 图论是运筹学应用十分广泛的一个分支。瑞士数学家欧拉（E Euler）于 1736 年发表了一篇题为“依据几何位置的解题方法”的论文，有效地解决了哥尼斯堡七桥难题（欧拉证明了每个点都只与奇数条线相关联，所以从某一点开始，不重复地走过7座桥，最后回到出发点是不可能的），这是有记载的第一篇图论论文，欧拉被公认为图论的创始人。 第1页/共171页第3页ACBD第2页/共171页第4页2. 图论的发展 1736 年 1936 年：匈牙利数学家 O. Knig 于1936 年出版了名为有限图与无限图的理论，为图论研究的第一本专著。从 1736 年欧拉的第一篇论文，到

2、这本专著的出版，前后经历 200 年之久，这一时期图论的发展是缓慢的。 第3页/共171页第5页1936年20世纪中期：电子计算机和离散数学问题的发展，使得作为提供离散数学模型的图论得以迅速发展。 目前图论被广泛应用到管理科学、计算机科学、信息论、控制论等各个领域，并取得了丰硕的成果。 第4页/共171页第6页1. 图 由一些点和一些点之间的连线所组成的二元组，称为图。 2. 顶点 图中点集 V = v i 中的元素 v i 称为顶点。 第5页/共171页第7页3. 边和弧 图中，两顶点之间的连线为无向的（不带箭头），称为边，记为 E = ei 。一条连接顶点 vi 和 vj 的边记为 vi

3、, vj 。 eivivj第6页/共171页第8页图中，两顶点之间的连线为有向的（带箭头），称为弧，弧为 A = ai 。一条由顶点 vi 指向顶点 vj 的弧记为 ( vi , vj ) 。 aivjvi第7页/共171页第9页4. 有向图和无向图 由点和边所构成的图，称为无向图，记为 G= ( V, E ) ，式中 V 是无向图 G 的点集合； E 是无向图 G 的边集合。 由点和弧所构成的图，称为有向图，记为 D = ( V, A ) ，式中 V 是有向图的点集合G ； A 是有向图 G 的弧集合。 第8页/共171页第10页无向图有向图第9页/共171页第11页5. 无向图中顶点数、边

4、数的表示方式 顶点数：p(G)，简记为p。 边 数：q(G)，简记为q。 6. 有向图中顶点数、弧数的表示方式 顶点数：p(D)，简记为p。 边 数：q(D)，简记为q。 第10页/共171页第12页1. 端点、始点、终点 无向图 G = ( V, E ) 中，边 e = u, v E，称顶点 u 和 v 是边 e 的端点，也称顶点 u 和 v 是相邻的。 euv第11页/共171页第13页有向图 D = ( V, A ) 中，弧 a = ( u, v ) A，称顶点 u 是弧 a 的始点，称顶点 v 是弧 a 的终点。 uv第12页/共171页第14页2. 关联边（弧） 无向图 G = (

5、V, E ) 中，边 e = u, v E，称边 e 是顶点 u 的关联边，也称边 e 是顶点 v 的关联边。 euv第13页/共171页第15页有向图 D = ( V, A ) 中，弧 a = ( u, v ) A，称弧 a 是始点 u 的关联弧，也称弧 a 是终点 v 的关联弧。 auv第14页/共171页第16页3. 多重边（弧） 无向图 G = ( V, E ) 中，边 e1=u, v、e2=u, v、ek=u, vE，即两个端点 u 和 v 之间的边多于一条，称这些边为多重边。 eiuve1ek第15页/共171页第17页有向图 D = ( V, A ) 中，弧 a1=(u, v)、

6、a2=(u, v)、ak=(u, v)A，即由始点 u 指向终点 v 的弧多于一条，称这些弧为多重弧。 aiuva1akuva1a2第16页/共171页第18页4. 环 无向图 G = ( V, E ) 中，边 e = u, u ，即边的两个端点相同，称该边为环。 ue第17页/共171页第19页有向图 D =( V, A ) 中，弧 a = (u, u) ，即弧的始点和终点相同，称该弧为环。 ue第18页/共171页第20页5. 简单图 无向图中，一个无多重边、无环的无向图，称为简单图。 有向图中，一个无多重弧、无环的有向图，称为简单图。 第19页/共171页第21页6. 多重图 无向图中，

7、一个有多重边，但无环的无向图，称为多重图。 有向图中，一个有多重弧，但无环的有向图，称为多重图。 第20页/共171页第22页简单图多重图例： 第21页/共171页第23页1. 顶点的次 在无向图中，以顶点 v 为端点的边的个数称为顶点 v 的次，记为 d(v)。 在有向图中，以顶点 v 为始点的弧数，称为顶点 v 的出次，记为 d + (v)。 在有向图中，以顶点 v 为终点的弧数，称为顶点 v 的入次，记为 d - (v)。 在有向图中，以顶点 v 的出次和入次之和，称为顶点 v 的次，记为 d(v)。 第22页/共171页第24页v1v2v3v4v5v7v6e1e2e4e5e6e3e9e

8、8e7d(v1)=2，d(v2)=2，d(v3)=4d(v4)=3，d(v5)=3，d(v6)=2d(v7)=2第23页/共171页第25页注：环的顶点的次数为 2 次。 d(v1)=4，d(v2)=2， d(v2)=3，d(v4)=1，d(v5)=0e2e1e3e4v1v2v3v4e5v5例：第24页/共171页第26页2. 悬挂点、悬挂边、悬挂弧 次数为 1 的顶点称为悬挂点。 如上例中的顶点 v4。无向图中，连接悬挂点的边称为悬挂边。 如上例中的边 e5。有向图中，连接悬挂点的弧称为悬挂弧。 第25页/共171页第27页d(v4)=1e2e1e3e4v1v2v3v4e5v5例：第26页/

9、共171页第28页3. 孤立点 次数为 0 的顶点称为孤立点。如上例中的顶点 v5 。 4. 奇点 次数为奇数的顶点称为奇点。如上例中的顶点 v3 和 v4 。 5. 偶点 次数为偶数的顶点称为偶点。如上例中的顶点 v1 和 v2 。 第27页/共171页第29页d(v5)=0e2e1e3e4v1v2v3v4e5v5例：d(v3)=3d(v4)=1d(v1)=4d(v2)=2第28页/共171页第30页6. 三个定理 定理 1 任何图中，顶点次数的总和等于边数（弧数）的 2 倍，即 qvdVv2)( 证明：计算各顶点的次数时，每条边都被它的端点各用了一次。 第29页/共171页第31页证明 9

10、个工厂之间，不可能每个工厂只与其他 3 个工厂有业务联系。（P278页习题8.1）证：如果9个工厂均是与其他3个工厂有业务联系，则顶点的次数总和为27，是奇数而不是偶数，同定理1矛盾。第30页/共171页第32页定理 2 任何图中，奇点的个数为偶数。 证明：设 V1 和 V2 分别是 G 中奇点和偶点的集合，由定理 1 可得 qvdvdvdVvVvVv2)()()(21 21)(2)(VvVvvdqvd第31页/共171页第33页 2)(Vvvd2q 和均为偶数 2)(Vvvd2q -为偶数 故也为偶数 1)(Vvvd又因为 d (v)（vV1）的值为奇数，所以 d(v)（vV1）的个数为偶数

11、。 第32页/共171页第34页证明 9个工厂之间，不可能只有4个工厂只与偶数个工厂有业务联系。 （P278页习题8.1）证：如果只有4个工厂与偶数个工厂有业务联系，则另外5个工厂与奇数个工厂有业务联系。这5个工厂均为奇点，与定理2矛盾。第33页/共171页第35页定理 3 有向图中，所有顶点的入次之和等于所有顶点的出次之和，即 VvVvvdvd)()(证明：计算各顶点的出次和入次时，每条弧都被它的端点各用了一次。 第34页/共171页第36页1. 链和路 在无向图 G = ( V, E )中，一个点、边交错序列 , ,., 1 1 2 2 1 1 kkkiiiiiiivevevev 如果满足

12、 ) 1,.,2 , 1(,1 ktvvetttiii1ivkiv，则称为连接和的一条链。 第35页/共171页第37页在有向图 D = ( V, A )中，一个点、弧交错序列 , ,., 1 1 2 2 1 1 kkkiiiiiiivavavav 如果满足 ) 1,.,2 , 1)(,(1 ktvvatttiii1ivkiv，则称为从到的一条路。 称为点kiiivvv,.,21为链的中间点。 第36页/共171页第38页v1v5v2v3v4a5a4a1a2a3例： (v1,a1,v2,a2,v3,a3,v4)不是一条路，因为弧a1(v1,v2)，a3(v3,v4)。 第37页/共171页第3

13、9页2. 初等链和初等路 kkkiiiiiiivevevev,.,112211 kiiivvv,.,21若链中，点均不相同，则称之为初等链。注：初等链中点无相同的，边也无相同的。第38页/共171页第40页注：初等路中点无相同的，弧也无相同的。 kkkiiiiiiivavavav,.,112211 kiiivvv,.,21中，点均不相同，则称之为初等路。若路第39页/共171页第41页v1v5v2v3v4a5a4a1a2a3例： (v1,a1,v2,a2,v3,a6,v1,a4,v5,a5,v4)不是一条初等路。 a6第40页/共171页第42页3. 简单链和简单路 kkkiiiiiiivev

14、evev,.,112211 若链中，边均不相同，则称之为简单链。注：简单链中边无相同的，但可有相同的点。121,., kiiieee第41页/共171页第43页注：简单路中弧无相同的，但可有相同的点。 kkkiiiiiiivavavav,.,112211 中，弧均不相同，则称之为简单路。若路121,., kiiiaaa第42页/共171页第44页v1v5v2v3v4a5a4a1a2a3例： (v1,a1,v2,a2,v3,a6,v1,a4,v5,a5,v4)不是一条初等路，但是一条简单路。 a6第43页/共171页第45页4. 圈和回路 kkkiiiiiiivevevev,.,112211 )

15、1,.,2 , 1(,1 ktvvetttiiikiivv 和和1在无向图 G = ( V, E ) 中，一个点、边交错序列，如果满足，且为同一个点，则称此链为圈。第44页/共171页第46页v1v5v2v3v4a5a4a1a2a3例： (v1,a1,v2,a2,v3,a6,v1)是一个圈。 a6第45页/共171页第47页 kkkiiiiiiivavavav,.,112211 ) 1,.,2 , 1)(,(1 ktvvatttiiikiivv和和1，如果满足，且为同一个点，则称此路为回路。 在有向图 D = ( V, A ) 中，一个点、弧交错序列第46页/共171页第48页v1v5v2v3

16、v4a5a4a1a2a3(v1,a1,v2,a2,v3,a6,v1)是一个回路。 a6例： 第47页/共171页第49页v1v5v2v3v4a5a4a1a2a3(v1,a1,v2,a2,v3,a6,v1)不是一个回路。 a6第48页/共171页第50页5. 初等圈和初等回路 1112211,.,iiiiiiivevevevkk 121,., kiiivvv若圈中，点都不相同，则称之为初等圈。 1112211,.,iiiiiiivavavavkk 121,., kiiivvv若回路中，点都不相同，则称之为初等回路。 第49页/共171页第51页初等圈：(v1, v2, v3, v4, v1)v1

17、v2v3v4v5v7v6e1e2e4e5e6e3e9e8e7第50页/共171页第52页(v4, v1, v2, v3, v5, v7, v6, v3 ,v4)不是一个初等圈。 v1v2v3v4v5v7v6e1e2e4e5e6e3e9e8e7第51页/共171页第53页6. 简单圈和简单回路 1112211,.,iiiiiiivevevevkk 121,., kiiieee121,., kiiiaaa若圈中，边均不相同，则称之为简单圈。 1112211,.,iiiiiiivavavavkk 若回路中，弧都不相同，则称之为简单回路。 第52页/共171页第54页(v4, v1, v2, v3,

18、v5, v7, v6, v3 ,v4)不是一个初等圈，但是一个简单圈。 v1v2v3v4v5v7v6e1e2e4e5e6e3e9e8e7第53页/共171页第55页7.连通图和不连通图 在无向图 G = (V, E) 中，若任意两个点之间，至少有一条链，则称 G 是连通图，否则称为不连通图。第54页/共171页第56页在有向图 D = (V, A) 中，若任意两个点之间，至少有一条路，则称 D 是连通图，否则称为不连通图。 第55页/共171页第57页8. 连通图分图 若 G 或 D 是不连通图，则它的每个连通部分，称为 G 的一个连通分图，简称分图。 第56页/共171页第58页v1v2v3

19、v4v5v7v6e1e2e4e5e6e3e9e8e7v8v9e10上图中是一个不连通图，但它有两个连通分图。 例： 第57页/共171页第59页9. 生成（支撑）子图 给一个无向图 G = ( V, E )，如图 ),(EVG ，使得 EEVV 、，则称 G 是 G的一个生成（支撑）子图。 第58页/共171页第60页给一个无向图 D = ( V, A )，如图 ),(AVD ，使得 AAVV 、，则称 D 是 D的一个生成（支撑）子图。 第59页/共171页第61页例： v1v3v5v4v2v1v5v4v3v2图G图G 图为图 G 的一个生成（支撑）子图 G 第60页/共171页第62页10

20、. G - v 图或 D - v 图 D - v：表示图 D 中去掉点 v 及 v 的关联弧后得到的一个图。 G - v：表示图 G 中去掉点 v 及 v 的关联边后得到的一个图。 第61页/共171页第63页v1v3v5v4v2v2v1v4v5图 G图 G - v3例： 第62页/共171页第64页11. 基础图 给一个有向图 D=(V, A) ，从 D 中去掉所有弧上的箭头（方向），从而得到一个无向图 G = (V , E)，称之为 D 的基础图，记为 G ( D ) 。 第63页/共171页第65页用矩阵表示图对研究图的性质及应用常常比较方便。图的矩阵表示方法主要有：权矩阵邻接矩阵第64

21、页/共171页第66页1. 权矩阵网络赋权图 G=(V，E)，其边 (vi，vj) 有权 wij ，构造矩阵 A=(aij)nn，其中 ，其其他他，0),(Evvwajiijij称矩阵 A=(aij)nn，为图 G 的权矩阵。第65页/共171页第67页 0650760844580320430974290A对角线上元素值为0v1v5v4v3v2742438569第66页/共171页第68页2. 邻接矩阵对于图 G=(V，E)，构造矩阵 A=(aij)mn，其中 ，其其他他，0),(1Evvajiij称矩阵 A=(aij)nn，为图 G 的邻接矩阵。第67页/共171页第69页v3v1v2v5v

22、6v4 010000101010100010010010000100000110A第68页/共171页第70页欧拉路：连通图 G 中，若存在一条路，经过 G 中的所有边，且每边仅经过一次，则称这条路为欧拉路。欧拉回路：连通图 G 中若存在一条回路，经过 G 中的所有边，且每边仅经过一次，则称这条回路为欧拉回路。欧拉图：具有欧拉回路的图称为欧拉图。第69页/共171页第71页欧拉路经过所有边的简单路欧拉回路经过所有边的简单回路第70页/共171页第72页定理1 无向连通图 G 是欧拉图，当且仅当 G 中无奇点。证明：（1）充分性：连通图G 为欧拉图 G 中无奇点。因为 G 为欧拉图，则必然存在一

23、条回路，经过 G 中所有的边，且只经过一次。对于 G 中的任一顶点 vi ，只要回路中出现一次，必关联两条边，即一条边进入这点，再沿另一边离开这点。所以点 vi 虽然可以在回路中重复出现，但次数必为偶数。第71页/共171页第73页（2）必要性：连通图G 中无奇点 G 为欧拉图。因为连通图 G 中全部都是偶点，则从任一顶点 v1 出发，经关联边 e1 进入 v2 ，由于 v2 也是偶点，则必然可由 v2 经另外一条不同的关联边 e2 进入另外一个顶点 v3，如此进行下去，每边仅取一次。由于连通图 G 中点数是有限的，所以这条路不能无休止地走下去，必然可以回到初始顶点 v1 ，从而得到一个回路

24、c1 。回路 c1 是否为欧拉回路只需验证 c1 是否包含连通图 G 中的所有边即可。第72页/共171页第74页 若回路 c1 经过 G 的所有边，则 c1 就是欧拉回路，必要性得以证明。 若回路 c1 只经过 G 中的一部分边，则 c1 尚不是欧拉回路。i） 从 G 中去掉 c1 后得到子图 G ，则 G 中每个顶点的次数仍为偶数。Ii）在 G 中，重复前面 c1 的方法，得到回路 c2 。第73页/共171页第75页iii）把 c1 与 c2 组合在一起，如果恰是图 G，则得到欧拉回路，否则重复上述步骤，得到回路 c3。iv）依次类推。由于图 G 中边数有限，最终可得一条经过图 G 所有

25、边的回路，即欧拉回路。第74页/共171页第76页该图无奇点，现在按照上述方法寻找欧拉回路。c1c2c3将c1、c2、c3组合起来，从而形成欧拉回路。为欧拉图第75页/共171页第77页欧拉图中欧拉回路的构造方法： 从图 G 中任一点 v1 出发，寻找一个初等回路 c1 。 从图 G 中去掉初等回路 c1 。 在剩余的图中再寻找初等回路 c2 。 从图 G 中去掉初等回路 c2 。按此方法进行下去，直到图中所有边都包含在这些初等回路中。把这些回路连接起来，从而得到即为欧拉回路。第76页/共171页第78页ACBDd(A)=3d(C)=5d(B)=3d(D)=3该连通图有4个奇点，不是欧拉图。判

26、断哥尼斯堡七桥难题第77页/共171页第79页下图能否一笔画出？可以一笔画出，因为该图为欧拉图。c1c2c3第78页/共171页第80页推论1 无向连通图 G 是欧拉图，当且仅当 G 的边集可划分为若干个初等回路。（由定理1的必要性证明过程可知。）推论2 无向连通图 G 中存在欧拉路，当且仅当 G 中恰有两个奇点。第79页/共171页第81页定理2 有向连通图 G 是欧拉图，当且仅当 G 中每个顶点的出次等于入次。推论 有向连通图 G 有欧拉路，当且仅当这个图中除去两个顶点外，其余每一个顶点的出次等于入次，且这两个顶点中，一个顶点的入次比出次多1，另一个顶点的入次比出次少1。第80页/共171

27、页第82页1962 年我国著名运筹数学家管梅谷教授提出中国邮路问题：一个邮递员，负责某一地区的信件投递。每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线，可以使所走的总路程最短？第81页/共171页第83页中国邮路问题的图论描述：给定一个连通图 G，每边有非负权 l(e)，要求一条回路过每边至少一次，且满足总权最小。第82页/共171页第84页分析：如果 G 中没有奇点，则是一个欧拉图，按欧拉回路走就是最短路；如果 G 中有奇点，要求连续走过每边至少一次，必然有些边不止走一次。第83页/共171页第85页树是图论中结构最简单但又十分重要的一种图。 1. 定义 连通且不含圈

28、的无向图称为无向树。在任一图 G 中，当点集 V 确定后，树是 G 中边数最少的连通图。 第84页/共171页第86页2. 定理 图 G = (V, E) 是一个树，p(G)2，则 G 中至少有两个悬挂点。 证 明 ： 在 G 中 找 出 边 数 最 多 的 一 条 初 等 链 ( v1,v2,vk )。第85页/共171页第87页现在来证明边数最多的初等链 ( v1 , v2 , , vk ) 的两个端点均为悬挂点。如果v1不是悬挂点，则至少存在边 v1, vm （vmv2）。 第86页/共171页第88页若点 vm 不在链(v1,v2,vk)中，那么(vm,v1,v2,vk)比(v1,v2

29、,vk)长，矛盾；若点 vm 在链(v1,v2,vk)中，那么(v1,v2, vm,v1)为圈，矛盾；从而可知 v1 为悬挂点。同理可证 vk 也为悬挂点。 第87页/共171页第89页3. 树的充要条件 图 G = (V, E) ，图 G 是一个树的充要条件为：（1）G 无圈，且 q (G) = p (G) -1（边数 = 点数 - 1）。（2）G 连通，且 q (G) = p (G) -1（边数 = 点数 - 1）。（3）G 中任意两点之间有唯一一条链相连。 （4）G 无圈，但每加一新边即得唯一一个圈。（5）G 连通，但每舍去一边就不连通。第88页/共171页第90页必要性：图 G 是一个

30、树 G 无圈，且 q(G) = p(G)-1 q(G) = p(G)-1用数学归纳法证明。p(G1)=1时，q(G1)=0，结论显然成立；p(G2)=2时，q(G1)=1，结论显然成立；假设 p (Gn) = n 时，q (Gn) = n-1，即结论成立。 （1）图 G 是一个树G 无圈，且 q (G) = p (G) -1。证明：第89页/共171页第91页下面来证明 p(Gn+1) = n+1 时，q(Gn+1)=n。Gn+1 是一个树，且 p(Gn+1) = n+12 由定理可知，Gn+1 中至少有两个悬挂点。设 v 是 Gn+1 的一个悬挂点，考虑图 Gn+1-v （图Gn+1中去掉点

31、 v 及 v 的关联边后得到的图）为一个顶点数量为 n 的树，则 第90页/共171页第92页又从而证明了 p(Gn+1) = n+1 时，q(Gn+1) = n，结论也成立。必要性得证。 q(Gn+1)= q(Gn+1-v)+1= n-1+1=np(Gn+1-v)=n，q(Gn+1-v) = p(Gn+1-v) 1 = n - 1第91页/共171页第93页充分性：图 G 无圈，且 q(G) = p(G) -1 图 G 是一个树 图 G 是连通的用反证法证明。设 G 是无圈的不连通图。G 可分为 s 个无圈的连通分图G1，G2，Gs（s2）G1，G2，Gs 均为无圈的连通图 第92页/共17

32、1页第94页G1，G2，Gs 均为树 由必要性可知：q (Gi) = p(Gi) -1（i=1, s, s2） 又G=G1，G2，Gs siiGpGp1)()( siiGqGq1)()(第93页/共171页第95页 sGpsGpGpGqGqsiisiisii )()(1)()()(111p(G)-2 p(G)-1 同已知条件 q(G) = p(G) -1矛盾，故假设错误。 充分性得证。 第94页/共171页第96页必要性：图 G 是一个树 G 连通，且 q(G)=p(G)-1 q (G) = p(G) - 1 略（同上，已证毕） 充分性：图 G 连通，且 q(G)= p(G)-1 图 G 是一

33、个树 图 G 中不含圈 （2）图 G 是一个树G 连通，且 q (G) = p (G) -1。第95页/共171页第97页 先来证明： 图 G 连通，且 q(G) = p(G)-1 图G中必有悬挂点用反证法证明。设 G 中无悬挂点。则 G 中所有点的次数都大于等于 2，即 d( vi )2，从而可得 第96页/共171页第98页（任何图中，顶点次数的总和等于边数的 2 倍，即 )(21)(1GpvdGqGpii )(2)()(1GqvdGpii ）第97页/共171页第99页从而可知：关系式 q(G) p(G) 和已知条件 q(G) = p(G)-1相互矛盾。 从而可知 G 中必有悬挂点。 第

34、98页/共171页第100页 用数学归纳法证明：图 G 连通，且 q(G) = p(G)-1 图 G 中不含圈 p(G1)=1，q(G1)=0时，G1显然不含圈，结论显然成立；p(G2)=2，q(G1)=1时，G2显然不含圈，结论显然成立；假设 p(Gn)=n，q(Gn)=n-1时，Gn中不含圈，即结论成立。 第99页/共171页第101页下面来证明 p(Gn+1)=n+1，q(Gn+1)=n 时，Gn+1中也不含圈。 Gn+1 中含有悬挂点 设 v 为Gn+1中的悬挂点，考虑图Gn+1-v（图Gn+1中去掉点 v 及 v 的关联边后得到的图）为一个顶点数量为 n 的连通图，且满足p(Gn+1

35、-v) = p(Gn+1) -1 = n， q(Gn+1-v)= q(Gn+1) -1 = n-1。 第100页/共171页第102页从而可知图 Gn+1-v 中不含圈Gn+1中也不含圈命题得证 第101页/共171页第103页（3） 图 G 是一个树G 中任意两点之间有唯一一条链相连必要性：图 G 是一个树 G 中任意两点之间有唯一一条链相连。因 G 是连通的：任两个点之间，至少有一条链；因 G 是无圈的：任两个点之间，只能有一条链，否则则形成了圈。 第102页/共171页第104页充分性：G 中任意两点之间有唯一一条链相连 图 G 是一个树G 中任意两点之间有唯一一条链：G 是连通的。再来

36、证明 G 是无圈的。反证法。设 G 中有圈，则这个圈上的两个顶点之间有两条链，与“G中任意两点之间有唯一一条链”相矛盾。故 G 中是无圈的。命题得证。 第103页/共171页第105页（4）图 G 是一个树G 无圈，但每加一新边即得唯一一个圈命 题 得 证。G 中任意两点之间有唯一一条链相连G 无圈，但每加一新边即得唯一一个圈第104页/共171页第106页图 G 是一个树G 连通，但每舍去一边就不连通（5）命 题 得 证。G 中任意两点之间有唯一一条链相连G 连通，但每舍去一边就不连通第105页/共171页第107页1. 定义 （1）生成树 ),(EVT 设图是图 G = ( V, E )

37、的生成子图是一个树，则称 T 是 G 的如果图),(EVT 一个生成树。 第106页/共171页第108页例： v1v3v5v4v2v1v5v4v3v2是上图的生成图，但不是生成树。第107页/共171页第109页v1v5v4v3v2是上图的生成图，而且是生成树。v1v3v5v2v4第108页/共171页第110页（2）树枝图 G 中，属于生成树的边称为树枝。（3）弦图 G 中，不属于生成树的边称为弦。第109页/共171页第111页v1v5v4v3v2是上图的生成图，而且是生成树。v1v3v5v2v4弦树枝第110页/共171页第112页（4）性质 p( T ) = p( G ) q ( T

38、 ) = p ( T ) -1 = p ( G ) -1（树枝数 = 点数 -1）； 弦数（G 中不属于树 T 的边数）= q (G ) q (T )= q( G ) - p( G )-1 = q(G) - p(G) + 1 （弦数= 边数 - 点数 + 1 ）第111页/共171页第113页v1v5v4v3v2v1v3v5v2v4弦树枝树枝数= 点数 -1= 5 1 = 4弦数= 边数 - 点数 + 1= 7 - 5 + 1 = 3 第112页/共171页第114页2. 定理 图 G 有生成树的充分必要条件是图 G 是连通的。 证明：必要性：图 G 有生成树 图 G 是连通的图 G 有生成树

39、 T，生成树 T 必是连通，从而图 G 也必是连通的。 第113页/共171页第115页充分性：图 G 是连通的 图 G 有生成树如果图 G 是连通的、且无圈，则图 G 本身就是一个树，从而图 G 是它自身的一个生成树。如果图 G 是连通的、且含有圈（破圈法）：（1）则任取一个圈，从圈中任意去掉一条边，得到图 G 的一个生成子图 G1，如果 G1不含圈，那么 G1 就是 G 的一个生成树； 第114页/共171页第116页（2）如果 G1 仍含圈，那么从 G1 中任取一个圈，从圈中任意去掉一条边，得到图 G1 的一个生成子图 G2，如果 G2不含圈，那么 G2 就是 G的一个生成树；（3）如此

40、重复，最终可以得到 G 的一个生成子图 Gk，使 Gk 中不含圈，于是 Gk 是 G 的一个生成树。 第115页/共171页第117页3. 寻找生成树的方法 （1）破圈法 从图 G 中任取一个圈，从圈中去掉一边，对余下的图重复这个步骤，直到不含圈为止，即得到一个生成树。“破圈法”中去掉的边数 = q ( G ) p ( G ) + 1 第116页/共171页第118页（2）避圈法思路：在已给出的图 G 中，每步选出一条边，使它与已选边不构成圈，直到选购 p ( G ) - 1 条边为止。下面介绍两种方法。 第117页/共171页第119页 深探法 步骤 1 在点集 V 中任取一点 v0，给 v

41、0 标号 0 ； 步骤 2 若某点 vi 已标号 i ，则检查以 vi 为端点的所有关联边（vi, v），寻找这些关联边中另一端点 v 未标号的关联边。 第118页/共171页第120页步骤3 若有未标号的，则任选一个未标号的端点 v ，给以标号 i +1，令其为 vi+1，检查以 vi+1 为端点的所有关联边（vi+1, v），寻找这些关联边中另一端点 v 未标号的关联边。第119页/共171页第121页步骤4 若无未标号的，则退到标号为 i -1的点 vi-1 ，检查以 vi-1 为端点的所有关联边（vi-1 , v），寻找这些关联边中另一端点 v 未标号的关联边。步骤5 重复步骤2、3和

42、4，直到全部点得到标号为止。 第120页/共171页第122页例： 012345678910111213第121页/共171页第123页 广探法步骤1 在点集 V 中任取一点 v0 ，给 v0 标号 0 ；步骤2 令所有标号为 i 的点集为Vi= vi ，检查以 vi 为端点的所有关联边（vi , v），寻找这些关联边中另一端点 v 未标号的关联边。第122页/共171页第124页步骤3 若有未标号的，则对所有未标号的端点 v ，给以标号 i +1，令其为 vi+1 ，检查以 vi+1 为端点的所有关联边（vi , v），寻找这些关联边中另一端点 v 未标号的关联边。步骤4 重复步骤 2 和

43、3 ，直到全部点得到标号为止。 第123页/共171页第125页例： 01232133233444第124页/共171页第126页1. 权和赋权图的基本概念 （1）定义给图 G = (V，E)，对 G 中的每一条边 vi，vj ，相应地给一个数 wij，称 wij 为边 vi，vj 上的权，称这样的图 G 为赋权图。第125页/共171页第127页（2）权的含义权是与边有关的数量指标，根据实际问题的需要，可以赋予不同的含义，如距离、时间、费用等。 第126页/共171页第128页（3）赋权图的意义赋权图不仅指出了各顶点之间的相邻关系，而且也表示出了各点之间的数量关系，所以赋权图被广泛地应用于解

44、决工程技术及科学生产管理等领域的最优化问题。赋权图在图论及其应用方面有着重要的地位。最小生成树问题就是赋权图上的最优化问题之一。 第127页/共171页第129页2. 最小生成树的基本概念 EVT ,E TvvijjiwTw,)(（1）生成树的权连通图 G = (V，E)，每条边 e =vi，vj上有一个非负权 w(e) = wij（wij0）。如果是 G = (V，E) 的一个生成树，称的权之和为生成树 T 的权，记为 w ( T )，即。 中所有边第128页/共171页第130页（2）最小生成树如果生成树 T * 的权 w (T *) 是 G 的所有生成树的权中最小者，则称 T * 是 G

45、 的最小生成树，简称最小树。即 w(T *) =)(minTwT第129页/共171页第131页（3）最小生成树的应用许多网络问题都可以归结为最小生成树问题。如设计长度最小的公路网，把若干城市联系起来；设计用料最省的电话线网，把有关单位联系起来。 第130页/共171页第132页3. 寻找最小生成树的算法 （1）避圈法，Kruskal算法 思路：开始选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。如果有两条或两条以上的边都是权最小的边，则从中任选一条。 第131页/共171页第133页步骤1 对赋权图 G = (V，E) 中的所有边按照权值从小到

46、大的顺序排序，记为 e1,e2,en ；步骤2 令E0=；步骤3 从 E E0 =e1,en 中选取权最小的边 e1，如果 e1 同 E0 中的边不构成圈，令 E1 = e1 ；第132页/共171页第134页步骤4 从 E E1=e2,en 中选取权最小的边e2，如果 e2 同 E1 中的边不构成圈，令 E2 = e1,e2；步骤5 从 E Ei-1 =ei,en 中选取权最小的边ei，如果 ei 同 Ei-1 中的边不构成圈，令 Ei = e1,e2, ei； 第133页/共171页第135页步骤6 从 E Ei=ei+1,en中选取权最小的边ei+1， 如 果 ei + 1 同 Ei 中

47、 的 边 不 构 成 圈 ， 令Ei+1=e1,e2, ei, ei+1 ；步骤7 重复上述步骤，直到集合 Ei 中的边数等于p(G) -1为止。 第134页/共171页第136页例v165524v3v5v6v4v24173某工厂内联结六个车间的道路网如上图所示。已知每条道路的长，要求道路架设联结六个车间的电话线网，使电话线的总长最小。第135页/共171页第137页解：（1）把边按权值从小到大的顺序排列： v2,v3=1，v2,v4=2，v4,v5=3， v5,v6=4，v4,v6=4，v3,v5=5， v1,v2=5，v1,v3=6，v2,v5=7， （2）E1=v2,v3； E2=v2,

48、v3，v2,v4； E3=v2,v3，v2,v4，v4,v5；第136页/共171页第138页E4=v2,v3，v2,v4，v4,v5，v5,v6或E4=v2,v3，v2,v4，v4,v5，v4,v6；因为v3,v5同E4构成圈，所以只能选v1,v2，从而可得：E5=v2,v3，v2,v4，v4,v5，v5,v6，v1,v2或E5=v2,v3，v2,v4，v4,v5，v4,v6，v1,v2。因为边数等于5，从而停止寻找。 第137页/共171页第139页v165524v3v5v6v4v24173不能选，构成圈不能选，构成圈第138页/共171页第140页v165524v3v5v6v4v2417

49、3不能选，构成圈不能选，构成圈第139页/共171页第141页v1524v3v5v6v4v213v152v3v5v6v4v2413第140页/共171页第142页（2）破圈法 定理：图 G 的生成树 T 为最小树，当且仅当对任一弦 e 来说，e 是 T + e 中与之对应的圈中的最大权边。第141页/共171页第143页步骤1 从图 G 中任找一个树 T1；步骤2 加上一条弦e1，T1+e1中立即生成一个圈，去掉该圈中最大权的边，得到新树 T2，以 T2 替代T1；步骤3 重复步骤2，检查剩余的弦，直到全部弦（共有 q(G) - p(G) + 1 条弦）检查完毕为止。 第142页/共171页第

50、144页例v165524v3v5v6v4v24173某工厂内联结六个车间的道路网如上图所示。已知每条道路的长，要求道路架设联结六个车间的电话线网，使电话线的总长最小。第143页/共171页第145页v165524v3v5v6v4v24173解：（1）利用广探法寻找一个树： （2）弦数= q(G)-p(G)+1=9-6+1=4； 弦= v2,v3, v2,v5, v4,v5, v4,v6 第144页/共171页第146页（3）加弦v2,v3，得圈（v2,v3,v1），去掉最大权边v1,v3；（4）加弦v2,v5，得圈（v2,v5,v3），去掉最大权边v2,v5；（5）加弦v4,v5，得圈（v4,

51、v5,v3,v2），去掉最大权边v3,v5；（6）加弦v4,v6，得圈（v4,v6,v5），去掉最大权边v4,v6或v5,v6。（7）所有弦检查完毕，从而得出最小树。 第145页/共171页第147页v165524v3v5v6v4v24173第146页/共171页第148页v165524v3v5v6v4v24173第147页/共171页第149页例 已知六大城市A、B、C、D、E、F之间的距离如下表所示，求联结六大城市的道路网，使道路网的总长度最短。 城市城市ABCDEFA1351776850B1360706759C516057362D7770572055E6867362034F5059255

52、34第148页/共171页第150页解：利用避圈法，将各城市之间的距离按照从近到远的顺序排列，依次选择，直到边数的 5 条停止。 135023420BCDEFA36边数已到达 5，停止。第149页/共171页第151页1. 定义 （1）有向树若有一个有向图在不考虑边的方向时是一个树，则称这个有向图为有向树。（2）根树（外向树）有向树 T ，恰有一个节点入次为 0 ，其余各点入次均为 1 ，则称 T 为根树，又称外向树。第150页/共171页第152页（3）根 根树中，入次为 0 的顶点称为根。（4）叶 根树中，出次为 0 的顶点称为叶。（5）分枝点 根树中，除了根和叶之外的其他顶点称为分枝点。（6）层次根树中，设所有弧的权值均为 1 ，则由根到某一顶点 vi 的路的长度，称为 vi 点的层次。 第151页/共171页第153页例： v1v2v3v4v5v6v7v8v9v10v11v12第152页/共171页第154页v1为根；v2、v3、v4、v8为分枝点；v5、v6、v7、v9、v10、v11、v12为叶；v2、v3、v4的层次为1；v12的层次为3。 第153页/共171页第155页（7）m 叉树根树中，若每个顶点