《图论的介绍ppt课件.ppt》由会员分享，可在线阅读，更多相关《图论的介绍ppt课件.ppt（108页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图论的介绍ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望哥尼斯堡七桥问題(Bridges of Koenigsberg)能不能走过每一个桥能不能走过每一个桥刚好一次并且回到原來的地方？刚好一次并且回到原來的地方？欧拉路径解決哥尼斯保七桥问題原來是一笔画问题啊！数学家欧拉(Euler,1707-1783)于1736年严格的证明了上述哥尼斯堡七桥问题无解，并且由此开创了图论的典型思维方式及论证方式实际生活中的图论Graph Model电路模拟电路模拟例：例
2、：Pspice、Cadence、ADS.PspiceCadence交通网络航空网络航空网络!捷運路線图！捷運路線图！网络架构图网络架构图计算机网络有向图有有单行道的街道！单行道的街道！行程表！行程表！Social NetworkHigh School Datingcorporate e-mailReference:Bearman,Moody and Stovel,2004image by Mark NewmanReference:Adamic and Adar,2004Protein interaction networkReference:Jeong et al,Nature Review|
3、GeneticsPower transmission grid of Western USThe InternetThe Internet as mapped by The Opte Projecthttp:/www.opte.orgMore ApplicationsnHypertextsq网页包含到其他网页的超链接。整个网页包含到其他网页的超链接。整个Web是一个图是一个图.搜搜索引擎需要图处理算法。索引擎需要图处理算法。nMatchingq职位招聘，如何有效将职位与应聘者匹配？职位招聘，如何有效将职位与应聘者匹配？nSchedulesq工程项目的任务安排，如何满足限制条件，并在最短时工程项
4、目的任务安排，如何满足限制条件，并在最短时间内完成？间内完成？nProgram structureq大型软件系统，函数（模块）之间调用关系。编译器分大型软件系统，函数（模块）之间调用关系。编译器分析调用关系图确定如何最好分配资源才能使程序更有效析调用关系图确定如何最好分配资源才能使程序更有效率。率。Graph ApplicationsGraph Problems and Algorithms哈密頓（Hamilton）周遊世界问題哈密頓路径至今尚无有效方法來解決！正十二面体有二十个顶点表示世界上20个城市各经每个城市一次最后返回原地投影至平面最短路径问題最短路径问題(Shortest Path
5、Problem)最快航線最快航線 最快的最快的routing最短路径算法最短路径算法Dijkstra算法算法n可以求出從某一点到图上其他任一点的最短路径可以求出從某一点到图上其他任一点的最短路径走迷宫与深度优先搜索走迷宫与深度优先搜索(Depth-First Search)老鼠走迷宮老鼠走迷宮深度优先搜索深度优先搜索一直往前走一直往前走碰壁就回碰壁就回头換条路找头換条路找沿途要记录下走过的路线沿途要记录下走过的路线Some graph-processing problemsnPath.Is there a path between s to t?nShortest path.What is t
6、he shortest path between s and t?nLongest path.What is the longest simple path between s and t?nCycle.Is there a cycle in the graph?nEuler tour.Is there a cycle that uses each edge exactly once?nHamilton tour.Is there a cycle that uses each vertex exactly once?nConnectivity.Is there a way to connect
7、 all of the vertices?nMST.What is the best way to connect all of the vertices?nBiconnectivity.Is there a vertex whose removal disconnects the graph?nPlanarity.Can you draw the graph in the plane with no crossing edges?First challenge:Which of these problems is easy?difficult?intractable?图论图论的术语的术语什么
8、是图？什么是图？一堆顶点和边的组合！一堆顶点和边的组合！Set of vertices connected pairwise by edges.例一例一 例二例二 图论的术语顶点(Vertex)边(Edge)一个图G=(V,E)V:顶点的集合E:边的集合例：如右图V=a,b,c,d,eE=(a,b),(a,c),(a,d),(b,e),(c,d),(c,e),(d,e)再來一些术语连通图(connected graph)子图(subgraph)树(tree)沒有回路的连通图森林(forest)一堆树的集合树的实例 行政组织图有向图(Digraph)有向图(Digraph)有向且无简单回路的图(
9、directed acyclic graph)加权图(Weighted Graph)生成树(Spanning Tree)生成树包括图中所有的顶点，并且是一棵树可运用生成树的实例Graph Terminology一些特殊的图完全图 Complete graphsn任意两点之间都有一条边与其相连的图称为完全图，以Kn 來表示，n为顶点数二分图（偶图）Bipartite graphsnA graph that can be decomposed into two partite sets but not fewer is bipartitenIt is a complete bipartite if
10、 its vertices can be divided into two non-empty groups,A and B.Each vertex in A is connected to B,and vice-versa Complete bipartite graph K2,3The graph is bipartite平面图 Planar graphsnA planar graph is a graph that can be embedded in a plane so that no edges intersectPlanar:=NOT Planar:平面图实例n8个顶点(V=8)
11、n12条边(E=12)n6个面 (F=6)n8-12+6=2更多平面图实例 树 Trees n树(tree):连通无简单回路无向图q若有n个顶点，則有n-1条边q任两点之间仅有一条路径n生成树(spanning tree):包括图中所有的顶点，并且是一棵树A connected graph GSpanning trees of Gtree图术语回顾点：点：研究对象（陆地、路口、国家、球队）；点间连线：点间连线：对象之间的特定关系（陆地间有桥、路口 之间道路、两国边界、两球队比赛及结果)。对称关系：对称关系：桥、道路、边界；用不带箭头的连线表示，称为边。用不带箭头的连线表示，称为边。非对称关系：
12、非对称关系：甲队胜乙队，用带箭头的连线表示，称为弧。图：图：点及边（或弧）组成。例：例：有甲、乙、丙、丁、戊五个球队，各队之间比赛有甲、乙、丙、丁、戊五个球队，各队之间比赛 情况如表：情况如表：点：球队；点：球队；连线：两个球队之间比赛过，如甲胜乙，用连线：两个球队之间比赛过，如甲胜乙，用 v1 v2表示。表示。v1v2v3v4v5 图的定义图的定义定义定义1：一个图，是由非空集合：一个图，是由非空集合V(G)=vi 和和V(G)中中 元素的有序对（或无序对）的集合元素的有序对（或无序对）的集合E(G)=ek 所组成的二元组（所组成的二元组（V(G)，E(G)）所构成。）所构成。记为记为 G=
13、（V(G)，E(G)）简记简记 G=（V，E）其中其中 V=vi 称为点集，称为点集，vi为点为点。E=ek称为边集，称为边集，ek为边（或弧）。为边（或弧）。当当V，E为有限集时，称为有限集时，称G为有限图。为有限图。否则，称否则，称G为无限图。为无限图。无向图：由点及边构成无向图：由点及边构成，边，边vi，vj有向图：由点及弧构成，弧（有向图：由点及弧构成，弧（vi，vj）图图G中点集中点集V的顶点个数，记为的顶点个数，记为p(G)；边数记为边数记为q(G),简记简记 p，q。1.简单图与多重图简单图与多重图某条边两个端点相同，称这条边为环。某条边两个端点相同，称这条边为环。若两点之间有多
14、于一条的边，称这些边为多重边。若两点之间有多于一条的边，称这些边为多重边。无环、无多重边的无环、无多重边的图称为简单图。图称为简单图。多重图：无环、但多重图：无环、但允许有多重边。允许有多重边。v1e1e2e3v2v3e5e4v4二、图论中常用术语二、图论中常用术语2.相邻与关联相邻与关联 若边若边e=u，vE，称，称u，v是是e的端点，也称的端点，也称u，v是是相邻的。称相邻的。称e是点是点u（及点（及点v）的关联边。）的关联边。若两条边有一个公共的端点，则称这两条边相邻接。若两条边有一个公共的端点，则称这两条边相邻接。vivjevi，vj相邻相邻 e 与与vi，vj关联关联vie1vjvk
15、e2 点与边关联点与边关联点与点点与点相邻相邻边与边相邻接边与边相邻接定理定理1 图图G=（V，E）中，所有点的次之和为边数）中，所有点的次之和为边数的两倍，的两倍，即即 3.奇点与偶点奇点与偶点次为奇数的点称为奇点，否则称为偶点。次为奇数的点称为奇点，否则称为偶点。定理定理2 任一图中奇点的个数为偶数。任一图中奇点的个数为偶数。证明：证明：设设v0和和v e分别是分别是G中的奇点和偶点的集合，中的奇点和偶点的集合，由定理由定理1，有，有因因 是偶数，是偶数，也是偶数，故也是偶数，故必为偶数。即在一个图中奇点的个数必为偶数。必为偶数。即在一个图中奇点的个数必为偶数。4.节点度与悬挂点、孤立点节
16、点度与悬挂点、孤立点图图G中以点中以点v为端点的边的数目，称为为端点的边的数目，称为v在在G中的度，中的度，记为记为d（v）。）。d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1度为度为1 的点为的点为悬挂点悬挂点，悬挂点的关联边称为，悬挂点的关联边称为悬挂边悬挂边，度为零的点称为度为零的点称为孤立点孤立点。v1e1e2e3v2v3e5e4v45.链与圈链与圈 给定一个图给定一个图G=（V，E），），G中的一个中的一个点、边交错点、边交错序列序列（vi1，ei1，vi2，ei2，vik-1，eik-1，vik），如果满），如果满足足eit=vit，vit+1（t=1，2，k-1）
17、，则称为一条联接），则称为一条联接vi1和和vik的的链链，记为，记为=（vi1，vi2，vik）。）。链（链（vi1，vi2，vik）中，若）中，若vi1=vik，称之为一，称之为一个个圈圈，记为，记为C=（vi1，vi2，vik-1，vi1）。初等链：链中点都不同。初等链：链中点都不同。简单链：链中边都不同。简单链：链中边都不同。（边能否相同？）边能否相同？）（点能否相同？）点能否相同？）v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9简单链简单链：1=（v2，v1，v3，v6，v4，v3，v5）初等链初等链：2=（v2，v1，v3，v5）简单圈简单圈：C1=（v1，v
18、2，v4，v3，v5，v6，v3，v1）初等圈：初等圈：C2=（v1，v2，v4，v6，v5，v3，v1）有向图中，不考虑弧的方向，有类似链（圈）的定义。有向图中，不考虑弧的方向，有类似链（圈）的定义。当链（圈）上弧的方向一致时，称为路（回路）。当链（圈）上弧的方向一致时，称为路（回路）。3.连通图连通图 给定图G=（V，E），任何两点间至少有一条链，则称G是连通图，否则为不连通图。若G是不连通的，它的每个连通部分称为G的连通分图。一些特殊图类一些特殊图类 1.平凡图平凡图 节点数n=1,边数m=0的图。2.零图零图 边数m=0的图。5.完备图完备图 无向图的完备图：任何两点之间有一条边；有向
19、图的完备图：任何两点u与v之间有两条有向边（u，v）及（v，u）。基本图：把有向图的每条边除去方向得到的无向图。若V(G)=X Y,X Y=，X、Y中的任两顶点不相邻，则G称为二分图，记为（S,X,Y）。4.4.树树 无圈连通图。6.6.二分图二分图9.网络网络 若对图G=（V，E）中每条边vi，vj赋予一个数wij，则称wij为边vi，vj的权，并称图G为网络（或赋权图）。网络：无向网络、有向网络。7.完全二分图完全二分图 若V(G)=(S,X,Y),如果任意X、Y，都有，E，则称G是完全的二分图。8.正则图正则图 如果G中每个点的次数都相同，则G叫做正则图。1.子图与支撑子图子图与支撑子图
20、定义定义2 给定图给定图G=（V，E），若图），若图G1=（V1，E1），其），其 中中V1 V，E1=uv|uvE，u，v v1，则称，则称G1是是G的子图。的子图。定义定义3 给定图给定图G=（V，E），若图），若图G1=（V，E1），其），其 中中E1 E，则称，则称G1是是G的一个支撑子图。的一个支撑子图。点全部保留点全部保留（a）（b）子图子图（c）支撑子图支撑子图四四 、图的运算、图的运算 2.2.图的收缩运算图的收缩运算 设图设图G=(V,E)，V1 V,在在G中收缩中收缩V1是指在图是指在图G中，中，在在V1中的点重为一个点，中的点重为一个点，G与与V1中的点相关联的边变中的点
21、相关联的边变为与这个新点相关联的边，称这样的图为关于为与这个新点相关联的边，称这样的图为关于V1收缩收缩。3.割集割集 给定图给定图G=（V，E），点的子集），点的子集S V，T V，定，定义义G中中边的集合边的集合S，TG=uv|u s，v T为一个割集。为一个割集。若若X=v1若若X V是是V的真子集，的真子集，常记为常记为v6v2v3v4v5v1v1v2v3v4v5v6若若X=v1，v2，4.图的同构图的同构定义定义4 设图设图G=（V，E）与）与G1=（V1，E1），若它们），若它们的点之间存在一一对应，并且保持同样的相邻关系，的点之间存在一一对应，并且保持同样的相邻关系，则称则称G与
22、与G1同构。记为同构。记为G G1。v1v2v3v4abcdv1v2v3v4abcd?(a)(b)图图(a)和和(b)就为同构就为同构五、图的矩阵表示五、图的矩阵表示 图的矩阵表示方法有：邻接矩阵、关联矩阵、可图的矩阵表示方法有：邻接矩阵、关联矩阵、可达矩阵、权矩阵等。达矩阵、权矩阵等。1.1.邻接矩阵邻接矩阵 邻接矩阵用于描述两个顶点之间是否有边（弧）相连。邻接矩阵用于描述两个顶点之间是否有边（弧）相连。对于有n个顶点的无向图G=(V,E)，定义邻接矩阵(B=bij)nn。其中，对于有几个顶点的有向图G=(V,A)，定义邻接矩阵(B=bij)nn。其中，例题例题1 已知无向图所示，求其邻接矩
23、阵。已知无向图所示，求其邻接矩阵。v5v3v1v2v4v6则 显然，无向图的邻接矩阵是关于对角线的对称矩阵。例例 2 已知：图所示，求其邻接矩阵。已知：图所示，求其邻接矩阵。v2v5v3v1v4v6则：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 0 1 1 v5 0 0 1 0 0 1 v6 0 0 0 0 0 0其邻接矩阵为：其邻接矩阵为：v4v5v2v1v3当当G为为无向图无向图时，时，邻接矩阵邻接矩阵为为对称对称矩阵。矩阵。在有向图中可达矩阵用于描述两点之间是否有路相连,即R=(rij)n
24、n ,其中，2.2.可达矩阵可达矩阵 例题例题3 求例题求例题2的可达矩阵的可达矩阵则 v1 v2 v3 v4 v5 v6 v1 1 1 1 1 1 1 v2 0 1 1 1 1 1 v3 0 0 1 1 1 1 v4 0 0 0 1 1 1 v5 0 0 0 0 1 1 v6 0 0 0 0 0 13.关联矩阵关联矩阵有向图的关联矩阵也称顶点边关联矩阵。设有向图 G=(V,A)，其中rij=V=v1,v2,v3vn，则关联矩阵可定义为 M=(mij)nm其中：例题例题4 4 求下图的关联矩阵求下图的关联矩阵v4v2v1v3a4a3a1a2a6a5则其关联矩阵为：a1 a2 a3 a4 a5
25、a6 v1 0 1 -1 0 0-1 v2 1 0 1 1 0 0 v3 -1-1 0 0 1 0 v4 0 0 0 -1 -1 1 权矩阵是最流行的一种网络矩阵表示法。对于有n个顶点的无向网络G=(V,E,W),边 vi,vj的权为wij，则权矩阵D=(dij)nn，其中：4.权矩阵权矩阵 对于有n个顶点的有向网络G=(V,A,W),边 vi,vj的权为wij，则权矩阵D=(dij)nn，其中：例题例题5.如图所示，弧上的数字代表数，如图所示，弧上的数字代表数，D=(dij)5 5。0 35 4319 0 85 18 43 0 11 0 16 77 0v4v5v2v1v3234567894其
26、权矩阵为：其权矩阵为：基基 本本 概概 念念最最 短短 路路 问问 题题 及及 其其 算算 法法固固 定定 起起 点点 的的 最最 短短 路路最短路是一条路径，且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此,可采用树生长的过程来求指定顶点到其余顶点的最短路算法步骤：算法步骤：u1u2u3u4u5u6u7u8一、一、可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题二、二、选选 址址 问问 题题1、中心问题中心问题2、重心问题重心问题可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题 选址问题选
27、址问题-中心问题中心问题S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处。选址问题选址问题-重心问题重心问题还有哪些选址问题？n消防队n汽车急救中心n警车配置和巡逻问题（2009研究生数学建模竞赛试题）警车配置和巡逻问题n110警车在街道上巡弋，既能够对违法犯罪分子起到震慑作用，降低犯罪率，又能够增加市民的安全感，同时也加快了接处警（接受报警并赶往现场处理事件）时间，提高了反应时效，为社会和谐提供了有力的保障。n该问题考虑到某城市内一区域，并假定所有事发现场均在下图的道路上。下图红点部
28、位为重点部位，该区域内三个重点部位的坐标分别为：（5112，4806），（9126，4266），（7434，1332），蓝色部分为水域，相邻两个交叉路口之间的道路近似认为是直线。警车配置和巡逻问题警车配置和巡逻问题n现在该城市拟增加一批配备有GPS卫星定位系统及先进通讯设备的110警车。假设110警车的平均巡逻速度为20km/h，接警后的平均行驶速度为40km/h。警车配置及巡逻方案则需要尽量满足以下要求：nD1.警车在接警后三分钟内赶到现场的比例不低于90；而赶到重点部位的时间必须在两分钟之内。nD2.使巡逻效果更显著。nD3.警车巡逻规律应有一定的隐蔽性。警车配置和巡逻问题n具体问题如下：
29、n一.若要求满足D1,该区最少需要配置多少辆警车巡逻？n二.请给出评价巡逻效果显著程度的有关指标。n三.请给出满足D1且尽量满足D2条件的警车巡逻方案及其评价指标值。n四.在第三问的基础上，再考虑D3条件，给出你们的警车巡逻方案及其评价指n标值。n五.如果该区域仅配置10辆警车，应如何制定巡逻方案，使D1、D2尽量得到n满足？n六.若警车接警后的平均行驶速度提高到50km/h，回答问题三。n七.你们认为还有哪些因素、哪些情况需要考虑？给出你们相应的解决方案。警车配置和巡逻问题新问题n单约束选路问题？n多约束选路问题？n多目标选路问题？n多路径选路问题？n区间最优路径？n匹配与最大匹配匹配与最大
30、匹配n定义定义:(:(二部二部)图图 G=G=X,E,YX,E,Y 的边集的边集E E的子集的子集M M称为称为G G的的一个一个匹配匹配,如果如果M M的任二边都没有公共端点的任二边都没有公共端点;G;G中边数中边数最多的匹配称为最多的匹配称为最大匹配最大匹配(不唯一不唯一););含有含有G G的每一点的的每一点的匹配称为匹配称为完美匹配完美匹配(必为最大匹配仍不唯一必为最大匹配仍不唯一).).n下面是最大下面是最大,完美匹配的例子完美匹配的例子(用粗线表示用粗线表示):):工作分配问题工作分配问题n问题问题 某教研室有某教研室有4 4位教师位教师:A,B,C,D.A:A,B,C,D.A能教
31、课程能教课程5;B5;B能能教教1,2;C1,2;C能教能教1,4;D1,4;D能教课程能教课程3.3.能否能否适当分配他们的适当分配他们的任务任务,使使4 4位教师担任位教师担任4 4门不同课并且不发生安排教师门不同课并且不发生安排教师教他不能教的课的情况教他不能教的课的情况?n此问题可归结为二部图的数学模型此问题可归结为二部图的数学模型:G=G=A,B,C,D,E,1,2,3,4,5A,B,C,D,E,1,2,3,4,5,(X,y),(X,y)E,E,如果如果X X能能教教y.y.一个一个满足要求的工作分配满足要求的工作分配正是一个含有正是一个含有4 4条边的条边的一个一个最大匹配最大匹配
32、.ABCD12345求图求图G G最大匹配最大匹配的方法的方法首先首先 任取一个匹配任取一个匹配(含一边也可含一边也可)M)M作为起点作为起点.接着接着按按下列方法逐步调整当前匹配下列方法逐步调整当前匹配(每一步使它调整为边每一步使它调整为边数多数多1 1的匹配的匹配)最后达到一个最大匹配最后达到一个最大匹配:步骤步骤 在在X X中选定一个不属于中选定一个不属于M M的点的点x xi i标记标记(*).(*).步骤步骤 在在X X的新标记的点中选一点的新标记的点中选一点,如如x xi i,用用(x(xi i)标记通过不属于标记通过不属于M M的边与的边与x xi i邻接并且尚未标记的邻接并且尚
33、未标记的点点(如如y yi i););在在Y Y的新标记的点中选一点的新标记的点中选一点(如如y yi i),),用用(y(yi i)标记通过标记通过M M的边与的边与y yi i邻接并且尚未标记的点邻接并且尚未标记的点;照此继续照此继续,直到发现标记到直到发现标记到Y Y的一个点的一个点,该点不与该点不与X X中任一边相关联或标记不到任何这样的点为止中任一边相关联或标记不到任何这样的点为止.出现前一情况出现前一情况,便找到一条关于便找到一条关于M M的的交替链交替链(定义定义8.4-48.4-4););利用它利用它可调整可调整M M到一个比到一个比M M多一边的匹配多一边的匹配;出现后一情况
34、便表示出现后一情况便表示M M已为最大匹配已为最大匹配.求最大匹配求最大匹配举例举例解解:取一个初始匹配取一个初始匹配M=Bb,Cc,Dd.M=Bb,Cc,Dd.用标记用标记法从点法从点A A开始求得一条交替链开始求得一条交替链:=(AcCe)(=(AcCe)(左图左图).).用用 调整匹配调整匹配M:M:将将 中属于中属于M M的边删去并将其中不属于的边删去并将其中不属于M M的其它边添加到的其它边添加到M M中得到比中得到比M M多一边的新匹配多一边的新匹配M(M(如如右图右图示示).).因对因对MM用标记法只能从用标记法只能从E E或或F F开始开始,但都但都不能求出不能求出MM的任何交
35、替链的任何交替链,故判定故判定MM是一个最大匹配是一个最大匹配.A(c)BCD(d)abc(D)d(E)eE(*)F(*)fA(*)BC(c)Dab c(A)de(C)EFfM树树的概念的概念n树树是应用中特别重要的特殊图是应用中特别重要的特殊图,分无向树和有向分无向树和有向树两种树两种.n定义定义 无回路的无向连通图称为无回路的无向连通图称为无向树无向树.也可以也可以说说,无基本回路的无向连通图称为无向树无基本回路的无向连通图称为无向树,因为因为:无回路等价于无基本回路无回路等价于无基本回路.n连通分支全为无向树的图连通分支全为无向树的图,即无回路的无向图即无回路的无向图,称为称为森林森林.
36、n树的树的1 1度点称为度点称为树叶树叶,不是树叶的点称为不是树叶的点称为分枝点分枝点.n例例 图图8.6-18.6-1.(n,m)(n,m)无向无向线线图图G G是是树的树的5 5个等价条件个等价条件G G是树是树连通无回路连通无回路.G G无回路且无回路且m=n-1.m=n-1.G G连通且连通且m=n-1.m=n-1.G G无回路且加一边得唯无回路且加一边得唯一回路一回路.G G连通且少一边不连通连通且少一边不连通.G G任二点间有唯一任二点间有唯一(基本基本)路径路径.证证 :2:2结点树的边数为结点树的边数为1=2-1.1=2-1.假设假设k k结点树的边结点树的边数为数为k-1.k
37、-1.要证要证k+1k+1结点树的边数为结点树的边数为k.k.事实上事实上,树树G G必必有一树叶有一树叶w w(否则否则G G任一点的度都大于任一点的度都大于1,1,从任一点出从任一点出发沿一边进入另一点恒可沿另一边离开发沿一边进入另一点恒可沿另一边离开.因因G G的结点的结点有限有限,故有限步以后一定要回到前面的点故有限步以后一定要回到前面的点,便与便与G G无无回路相矛盾回路相矛盾).).子图子图G-wG-w显然是树显然是树,其点数是其点数是k,k,按按归纳假设归纳假设其边数是其边数是k-1,k-1,从而从而G G的边数是的边数是k=(k+1)-1,k=(k+1)-1,归纳证明完成归纳证
38、明完成.证证 :要证要证若若G G无回路且无回路且m=n-1,m=n-1,则则G G连通连通.不然的不然的话话,G,G有有k(k(2)2)个无回路的连通分支个无回路的连通分支(树树):):T T1 1,T,Tk k,设设T Ti i为为(n(ni i,m,mi i)图图,则则 m=mm=m1 1+m+mk k=(n=(n1 1-1)+-1)+(n(nk k-1)=(n-1)=(n1 1+n+nk k)-kn-1)-k2(n-1)=2m,2(n-1)+12(n-1)=2m,与与d(vd(v1 1)+d(v)+d(vn n)=2m)=2m的已知规律的已知规律矛盾矛盾.生成树生成树的概念的概念n定义
39、定义 无向图无向图G=G=V,EV,E 的生成子图的生成子图T T是树是树,则称则称T T是是G G的一棵的一棵生成树生成树(不唯一不唯一,图图8.6-28.6-2).).n任何连通无向图任何连通无向图G G至少有一棵生成树至少有一棵生成树.证证(破圈法破圈法)若若G G无简单回路无简单回路,则则G G自己是一棵生成树自己是一棵生成树.否则否则,G,G有简单回路有简单回路C C1 1,删去删去C C1 1的一边所得的一边所得G G的生成子的生成子图记为图记为G G1 1.若若G G1 1无回路无回路,则则G G1 1为生成树为生成树;否则否则G G1 1有简单有简单回路回路C C2 2,删去删
40、去C C2 2的一边所得的一边所得G G1 1的生成子图记为的生成子图记为G G2 2.若若G G2 2无回路无回路,则则G G2 2为生成树为生成树;否则否则,照此继续照此继续.易见经易见经m+1-nm+1-n步必可找到步必可找到G G的一棵生成树的一棵生成树.n推论推论 无向图无向图G G连通当且仅当连通当且仅当G G有生成树有生成树.最小生成树最小生成树的概念的概念n定义定义 赋权简单连通赋权简单连通无向图无向图G=G=V,E,WV,E,W 的子图的子图 H H的的权定义为权定义为 H H 的所有边的权和的所有边的权和.G.G中权最小的生成树中权最小的生成树称为称为最小生成树最小生成树(
41、对普通简单连通图不考虑最小生对普通简单连通图不考虑最小生成树成树).).n最小生成树有很强的最小生成树有很强的应用背景应用背景,例如例如:设计联系若干设计联系若干城市的最短线路通信网城市的最短线路通信网;设计供应若干居民点的最设计供应若干居民点的最短自来水管线路等短自来水管线路等.求最小生成树求最小生成树的的KruskalKruskal算法算法(避圈法避圈法)n算法算法 将赋权简单连通将赋权简单连通无向图无向图G G的边的边排序排序:e:e1 1 e e2 2 e em m.开始时开始时 k:=1,A:=k:=1,A:=.步骤步骤 若若A Aeek k 导出的子图无回路导出的子图无回路,则则
42、A:=AA:=Aeek k.步骤步骤 若若|A|=|A|=n-1n-1,算法结束算法结束;否则转否则转步骤步骤.例例 对左边无向图用对左边无向图用KruskalKruskal算法求得算法求得右边的最小生成树右边的最小生成树.1 2 3 4 5 6 7 8 9 10 11 121 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 71 2 3 4 5 6 7=n-1=n-11234567891011121235689KruskalKruskal算法算法的正确性的正确性证明证明:由由KruskalKruskal算法必可求得赋权简单图算法必可求得赋权简单图G G的一棵生成的一
43、棵生成树树T T0 0(因因G G连通连通),),不妨令不妨令T T0 0的边为的边为e e1 1,e,en-1n-1.若若T T0 0不是不是最小生成树最小生成树,则则G G的每棵最小生成树对应一个的每棵最小生成树对应一个i,i,使得使得e ei+1i+1 T T但但ee1 1,e,ei i T(i=0T(i=0表示表示T T与与T T0 0无公共边无公共边).).由于由于最小生成树有限最小生成树有限,我们取我们取T T为对应为对应最大最大i i的那棵最小生成的那棵最小生成树树.于是于是,T+e,T+ei+1i+1有唯一基本回路有唯一基本回路C(C(包含包含e ei+1i+1).).因因树树
44、T T0 0无无回路回路,故有边故有边f f C C且且f f T T0 0,即即f f T-TT-T0 0.在在T T中以中以e ei+1i+1代代f f(仍无回路仍无回路)得新生成树得新生成树T=T+eT=T+ei+1i+1-f,-f,其权为其权为W(T)=W(T)+WW(T)=W(T)+W(e(ei+1i+1)-W(f)-W(f)W(T)W(T).于是于是W(eW(ei+1i+1)W(f).W(f).因因T T为树为树,e,e1 1,e,ei i,f,f诱导的子图无回路诱导的子图无回路,从而由从而由KruskalKruskal算法选边算法选边的过程知的过程知W(eW(ei+1i+1)W(
45、f).W(f).所以所以W(eW(ei+1i+1)=W(f).)=W(f).这意味着这意味着W(T)=W(T),W(T)=W(T),即即TT也是也是G G的最小生成树的最小生成树.但但TT包含包含ee1 1,e,ei i,e,ei+1i+1,他比他比T T对应更大的对应更大的i i值值,引出引出矛盾矛盾.得证得证必须是最小生成树必须是最小生成树.求最小生成树的求最小生成树的破圈法破圈法n此法此法19751975年由年由中国数学家管梅谷中国数学家管梅谷教授首先提出教授首先提出,具具体算法如下体算法如下:将赋权简单连通将赋权简单连通无向图无向图G=G=V,EV,E 的边排序的边排序:e e1 1
46、e e2 2 e em m.开始时开始时 A:=E.A:=E.步骤步骤 若若A A无回路无回路,则则A A是最小生成树是最小生成树,算法结束算法结束,否否则转步骤则转步骤.步骤步骤 在在A A中任取的一条回路中任取的一条回路C C中取有最大权的边中取有最大权的边e,e,置置A:=A-eA:=A-e后转步骤后转步骤.n破圈法的正确性基于下列事实破圈法的正确性基于下列事实(定理定理8.6-98.6-9):):G G的任何一条简单回路的任何一条简单回路C C中权最大的边中权最大的边f f一定不属于一定不属于任何最小生成树任何最小生成树T.(CT.(C必有一边必有一边e e不属于不属于T,T,若若f
47、f属于属于T,T,则以则以e e代代f f所得的生成树所得的生成树TT的权的权W(T)=W(T)+W(e)-W(f)W(T)=W(T)+W(e)-W(f)W(T)W(T),产生矛盾产生矛盾.).)树叶树叶,分枝点分枝点,子树子树的概念的概念n有根树的典型例子是有根树的典型例子是家谱树家谱树.树根是家谱的第一代老树根是家谱的第一代老祖宗祖宗;每条弧始点和终点分别是每条弧始点和终点分别是父父和和子子;每条路径始每条路径始点是点是祖先祖先,终点是终点是后裔后裔.n出度为出度为0 0的结点的结点(没有儿子者没有儿子者)称为称为树叶树叶,否则称为否则称为分分枝点枝点;分枝点及其所有后裔组成分枝点及其所有
48、后裔组成子树子树(非根的分枝点非根的分枝点导出导出真子树真子树).).n从树根从树根r r到一结点到一结点a a有唯一有向路径有唯一有向路径,其其长度长度t t称为称为a a的的层次层次(a(a为为第第t t代孙代孙),),有根树各结点层次最大值称为树有根树各结点层次最大值称为树的的高度高度.有根树有根树的的表示功能表示功能n与家谱的作用相似与家谱的作用相似,可用有根树表示复杂组织的可用有根树表示复杂组织的层层次结构次结构或复杂事物的或复杂事物的分类结构分类结构,计算机的计算机的文件系统文件系统等等等等.n在计算机科学中常用有根树表示算术运算式在计算机科学中常用有根树表示算术运算式.其中其中一种作法是一种作法是:运算对象放在树叶运算对象放在树叶的位置的位置,运算符放运算符放在分枝点在分枝点的位置的位置,每个分枝点上的每个分枝点上的运算都作用在它运算都作用在它的的左左子树和子树和右右子树上子树上,计算次序由路径长度确定计算次序由路径长度确定,远的优先远的优先.