《图论及其算法2008数模.ppt》由会员分享，可在线阅读，更多相关《图论及其算法2008数模.ppt（117页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.图论问题的起源图论问题的起源 18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块,它们通过七座桥相互连接,如下图.当时该城的市民热衷于这样一个游戏:“一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点？”SNAB七桥问题的分析 七桥问题看起来不难，很多人都想试一试，但没有人找到答案.后来有人写信告诉了当时的著名数学家欧拉.千百人的失败使欧拉猜想,也许那样的走法根本不可能.1876年,他证明了自己的猜想.Euler把南北两岸和两个岛抽象成四个点,将连接这些陆地的桥用连接相应两点的一条线来表示,就得到如下一个简图:SNAB欧拉的结论欧拉的结论欧拉指出欧拉指出:一个线图中存在通过每边一次
2、仅一次一个线图中存在通过每边一次仅一次回到出发点的路线的充要条件是回到出发点的路线的充要条件是:1)1)图是连通的图是连通的,即任意两点可由图中的一些边连即任意两点可由图中的一些边连接起来接起来;2)2)与图中每一顶点相连的边必须是偶数与图中每一顶点相连的边必须是偶数.由此得出结论由此得出结论:七桥问题无解七桥问题无解.欧拉由七桥问题所引发的研究论文是图论的开欧拉由七桥问题所引发的研究论文是图论的开篇之作篇之作,因此称欧拉为图论之父因此称欧拉为图论之父.4.4.图的作用图的作用 图是一种表示工具.改变问题的描述方式,往往是创造性的启发式解决问题的手段.一种描述方式就好比我们站在一个位置和角度观
3、察目标,有的东西被遮挡住了,但如果换一个位置和角度,原来隐藏着的东西就可能被发现.采用一种新的描述方式,可能会产生新思想.图论中的图提供了一种直观,清晰表达已知信息的方式.它有时就像小学数学应用题中的线段图一样,能使我们用语言描述时未显示的或不易观察到的特征、关系,直观地呈现在我们面前,帮助我们分析和思考问题,激发我们的灵感.5.5.图的广泛应用图的广泛应用图的应用是非常广泛的图的应用是非常广泛的,在工农业生产、交通运在工农业生产、交通运输、通讯和电力领域经常都能看到许多网络输、通讯和电力领域经常都能看到许多网络,如如河道网、灌溉网、管道网、公路网、铁路网、电河道网、灌溉网、管道网、公路网、铁
4、路网、电话线网、计算机通讯网、输电线网等等话线网、计算机通讯网、输电线网等等.还有许还有许多看不见的网络多看不见的网络,如各种关系网如各种关系网,像状态转移关系、像状态转移关系、事物的相互冲突关系、工序的时间先后次序关系事物的相互冲突关系、工序的时间先后次序关系等等等等,这些网络都可以归结为图论的研究对象这些网络都可以归结为图论的研究对象-图图.其中存在大量的网络优化问题需要我们解决其中存在大量的网络优化问题需要我们解决.还有象生产计划、投资计划、设备更新等问题也还有象生产计划、投资计划、设备更新等问题也可以转化为网络优化的问题可以转化为网络优化的问题.6.基本的网络优化问题 基本的网络优化问
5、题有:最短路径问题、最小生成树问题、最大流问题和最小费用问题.图论作为数学的一个分支,已经有有效的算法来解决这些问题.当然这当中的有些问题也可以建立线性规划的模型,但有时若变量特别多,约束也特别多,用线性规划的方法求解效率不高甚至不能在可忍受的时间内解决.而根据这些问题的特点,采用网络分析的方法去求解可能会非常有效.例如,在1978年,美国财政部的税务分析部门在对卡特尔税制改革做评估的过程中,就有一个100,000个约束以上,25,000,000个变量的问题,若用普通的线性规划求解,预计要花7个月的时间.他们利用网络分析的方法,将其分解成6个子问题,利用特殊的网络计算机程序,花了大约7个小时问
6、题就得到了解决.图的基本概念(1)定义定义1 图G是一个三元组,记作其中(1)V(G)=v1,v2,vn=,称为图G的结点集.(2)E(G)=e1,e2,em是G的边集合,其中ei为vj,vt或.若ei为vj,vt,称ei为vj和vt为端点的无向边;若ei为,称ei为vj 为起点,vt为终点的有向边;(3)称为关联函数.图的基本概念(2)定义定义2 2.邻接结点邻接结点:关联于同一条边的两个结点.孤立结点:不与任何结点相连接的结点.邻接边邻接边:关联于同一顶点的两条边.环环:两端点相同的边称为环或自回路.平行边平行边:两个结点间方向相同的若干条边称为平行边或重边对称边对称边:两端点相同但方向相
7、反的两条有向边.图的基本概念(3)定义定义3 无向图无向图:每条边都是无向边的图.有向图有向图:每条边都是有向边的图.混合图混合图:图中不全是有向边,也不全是无向边的图.平凡图平凡图:只有一个孤立结点的图.定义定义4 多重图多重图:含有平行边的图.简单图简单图:无环且无平行边的图.完全图完全图:任何不同结点之间都有边相连的简单无向图.图的基本概念(4)说明:(1)在简单图 中,以x为起点y为终点的边至多有一条,因此,图中的边可直接用顶点对表示,而关联函数 就可以直接表示在其边集中,故可简记为G=.(2)对无向图G,将G中的每条边用两条与e有相同端点对称边e和e来代替后得到一个有向图D,这样得到
8、的有向图D称为G的对称有向图的对称有向图.由此可见,无向图可视为特殊的有向图.(3)n个结点的完全图记为Kn,完全图Kn有 条边.完全图的对称有向图称为完全有向图,记作 .(4)图G的顶点个数称为图图G G的阶的阶.(5)对于有向图D,去掉边上的方向得到的无向图G称称为为D D的基础图的基础图.反之,任一个无向图G,将G的边指定一个方向得到一个有向图D,称D D为为G G的一个定向图的一个定向图.例 证明:在任意六个人的聚会上,要么三个曾相识,要么三个不曾相识.证明:用A,B,C,D,E,F代表这六个人,若两人曾相识,则在代表该两人的顶点间连一条红边;否则连一条蓝边.于是,原问题等价于证明所得
9、图中必含有同色三角形.考察某一顶点,设为F.与F关联的边中必有三条同色,不妨设它们是三条红边FA,FB,FC.再看三角形ABC.若它有一条红边,设为AB,则FAB是红边三角形;若三角形ABC没有红边,则其本身就是蓝边三角形.图的运算图的运算(一）一）定义定义1 1 设 与 是任何两个图.若 且 是 在 上的限制,则称 是是G G的子图的子图,记作 ,称G为G1的母图.若 且V1=V,则称 是G的生成子图或支撑子图生成子图或支撑子图.设 ,以V1为顶点,以两端点均在V1中的全体边为边集的G的子图,称为V V1 1的的导出子图导出子图,记作GV1.设 ,以E1为边集,以E1中的边关联的全部顶点集的
10、G的子图,称为E E1 1的的导出子图导出子图,记作GE1.特别,若 ,则以 G-V1表示从G中删去V1内的所有点以及与这些顶点关联的边所得到的子图,若V1=v,常把G-v简记为G-v,类似地,设 ,G-E1表示在G中删去E1中所有边所得的子图,同样G-e简记为G-e.图的运算图的运算(二）二）定义定义2 设G是n阶无向简单图,以V为顶点集,以所有能使G成为完全图完全图Kn的添加边组成的集合为边集的图,称为G相对于完全图完全图Kn补图补图,简称G的补图,记作 .定义定义3 设G1和G2都是图G的子图.G G1 1和和G G2 2的并的并G G1 1G G2 2:仅由G1和G2中所有边组成的图.
11、G1和和G2的交的交 G G1 1G G2 2 :仅由G1和G2的公共边组成的图.G G1 1和和G G2 2的差的差G G1 1-G-G2 2:仅由G1中去掉G2中的边组成的图.G1和和G2的环的环和和G G1 1 G G2 2:在G1和G2的并中去掉G1和G2的交 所得到的图.路与连通图路与连通图(一一)定义定义1 1 设设u u和和v v是任意图是任意图G G的顶点的顶点,图图G G的一条的一条u-vu-v是有是有限的顶点和边交替序列限的顶点和边交替序列u u0 0e e1 1u u1 1e e2 2uun-1n-1e en nu un n(u=(u=u u0 0,v=u,v=un n)
12、,),其中与边其中与边e ei i(1(1 i i n)n)相邻的两顶点相邻的两顶点u ui-1i-1和和u ui i正好是正好是e ei i的两个端点的两个端点.数数n(n(链中出现的边数链中出现的边数)称为链的长度称为链的长度.u(u.u(u0 0)和和v(uv(un n)称为链的端点称为链的端点,其余其余的顶点称为链的内部点的顶点称为链的内部点.一条一条u-vu-v链链,当当u u v v时时,称称它为开的它为开的,否则称为闭的否则称为闭的.边互不相同的链称为边互不相同的链称为迹迹,内部点互不相同的链称为路内部点互不相同的链称为路.注释注释1.1.(1)(1)在一条链中在一条链中,顶点和
13、边可以重复顶点和边可以重复.(2)(2)若若G G是简单图是简单图,G,G中的链中的链u u0 0e e1 1u u1 1e e2 2uun-1n-1e en nu un n还可用还可用结点序列结点序列u u0 0u u1 1uun-1n-1u un n表示表示.(3)(3)不含边的链不含边的链(即长度为即长度为0)0)称为平凡链称为平凡链.(4)(4)设设W W是有向图是有向图D D中中u-vu-v链链(迹迹,路路),),指定指定W W的方向从的方向从u u到到v.v.若若W W中所有边的方向与此方向一致中所有边的方向与此方向一致,则称则称W W为为D D中从中从u u到到V V的有向链的有
14、向链(迹迹,路路).).路与连通图路与连通图(二二)定义定义2.两端点相同的迹两端点相同的迹(即闭集即闭集)称为回称为回.两两端点相同的路端点相同的路(即闭路即闭路)称为称为圈或回路圈或回路.长度长度为为K,奇数奇数,偶数的回偶数的回(圈圈)分别称为分别称为K,奇奇,偶回偶回(圈圈).有向闭迹有向闭迹(闭路闭路)称为称为有向回有向回(有向圈有向圈).定理定理1.若简单图若简单图G中每个顶点的度数至少是中每个顶点的度数至少是k(k 2),则则 G中必含有一个长度至少是中必含有一个长度至少是k+1的圈的圈.定理定理2.设简单图设简单图G中每个顶点的度数至少是中每个顶点的度数至少是3,则则G中含有偶
15、圈中含有偶圈.定义定义3.给定无向图给定无向图G=,x,y V(G),若若图中存在连接图中存在连接x和和y的路的路,称节点称节点x和和y是是连通的连通的.规定规定x到自身总是连通的到自身总是连通的.路与连通图路与连通图(四四)1.说明:容易验证,结点集V(G)上的顶点间的连通关系是V(G)上的一个等价关系等价关系,该等价关系确定V(G)的一个划分V1,V2,Vm,使得当且仅当当且仅当两个顶点x和y属于同一子集Vi时,x和y才是连通的.Vi在G中的导出子图GV1,GV2,GVm称为G的连通分支或分支连通分支或分支,m称为G的连通分支数,记作W(G)=m.如下图有4个连通分支.定义4.如果无向图G
16、中每一对不同的顶点x和y都有一条路,即W(G)=1,则称G是连通图,反之称为非连通图.路与连通图路与连通图(五五)引理1 非平凡图G是连通图当且仅当对V(G)的每一个非空真子集S,定理3 设G是P阶连通图,则悬挂点:度数为1顶点.定理4 设连通图G至少有两个顶点,其边数小于顶点数,则此图至少有一个悬挂点.路与连通图路与连通图(七七)定义5 设 是有向图,若图 D中存在x到y的有向路,称结点x可达结点y.规定x到自身总是可达的.定义定义6 设G是有向图,任何结点间,至少有一个结点可达另一个结点,则称该有向图是单侧连通的.如果有向图D的任何一对结点间是相互可达的,则称该有向图是强连通强连通的的.若
17、有向图G的基础图是连通的,则称该有向图D是弱弱连通的连通的.定义定义7 设G是有向图,G中所有从x到y的有向路的最小长度称为从x到y的距离.称为图图G的直径的直径.连通图和二分图(1)定义1 如果在图G中删去一个结点x后,图G连通分支数增加,即W(G-x)W(G),则称结点x x为为G G的的割点割点.如果在图G中删去一条边e后,图G的连通分支数增加,即W(G-e)W(G),则称边边e e为为G G的割的割边边.定义2 没有割点的非平凡连通图称为块块.G中不含割点的极大连通子图称为图图G G的块的块.定义3 如果G的顶点集的一个真子集T满足G-T不连通或是平凡图,则称T T为为G G的一个点割
18、的一个点割.如果图G的边集的一个真子集S满足G-S不连通或是平凡图,则称S S为为G G的一个边割的一个边割.定义4设G是连通图,称 是G的点割为G的点连通度或连通度点连通度或连通度;称 是G的边割为G的边连通度的边连通度.定理1 对一个图G,有 是图G的最小顶点度的最小顶点度.连通图和二分图(3)定义5 如果无向图G的连通度 称图G是n n连通的或连通的或G G为为n n连通图连通图.若 称图G G是是n n边连通的或边连通的或G G为为n n边连通图边连通图.定理2 设图G是n连通的,则对定理3 设G是2边连通图,则G有强连通的定向图.连通图和二分图(4)定义6 把简单图G的顶点集合分成两
19、个不相交的非空集合V1,V2,使得图G中的每一条边,与其关联的两个结点分别在V1和V2中,则G称为偶图或二分图,记作G=,其中V1和V2叫做G的二划分.对于二分图G=,若 ,V1中的任意一点与V2中的所有点相邻且V2中的任意一点与V1中的所有点相邻,则称该图为结点m和n的完全偶图或完全二分图,记作Km,n.定理4 非平凡图G是二分图当且仅当当且仅当G中不含有长为奇数的圈.图的矩阵表示(1)1.邻接矩阵:设 是任意图,其中V=x1,x2,xn,E=e1,e2,em,则n阶方阵A=(aij)称为G的邻接矩阵.其中aij为图G中以xi为起点且以xj为终点的边的数目.说明1:由定义易知,无向图的邻接矩
20、阵是对称矩阵,而有向图的邻接矩阵未必是对称矩阵.定理1 已知有向图 ,其中V=x1,x2,xn,且A=(aij)nn为G的邻接矩阵,则Ak中的i和j列元素aij(k)是图G中从xi到xj且长度为k的有向链的数目.说明2:该定理同样适合无向图,且定理中的链不能改为迹或路.推论1 若G是P阶简单图,且G的邻接矩阵为A=(aij),则对G的每一个顶点vi,i=1,2,p,有d(vi)=aii(2),其中A2=(aii(2).定理2 已知P(P3)阶图G的邻接矩阵为A,作P阶方阵R=A+A2+Ap-1,则图G连通的充分必要条件为R中的每个元素都不为零.2.关联矩阵关联矩阵:设 是有向图,且V=,称 阶
21、矩阵M=(mij)为有向图D的关联矩阵,其中设 是无向图,且V=,称 阶矩阵M=(mij)为无向图D的关联矩阵,其中说明3:从关联矩阵可得无向图的一些性质:(1)关联矩阵的每一列只有两个1(每条边只关联两个顶点);(2)关联矩阵的每一行元素之和为对应顶点的度;(3)若某行中元素全为零,则相应顶点为孤立点;(4)重边所对应的列完全相同.3.可达矩阵:设G=是无重边有向图,其中V=,称 阶矩阵P=(Pij)为G的可达矩阵.其中图的矩阵表示(2)定理定理2 已知P(P3)阶图G的邻接矩阵为A,作P阶方阵R=A+A2+Ap-1,则图G连通的充分必充分必要条件要条件为R中的每个元素都不为零.2.关联矩阵
22、:设 是有向图,且V=,称 阶矩阵M=(mij)为有向图D的关联矩阵,其中 图的矩阵表示(3)设 是无向图,且V=,称 阶矩阵M=(mij)为无向图无向图D的关联矩阵,其中说明3:从关联矩阵可得无向图的一些性质:(1)关联矩阵的每一列只有两个1(每条边只关联两个顶点);(2)关联矩阵的每一行元素之和为对应顶点的度;(3)若某行中元素全为零,则相应顶点为孤立点;(4)重边所对应的列完全相同.欧拉图欧拉图(1)定义定义1 1 给定无孤立结点的无向图G,经过图G的每边一次且仅一次的迹为一条欧拉路.经过图G的每边一次且仅一次的回为一条欧拉回路.说明:(1)由定义,含有欧拉路(回)的图显然是连通的;(2
23、)欧拉路是迹(边互不重复),但不是严格意义上的路.定理1连通图G具有欧拉回路当且仅当其每个顶点的度数为偶数.欧拉图与哈密顿图(2)定理定理2 2 连通图连通图G G具有欧拉路而无欧拉回路具有欧拉路而无欧拉回路,当且仅当当且仅当G G恰有两个奇数度顶点恰有两个奇数度顶点.定义定义2 2 给定有向图给定有向图D,D,经过经过D D中每边中每边一次且仅一次且仅一次一次的的有向迹有向迹称为称为D D的的有向欧拉路有向欧拉路.经过经过D D中中每边一次且仅一次的每边一次且仅一次的有向闭迹有向闭迹(回回),),称为有称为有向欧拉回路向欧拉回路.欧拉图与哈密顿图(3)定理定理3 具有弱连通性的有向图具有弱连
24、通性的有向图G具有有向欧具有有向欧拉回路拉回路,当且仅当当且仅当G的每个结点的入度等于出的每个结点的入度等于出度度.具有弱连通性的有向图具有弱连通性的有向图G具有有向欧拉路具有有向欧拉路,当当且仅当且仅当在在G中中,一个结点的入度比出度大一个结点的入度比出度大1,另另一个结点的入度比出度小一个结点的入度比出度小1,而其余每个结点而其余每个结点的入度等于出度的入度等于出度.定义定义3 含有含有欧拉回路的无向连通图欧拉回路的无向连通图与与含有向欧含有向欧拉回路的弱连通有向图拉回路的弱连通有向图,统称为欧拉图统称为欧拉图.求Euler图的Euler回路的Fleury算法.(1)(1)任意选取一个顶点
25、任意选取一个顶点v v0 0,置置W W0 0=v=v0 0;(2)(2)假定迹假定迹(若是有向图若是有向图,则是有迹则是有迹)W Wi i=v=v0 0e e1 1v v1 1e ei iv vi i已经选出已经选出,则则用下列方法从用下列方法从E(G)-eE(G)-e1 1,e,e2 2,e ei i 中取中取e ei+1i+1;(a)e(a)ei+1i+1与与v vi i关联关联(若是有向图若是有向图,e,ei+1 i+1 以以v vi i为起点为起点)(b)(b)除非没有别的边可选择除非没有别的边可选择,e,ei+1i+1不是不是 G Gi i=G-e=G-e1 1,e,e2 2,e
26、ei i 的割边的割边.(3)(3)当当(2)(2)不能执行时不能执行时,停止停止.否则让否则让i+1i+1i,i,转转(2).(2).(以以p46p46为例为例)定理定理4 4若若G G是是EulerEuler图图,则则FleuryFleury算法终止时得到的迹算法终止时得到的迹是是EulerEuler回路。回路。定义1 给定无向图G,若存在一条路经过图G的每个结点一次且仅一次,这条路称为哈密顿路哈密顿路.若存在一条闭路经过图G的每个结点一次且仅一次,这条闭路称为哈密顿回路哈密顿回路.定义2 给定有向图D,若存在一条路经过图G的每个结点一次且仅一次,这条路称为哈密顿有向路哈密顿有向路.若存在
27、一条闭路经过图G的每个结点一次且仅一次,这条有向闭路称为哈密顿有向回路哈密顿有向回路.哈密顿图(1)哈密顿图(1)定义3 具有哈密顿回路的无向图与具有哈密顿有向回路的有向图,统称为哈密顿图哈密顿图.例1 对于完全图Kn(n3),由于Kn中任意两个顶点之间都有边,从Kn的某一顶点开始,总可以遍历其余节点后,再回到该结点,因而Kn(n3)是哈密顿图.说明:判断一个给定的图是否为哈密顿图,是图论中尚未解决的难题之一,下面介绍若干必要条件和充分条件.哈密顿图(3)定理定理1 设任意n(n3)阶图G,对所有不同非邻接顶点x和y,若deg(x)+deg(y)n,则G是哈密顿图是哈密顿图.定理定理2 设u和
28、v是n阶图G的不同非邻接点,且deg(u)+deg(v)n,则G+边u,v是哈密顿图当且仅当当且仅当哈密顿图.定义定义4 给定n阶图G,若将图G度数之和至少是n的非邻接点用一条边连接起来得图G,对图G重复上述过程,直到不再有这样的结点对存在为止,所得到的图,称为是原原图图G的闭包的闭包,记作C(G).定理定理3 一个图是哈密顿图当且仅当当且仅当它的闭包是哈密顿图.定理4 设G是阶至少为3的图,如果G的闭包是完全图,则G是哈密顿图是哈密顿图.定理5 如果G是一个n阶(n3)任意图,且对G的每个顶点x,都有deg(x)n/2,则G是哈密顿图是哈密顿图.说明:由哈密顿图的定义可知,哈密顿图有向图必是
29、强连通的,哈密顿无向图必无割点.8.哈密顿图(4)定理5 若G是一个哈密顿图,则对于V(G)的每个非空真子集S,其中W(G-S)为G-S的分支数.9.9.哈密顿图哈密顿图(5)(5)说明:定理6只是一个必要条件,如下的皮特森图,尽管有 但它不是哈密顿图.10.10.哈密顿图哈密顿图(6)(6)应用应用定理定理5 5 若若G G是一个是一个n(nn(n 3)3)阶任意图阶任意图,且对且对G G的的每个顶点每个顶点x,x,都有都有deg(x)deg(x)n/2,n/2,则则G G是哈密顿图是哈密顿图.例例1.111.11个学生要共进晚餐个学生要共进晚餐,他们将坐成一个圆桌他们将坐成一个圆桌,计计划
30、要求每次晚餐上划要求每次晚餐上,每个学生有完全不同的邻座每个学生有完全不同的邻座.这样能共进晚餐几次这样能共进晚餐几次.分析分析:如何将该问题转化成图论中的相关问题如何将该问题转化成图论中的相关问题.实际实际上上,可以这样来构造一个图可以这样来构造一个图,即以每个学生看作图即以每个学生看作图的顶点的顶点,以学生的邻座关系作为图的以学生的邻座关系作为图的边边,11.11.哈密顿图哈密顿图(7)(7)这样学生每次进餐的就坐方式就对应一个哈密顿这样学生每次进餐的就坐方式就对应一个哈密顿回回路路.两两次次进进餐餐中中,每每个个学学生生有有完完全全不不同同的的邻邻座座对对应应着着两两个个没没有有公公共共
31、边边的的哈哈密密顿顿回回路路.因因为为每每个个学学生生都都可可以以与与其其余余学学生生邻邻座座,故故问问题题转转化化为为在在图图K11中找出所有没有公共边的哈密顿回路的个数中找出所有没有公共边的哈密顿回路的个数.K11中中共共有有 条条边边,而而K11中中每每条条哈哈密密顿顿回回路路的的长长度度为为11,因因此此K11中中最最多多有有55/11=5条条没没有有公公共共边边的的哈哈密密顿顿回回路路,构构造造方方法法为为:设设第第一一条条哈哈密密顿顿回回路路为为(1,2,3,11,1),将将1固固定定在在圆圆心心,其其余余固固定定在在圆圆周周上上,如如图图(1)所所示示,然然后后将将图图的的顶顶点
32、点旋旋转转i3600/10(i=1,2,3,4),从从而而就就得得到到另另外外4个个哈密顿回路哈密顿回路.12.12.哈密顿图哈密顿图(8)(8)1 (3,2,4,6)5 7(5,3,2,4)(2,4,6,8)3 9(7,5,3,2)(4,6,8,10)2 11(9,7,5,3)(6,8,10,11)4 10(11,9,7,5)(8,10,11,9)6 8(10,11,9,7)图图1 1第五节 最短路路问题1.加权图:边上有数的图称为加权图;该数称为边的权。2.最短路问题:如何求两个结点之间的最短路.3.迪克斯曲拉算法:这是荷兰计算机科学教授Edsger W.Dijkstra(1930-)在1
33、959年发现的一个算法.他在1972年获得计算机协会授予的图灵奖,这是计算机科学中最具声望的奖项.迪克斯曲拉迪克斯曲拉算法算法是求出一个连通加权简单图中从结点a到结点z的最短路.边i,j的权(i,j)0,且结点x的标号为L(x),结束时,L(z)是从x到z的最短路的长度.4.迪克斯曲拉算法流程Procedure Dijkstra(G:所有权为正的加权连通简单图)G带有顶点a=v0,v1,vn=z和权w(vi,vj),若vi,vj不是G中的边,则w(vi,vj)=)For i:=1 to n L(vi):=L(a):=0 S:=初始化标记,a的标记为0,其余结点标记为,S是空集While zS
34、beginu:=不属于S的L(u)最小的一个顶点 S:=SuFor 所有不属于S的顶点v If L(u)+w(u,v)L(v)then L(v):=L(u)+w(u,v)这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记End L(z)=从a到z的最短路的长度.例1.用迪克斯曲拉算法求下图所示的加权图中顶点a与z之间最短路的长度.（见65页）a4b5d2110c8e263z定理1 迪克斯曲拉算法求出连通简单无向图的中两点之间的最短路的长度。定理2 迪克斯曲拉算法使用O(n2)次运算（加法和比较）来求出n阶连通简单无向加权图中两个顶点之间的最短路的长度。迪克斯曲拉算法可以推广到求加权有
35、向图的最短路。定理定理3 设有向图G中不含长度非正的有向圈，并且从点1到其余各点都有有限长的有向路，那么式（2）有唯一有限解。.Floyd算法 Dijkstra算法只求出一个特定顶点到其他各顶点的最短路.但在许多实际问题中,需求出任意两点之间的最短路,如全国各城市之间最短的航线,选址问题等.Floyd算法可以比较好地解决这一问题.为介绍Floyd算法,先定义矩阵的两种运算.定义1 已知矩阵A=(aij)ml,B=(bij)ln,规定C=AB=(cij)mn,其中cij=min(ai1+b1j,ai2+b2j,ail+blj).定义2 已知矩阵A=(aij)mn,B=(bij)mn,规定D=AB
36、=(dij)mn,其中dij=min(aij,bij).可以利用上面定义的运算求任意两点间的最短距离.已知n阶加权简单图G,设D=(dij)nn是图G的边权矩阵即dij=w(i,j)(若G是有向图,则dij=w),若结点i到结点j无边相连时,则取dij=.然后依次计算出矩阵D2,D3,Dn及S,其中D2=DD=(dij2)nnD3=D2 D=(dij3)nn,Dn=Dn-1 D=(dijn)nnS=DD2D3Dn=(Sij)nn由定义可知,dijk表示从结点i到结点j经k边的路(在有向图中即为有向路)中的长度最短者.这就是Floyd算法.Floyd算法的时间复杂度为O(n4).v121v27v
37、6v41332v6例2.利用Floyd算法求下图中任意两点间最短有向路的长度.(p71-73)Warshall算法D=(dij)为图G的边权矩阵(1)输入D(2)k：=1；(3)i：=1；(4)dij:=min(dij,dik+dkj),j=1,2,n(5)i：=i+1,若in,转(4);(6)k：=k+1,若kn,转(3);否则停止。实质上是考虑经过n次结点转换每一次保留最短路的长度。举例见P74.旅行推销员问题和中国投递员问题（NPC问题）一、旅行推销员问题（最邻近算法最邻近算法给出旅行推销员问题的近似解）给出旅行推销员问题的近似解）步骤如下步骤如下（1 1）由任意选择的结点开始，找出于该
38、结点邻近）由任意选择的结点开始，找出于该结点邻近的点，形成一条有边的初始路。的点，形成一条有边的初始路。（2 2）以表示最新加到这条路上的结点，从不在路）以表示最新加到这条路上的结点，从不在路上的所有结点中选一个和最靠近的结点，把连接与上的所有结点中选一个和最靠近的结点，把连接与这一结点的边加到这条路上，重复这一步骤直到这这一结点的边加到这条路上，重复这一步骤直到这条路包含图中所有结点。条路包含图中所有结点。例例1 1 用用“最邻近算法最邻近算法”给出下面加权图中给出下面加权图中有充分小权的哈密顿路有充分小权的哈密顿路P76.P76.AFBECD1669 7151312183513182119
39、说明:“最邻近插入方法”是“最邻近法”的一种改进方法.该方法是在每次迭代中都构成一个闭的旅行路线.求解时,在已经建立旅程以外的顶点中,寻找最临近于旅程中某个顶点的顶点,然后将其插入该旅程中,并使增加的距离尽可能小,当全部顶点收入这个旅程后,就找到了所求的最短哈密顿回路的近似解.例2用“最邻近插入方法”找出上图中具有充分小权的哈密顿回路.定理定理1 1 设设P P是加权连通图是加权连通图G G中一条包含中一条包含G G的所有边的所有边至少一次的闭链，则至少一次的闭链，则P P最优的最优的充要条件充要条件（具有最小（具有最小长度）是：长度）是：（1 1）P P中无二重以上的边；中无二重以上的边；（
40、2 2）在）在G G的每个圈中的每个圈中C C中，重复边集中，重复边集E E的长度之和不的长度之和不超过这个圈的长度的一半，超过这个圈的长度的一半，即即W(E)W(E)1/2W(C).1/2W(C).二.中国邮路问题奇偶点奇偶点作业法作业法（1 1）把）把G G中所有奇度顶点配成对，将每对奇中所有奇度顶点配成对，将每对奇度顶点之间的一条路上的每边改为二重边，度顶点之间的一条路上的每边改为二重边，得到一个新图得到一个新图G G1 1，新图新图G G1 1中无奇度顶点，即中无奇度顶点，即G G1 1为多重欧拉图为多重欧拉图.（2 2）若）若G G1 1中某对结点间有多于两条边连接，中某对结点间有多
41、于两条边连接，则去掉其中偶数条边，留下一条或两条边连则去掉其中偶数条边，留下一条或两条边连接这两个结点，直到每对相邻结点至多由接这两个结点，直到每对相邻结点至多由2 2条边连接。得到图条边连接。得到图G G2 2.（3 3）检查）检查G G2 2的每个圈的每个圈C C，若某个圈若某个圈C C上重复边集上重复边集E E的的权和超过这个圈的权和的一半，则将权和超过这个圈的权和的一半，则将C C按定理按定理1 1必要必要性证明中的方法进行调整，直到对性证明中的方法进行调整，直到对G G2 2所有的圈其重所有的圈其重复边的权和不超过此圈权和的一半，得到图复边的权和不超过此圈权和的一半，得到图G G3
42、3.（4 4）用）用FleuryFleury算法求算法求G G的的EulerEuler回路回路.例例3 3 求求下图下图G G的最优环游的最优环游p81.p81.v1v2v3v4v5v6v7v8v9v10v11v122 4 5 5 3 6 4 6 4 65 4 4 7 9 3 8AV1 2 v10 4 v9 5 v8 V2 6 v11 4 v12 6 v75 5 4 4 7 7V3 9 v4 3 v5 8 v6B445 5 4 4 7 7993 84 8 6 4 63 6C446 4 66 65 4 4 4 4 79 3 83 6D444 4 3 32 4 55 3 6 4666642树的基本
43、概念定义定义1 树是无圈连通无向图树是无圈连通无向图.树中度数为树中度数为1的结点的结点称为称为树的叶树的叶.树中度数大于树中度数大于1的结点称为树的的结点称为树的分分枝点枝点或或内点内点.不相交的若干树称为不相交的若干树称为森林森林,即森林的每个连通分即森林的每个连通分枝是枝是树树.定义定义2 2 设设T T是有向图是有向图,若若T T的基础图是树的基础图是树,称称T T是是有有向树向树.定义定义3 3 仅一个结点的入度为仅一个结点的入度为0,0,其余所有结点的其余所有结点的入度都为入度都为1 1的有向树称为的有向树称为根树根树.入度为入度为0 0的结点称的结点称为根为根.出度为出度为0 0
44、的结点的结点(度数为度数为1 1的结点的结点)仍称为仍称为叶叶;出度不为出度不为0 0的结点称为的结点称为分枝点或内点分枝点或内点.由根到某由根到某一顶点一顶点v v的有向路的长度的有向路的长度,称为称为v v的层数的层数.根树的根树的高度高度就是顶点层数的最大值就是顶点层数的最大值.支撑树定义定义1 若若T是是G的一个生成子图且又是一棵树的一个生成子图且又是一棵树,则则称称T是图是图G的一棵的一棵生成树或支撑树生成树或支撑树.生成树生成树T中的中的边称为边称为T T的树枝的树枝,不在生成树不在生成树T中的中的G的边的边,称为称为树树T T的弦的弦.定理定理1 图图G有生成树有生成树G为连通图
45、为连通图.求连通简单图的生成树求连通简单图的生成树深度优先搜索和广度优先搜索深度优先搜索和广度优先搜索深度优先搜索深度优先搜索:任意选择图任意选择图G G的一个顶点为根的一个顶点为根,通过不断地增加边来形成以顶点通过不断地增加边来形成以顶点v v0 0为起点为起点的路的路,直到这条路经过图直到这条路经过图G G的每个顶点的每个顶点,此时此时得到的这条路就是该图的生成树得到的这条路就是该图的生成树.其中每条其中每条新边都与路上的一个顶点以及不在路上的新边都与路上的一个顶点以及不在路上的一个顶点关联一个顶点关联.如果这条路不经过图如果这条路不经过图G G的所的所有顶点有顶点,则返回倒数第二个顶点则
46、返回倒数第二个顶点,继续重复上继续重复上面过程面过程,直到不能添加更多的边为止直到不能添加更多的边为止.又图又图G G是有有限边数的连通图是有有限边数的连通图,故最后总能产生一故最后总能产生一棵生成树棵生成树.例例1 用深度搜索来找出下图用深度搜索来找出下图G的生成树的生成树a ab bcdefghijk广度优先搜索广度优先搜索基本思想基本思想:从图的顶点中任意地选择一个根从图的顶点中任意地选择一个根,然然后添加与该顶点相关联的所有边后添加与该顶点相关联的所有边,在这个阶在这个阶段添加的新顶点成为生成树里段添加的新顶点成为生成树里1 1层上的顶点层上的顶点,任意地排序它们任意地排序它们.下一步
47、下一步,按顺序访问按顺序访问1 1层上层上的每一个顶点的每一个顶点,只要不产生回路只要不产生回路,就添加与这就添加与这个顶点相关联的每条边个顶点相关联的每条边,这样就产生了树里这样就产生了树里2 2层上的顶点层上的顶点.遵循这样的原则继续下去遵循这样的原则继续下去,经经有限步骤后有限步骤后(因为图中只有有限条边因为图中只有有限条边)就产生就产生了生成树了生成树.例例2.用广度优先搜索找出例用广度优先搜索找出例1中图中图G的生成树的生成树.P106 最小支撑树最小支撑树 定义定义1:1:连通加权图里权和最小的支撑树称为连通加权图里权和最小的支撑树称为最小支撑树最小支撑树.最小支撑树的实际应用背景
48、最小支撑树的实际应用背景:在某一国家或地区在某一国家或地区,需建造一铁路网需建造一铁路网/公路网把一些城市连接起来公路网把一些城市连接起来,需需要总长度最短或造价最低要总长度最短或造价最低.寻找最小支撑树的贪心算法原理寻找最小支撑树的贪心算法原理:通过添加通过添加还没使用过的具有规定性质且权最小的边还没使用过的具有规定性质且权最小的边来进行的来进行的,其实质就是在每步上进行最优选其实质就是在每步上进行最优选择择,即即“局部最优化局部最优化”.普林算法算法的基本思想:首先选择带最小权的边,把它放进支撑树里.相继向树里添加带最小权的边,这些边与已在树里的顶点相关联,并且不与已在树里的边形成圈,直到
49、添加了n-1条边止.算法描述如下:算法1 普林算法Procedure prim(G:带n个顶点的连通无向图)T:=权最小的边For i:=1 to n-2 begine:=与T里顶点相关联的权最小的边,并且若添加到T里则不形成圈T:=添加e之后的T end T是G的最小支撑树例1 用普林算法求下图所示的最小支撑树定理1 普林算法是正确的,即在算法结束时,得到一棵最小支撑树.(证略)1 17 745102616158abcgfde克鲁斯卡尔(Kruskal)算法算法的基本思想:选择图中最小的一条边,相继添加不与已经选择的边形成圈的权最小的边,直到挑选n-1(n为结点的个数)条边为止.该算法的伪代
50、码如下:Procedure Kruskal(G:n个顶点的连通加权无向图)T:=空图.For i:=1 to n-1 beginE:=当添加到T里时不形成圈的G里权最小的边T:=添加e之后的TEndT是G的最小支撑树定理2 由Kruskal算法构作的任何生成树T=Ge1,e2,en-1都是G的最小生成树,n为G的结点数.基于破圈法的最小生成树的生成方法该方法是由管梅谷教授给出的,其基本思想为:设G是连通加权简单图,若G不是树,则G中必含有回路,删去G中含于某回路内权最大的一条边,所得的图记为G1,G1是G的连通生成子图.下一步,若G1不是树,又从G1某个回路内删去权最大的一条边,如此下去,最后