图论模型基础知识

1、下下回回停停 1. 图论的基本概念图论的基本概念2. 最短路问题及算法最短路问题及算法 图论模型基础知识图论模型基础知识 3. 最小生成树及算法最小生成树及算法 4. 旅行售货员问题旅行售货员问题1.图论的基本概念图论的基本概念1) 图的概念图的概念2) 赋权图与子图赋权图与子图3) 图的矩阵表示图的矩阵表示4) 图的顶点度图的顶点度5) 路和连通路和连通1) 图的概念图的概念 定义定义 一个一个图图G是指一个二元组是指一个二元组(V(G),E(G)，其中，其中: 其中元素称为图其中元素称为图G的的顶点顶点.组成的集合，即称为组成的集合，即称为边集边集,其中元素称为其中元素称为边边.),(ji

2、vv 定义定义 图图G的的阶阶是指图的顶点数是指图的顶点数|V(G)|, 用用来表示；来表示；v图的边的数目图的边的数目|E(G)|用用 来表示来表示. 也用也用来表示边来表示边jivv).,(jivv,)(21vvvGV是非空有限集，称为是非空有限集，称为顶顶点集点集，1)2) E(G)是顶点集是顶点集V(G)中的无序或有序的元素偶对中的无序或有序的元素偶对).,(EVG )(),(GEGVG 表示图，表示图，简记简记 用用 定义 若一个图的顶点集和边集都是有限集，则称若一个图的顶点集和边集都是有限集，则称 其为其为有限图有限图. 只有一个顶点的图称为只有一个顶点的图称为平凡图平凡图，其他的

3、，其他的 所有图都称为所有图都称为非平凡图非平凡图. 定义若若图图G中的边均为中的边均为有序有序偶对偶对,称称G为为有向有向),(jivv边边 为为无向边无向边，称，称e连接连接 和和 ，顶点，顶点 和和 称称图图. 称边称边为为有向边有向边或或弧弧,称称),(jivve 是从是从),(jivve iv连接连接jv，称，称 为为e的的尾尾，称，称 为为e的的头头. ivjv 若图若图G中的边均为中的边均为无序无序偶对偶对 ，称，称G为为无向图无向图.称称jivv为为e的的端点端点. jivve ivjvivjv 既有无向边又有有向边的图称为既有无向边又有有向边的图称为混合图混合图. 常用术语常

4、用术语1) 边和它的两端点称为互相边和它的两端点称为互相关联关联.2)与同一条边关联的两个端点称与同一条边关联的两个端点称为为相邻相邻的顶点，与同一个顶点的顶点，与同一个顶点 点关联的两条边称为点关联的两条边称为相邻相邻的边的边. 3) 端点重合为一点的边称为端点重合为一点的边称为环环， 端点不相同的边称为端点不相同的边称为连杆连杆.4) 若一对顶点之间有两条以上的边联结，则这些边若一对顶点之间有两条以上的边联结，则这些边 称为称为重边重边5) 既没有既没有环也没有重边环也没有重边的图，称为的图，称为简单图简单图 常用术语常用术语6) 任意两顶点都相邻的简单图任意两顶点都相邻的简单图,称为称为

5、完全图完全图. 记为记为Kv. 7) 若若 ， ，且且X 中任意两顶点不中任意两顶点不YXGV)(YX ， 相邻，相邻，Y 中任意两顶点不相邻，则称为中任意两顶点不相邻，则称为二部图二部图或或 偶图偶图；若；若X中每一顶点皆与中每一顶点皆与Y 中一切顶点相邻中一切顶点相邻,称为称为完全二部图完全二部图或或完全偶图完全偶图,记为记为 (m=|X|,n=|Y|)nmK,8) 图图 叫做叫做星星.nK, 1:X1x2x3x:Y1y2y3y4y二部图二部图6K:X1x2x3x:Y1y2y3y4y4 , 1K4 , 3K2) 2) 赋权图与子图赋权图与子图 定义定义 若图若图 的每一条边的每一条边e 都

6、赋以都赋以)(),(GEGVG 一个实数一个实数w(e)，称，称w(e)为边为边e的的权权，G 连同边上的权连同边上的权称为称为赋权图赋权图. 定义定义 设设 和和 是两个图是两个图.),(EVG ),(EVG 1) 若若 ,称称 是是 的一个的一个子图子图,记记 EEVV,GG.GG 2) 若若 ， ，则称，则称 是是 的的生成子图生成子图.VV EE GG 3) 若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 VV VV 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 VG 为为 的的由由 导出的子图导出的子图，记为，记为 .GVVG4) 若若

7、 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点EE EEE 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的GGE 边导出的子图边导出的子图，记为，记为 . EG,321vvvG,6543eeeeG 3) 若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 VV VV 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 VG4) 若若 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点EE EEE 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的GGE 边导出的子图边导出的子图，记为

8、，记为 . EGGVVG 为为 的的由由 导出的子图导出的子图，记为，记为 .3) 3) 图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵:1) 对无向图对无向图 ，其邻接矩阵，其邻接矩阵 ，其中：，其中： G)(ijaA., 0, 1不相邻与若相邻与若jijiijvvvva54321543210010000100110110010100110vvvvvAvvvvv(以下均假设图为简单图以下均假设图为简单图).2) 对有向图对有向图 ,其邻接矩阵其邻接矩阵 ,其中：其中： )(ijaA),(EVG .),(, 0,),(, 1EvvEvvajijiij若若4321432101000010000011

9、10uuuuAuuuu其中：其中：3) 对有向赋权图对有向赋权图 , 其邻接矩阵其邻接矩阵 ,)(ijaA),(EVG .),(,0,),(,EvvjiwEvvwajiijjiijij若，为其权，且若43214321040608730uuuuAuuuu对于无向赋权图的邻接矩阵可类似定义对于无向赋权图的邻接矩阵可类似定义. 关联矩阵关联矩阵 1) 对无向图对无向图 ，其关联矩阵，其关联矩阵 ,),(EVG )(ijmM其中：其中：., 0, 1不关联与若相关联与若jijiijevevm54321543211000001000111100010100011vvvvvMeeeee2) 对有向图对有向

10、图 ，其关联矩阵，其关联矩阵 ,),(EVG )(ijmM., 0, 1, 1的头与尾不是若的头是若的尾是若jijijiijevevevm其中：其中：43215432111000101100001101101uuuuMeeeee4) 图的顶点度图的顶点度定义定义 1) 在无向图在无向图G中，与顶点中，与顶点v关联的边的数目关联的边的数目(环环算两次算两次),称为顶点称为顶点v的的度度或或次数次数，记为，记为d(v)或或 dG(v).称度为奇数的顶点为称度为奇数的顶点为奇点奇点，度为偶数的顶点为，度为偶数的顶点为偶点偶点.2) 在有向图中，从顶点在有向图中，从顶点v引出的边的数目称为顶点引出的边

11、的数目称为顶点 v的的出度出度，记为，记为d+(v)，从顶点，从顶点v引入的边的数目称为引入的边的数目称为 v的的入度入度，记为，记为d -(v). 称称d(v)= d+(v)+d -(v)为顶点为顶点v的的 度度或或次数次数定理定理.2)(Vvvd的个数为偶数的个数为偶数推论推论 任何图中奇点任何图中奇点4)(1vd1)(3ud2)(3ud3)(3ud5) 路和连通路和连通 定义定义1) 无向图无向图G的一条的一条途径途径（或（或通道通道或或链链）是指）是指一个有限非空序列一个有限非空序列 ，它的项交替，它的项交替kkveevevW2110 地为顶点和边，使得对地为顶点和边，使得对 ， 的端

12、点是的端点是 和和 ,ki 1ie1iviv称称W是从是从 到到 的一条的一条途径途径，或一条，或一条 途径途径. 整整0vkv),(0kvv数数k称为称为W的的长长. 顶点顶点 和和 分别称为的分别称为的起点起点和和终点终点 ,0vkv而而 称为称为W的的内部顶点内部顶点.121,kvvv 2) 若途径若途径W的的边互不相同但顶点可重复边互不相同但顶点可重复，则称，则称W为为迹迹或或简单链简单链. 3) 若途径若途径W的的顶点和边均互不相同顶点和边均互不相同，则称，则称W为为路路或或路径路径. 一条起点为一条起点为 ,终点为终点为 的路称为的路称为 路路0vkv),(0kvv记为记为).,(

13、0kvvP 定义定义 1) 途径途径 中由相继项构成子序列中由相继项构成子序列kkvevevW.110 称为途径称为途径W的的节节.jjiiivevev.11 2) 起点与终点重合的途径称为起点与终点重合的途径称为闭途径闭途径. 3) 起点与终点重合的的路称为起点与终点重合的的路称为圈圈(或或回路回路)，长长为为k的圈称为的圈称为k阶圈阶圈，记为，记为Ck. 4) 若在图若在图G中存在中存在(u,v)路，则称顶点路，则称顶点u和和v在图在图G中中连通连通. 5) 若在图若在图G中顶点中顶点u和和v是连通的，则顶点是连通的，则顶点u和和v之之之间的之间的距离距离d(u,v)是指图是指图G中中最短

14、最短(u,v)路的长路的长；若没；若没没有路连接没有路连接u和和v，则定义为无穷大，则定义为无穷大. 6) 图图G中中任意两点皆连通任意两点皆连通的图称为的图称为连通图连通图 7) 对于有向图对于有向图G，若，若 ，且，且 有有kkveevevW2110ie 类似地，可定义类似地，可定义有向迹有向迹，有向路有向路和和有向圈有向圈.头头 和尾和尾 ，则称，则称W为为有向途径有向途径.iv1iv 例例 在右图中：在右图中： 途径或链：途径或链： 迹或简单链：迹或简单链： 路或路径：路或路径： 圈或回路：圈或回路：wugyexeyfxcyvbwcxdvauguavdxcwuuavbwcxfyg2最短

15、路问题及算法最短路问题及算法 最短路问题是图论应用的基本问题，很多实际最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费问题，如线路的布设、运输安排、运输网络最小费用流等问题用流等问题,都可通过建立最短路问题模型来求解都可通过建立最短路问题模型来求解.最短路的定义最短路的定义最短路问题的两种方法：最短路问题的两种方法：Dijkstra和和Floyd算法算法 .1) 求赋权图中从给定点到其余顶点的最短求赋权图中从给定点到其余顶点的最短路路. .2) 求赋权图中任意两点间的最短路求赋权图中任意两点间的最短路. 2) 在赋权图在赋权图G中，从顶点中，从顶点u到顶点到

16、顶点v的具有最小权的具有最小权定义定义 1) 若若H是赋权图是赋权图G的一个子图，则称的一个子图，则称H的各的各边的权和边的权和 为为H的的权权. 类似地，若类似地，若)()()(HEeewHw称为路称为路P的的权权若若P(u,v)是赋权图是赋权图G中从中从u到到v的路的路,称称)()()(PEeewPw 的路的路P*(u,v)，称为，称为u到到v的的最短路最短路 3) 把赋权图把赋权图G中一条路的权称为它的中一条路的权称为它的长长，把，把(u,v)路的最小权称为路的最小权称为u和和v之间的之间的距离距离，并记作，并记作 d(u,v). 1) 赋权图中从给定点到其余顶点的最短路赋权图中从给定点

17、到其余顶点的最短路 假设假设G为赋权有向图或无向图，为赋权有向图或无向图，G边上的权均非边上的权均非负负若若 ，则规定，则规定 )(),(GEvu.),(vuw最短路是一条路，且最短路的任一节也是最短路最短路是一条路，且最短路的任一节也是最短路求下面赋权图中顶点求下面赋权图中顶点u0到其余顶点的最短路到其余顶点的最短路Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把

18、达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj01Su 10 ,min)(1ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并

19、把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj01Su 1)(1ul02Su Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(

20、vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul03Su )(3ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(m

21、invliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul04Su )(3ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvli

22、Sv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul05Su )(3ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvl

23、iSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul)(5ul06Su )(3ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)

24、(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul)(5ul4)(6ul07Su Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小

25、值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个

26、最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul)()(min10ulvlSv8)(7ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(min

27、vuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2).,101uuS 1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul12Su 21 , 2min)(2ul2)(2ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对

28、每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2).,101uuS 1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul12Su 21 , 2min)(2ul2)(2ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)

29、(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2).定义 根据顶点根据顶点v的标号的标号l(v)的取值途径，使的取值途径，使 到到v0u的最短路中与的最短路中与v相邻的前一个顶点相邻的前一个顶点w，称为，称为v的的先驱先驱点点，记为，记为z(v), 即即z(v)=w.先驱点可用于追踪最

30、短路径先驱点可用于追踪最短路径. 例例5的标号过程也的标号过程也可按如下方式进行：可按如下方式进行： 首先写出左图带权邻接矩阵首先写出左图带权邻接矩阵024782063446046340357630135102273201847210W因因G是无向图，故是无向图，故W是对称阵是对称阵1u0u6u7u2u4u3u5uDijkstra算法：算法：求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路设设G为赋权有向图或无向图，为赋权有向图或无向图，G边上的权均均非负边上的权均均非负. 对每个顶点，定义两个标记（对每个顶点，定义两个标记（l(v)，z(v)），其中），其中: l(v) ：表从

31、顶点表从顶点u0到到v的一条路的权的一条路的权 z(v) ：v的先驱点，用以确定最短路的路线的先驱点，用以确定最短路的路线.l(v)为从顶点为从顶点u0到到v的最短路的权的最短路的权算法的过程就是在每一步改进这两个标记，使最终算法的过程就是在每一步改进这两个标记，使最终S：具有永久标号的顶点集：具有永久标号的顶点集.输入输入: G的带权邻接矩阵的带权邻接矩阵 w(u,v)备用备用-将求最短路与最短路径结合起来将求最短路与最短路径结合起来:算法步骤：算法步骤：l(v)u0vl(u)uw(u,v)首先写出带权邻接矩阵首先写出带权邻接矩阵0247820634460463403576301351022

32、73201847210W例例 求下图从顶点求下图从顶点u0到到其余顶点的最短路其余顶点的最短路因因G是无向图，故是无向图，故W是对称阵是对称阵1u0u6u7u2u4u3u5u见见Matlab程序程序-Dijkstra.doc2) 求赋权图中任意两顶点间的最短路求赋权图中任意两顶点间的最短路 算法的基本思想算法的基本思想 （I）求距离矩阵的方法）求距离矩阵的方法.（II）求路径矩阵的方法）求路径矩阵的方法.（III）查找最短路路径的方法）查找最短路路径的方法. Floyd算法：求任意两顶点间的最短路算法：求任意两顶点间的最短路. 举例说明举例说明算法的基本思想算法的基本思想（I）求距离矩阵的方法

33、）求距离矩阵的方法.（II）求路径矩阵的方法）求路径矩阵的方法.在建立距离矩阵的同时可建立路径矩阵在建立距离矩阵的同时可建立路径矩阵R ivjv（III）查找最短路路径的方法）查找最短路路径的方法.然后用同样的方法再分头查找若：然后用同样的方法再分头查找若：1av2av3avkav1bv2bvmbv（IV）Floyd算法：求任意两顶点间的最短路算法：求任意两顶点间的最短路.例例 求下图中加权图的任意两点间的距离与路径求下图中加权图的任意两点间的距离与路径. ,053142503330212044401210 )0(D,654321654321654321654321654321654321 )

34、0(R,053142503330212044401210 )0(D,min) 1() 1() 1()(kkjkikkijkijdddd插入点插入点 v1，得：得：,053132503330212043401210)1(D,654311654321654321654321154321654321 )1(R矩阵中带矩阵中带“=”的项为经迭代比较以后有变化的元素的项为经迭代比较以后有变化的元素.,min) 1() 1() 1()(kkjkikkijkijdddd插入点插入点 v2，得：得：,053132503330212043401210)1(D矩阵中带矩阵中带“=”的项为经迭代比较以后有变化的元素

35、的项为经迭代比较以后有变化的元素.,05313250333021204534012510)2(D,654311654321654321654322154321654221 )2(R,min) 1() 1() 1()(kkjkikkijkijdddd,053132503330267120453640127510)3(D,654311654321654333654322153321653221 )3(R插入点插入点 v3，得：得：,05313250333021204534012510)2(D,min) 1() 1() 1()(kkjkikkijkijdddd,0531325033302671204

36、53640127510)3(D插入点插入点 v4，得：得：,05313250359103302671520453964012107510)4(D,654311654444654333644322143321643221 )4(R,)4()5(DD插入点插入点 v5，得：得：,)4()5(RR,min) 1() 1() 1()(kkjkikkijkijdddd插入点插入点 v6，得：得：,05313250359103302671520453964012107510)5(D,053132503587330265152043386401275310)6(D.654311654466654336644

37、326163321666621 )6(R,053132503587330265152043386401275310)6(D.654311654466654336644326163321666621 )6(R8)6(52d8)6(52d故从故从v5到到v2的最短路为的最短路为8 6)6(52R由由v6向向v5追溯追溯: . 6)6(56R由由v6向向v2追溯追溯: , 1)6(62R. 2)6(12R所以从到的最短路径为：所以从到的最短路径为： .2165vvvv见见Matlab程序程序-Floyd.doc3最小生成树及算法最小生成树及算法1v1) 树的定义与树的特征树的定义与树的特征定义定义

38、连通且不含圈的无向图连通且不含圈的无向图称为称为树树常用常用T表示表示. 树中的边称为树中的边称为树枝树枝. 树中度为树中度为1的顶点称为的顶点称为树叶树叶.孤立顶点称为孤立顶点称为平凡树平凡树.2v3v4v5v平凡树平凡树定理定理2 设设G是具有是具有n个顶点的图，则下述命题等价：个顶点的图，则下述命题等价：1) G是树（是树（ G无圈且连通）；无圈且连通）；2) G无圈，且有无圈，且有n-1条边；条边；3) G连通，且有连通，且有n-1条边；条边；4) G无圈，但添加任一条新边恰好产生一个圈无圈，但添加任一条新边恰好产生一个圈; 5) G连通，且删去一条边就不连通了（即连通，且删去一条边就

39、不连通了（即G为为最最最小连通图最小连通图）；）；6) G中任意两顶点间有唯一一条路中任意两顶点间有唯一一条路.2）图的生成树）图的生成树定义定义 若若T是是包含图包含图G的全部顶点的全部顶点的子图的子图,它又是树它又是树,则称则称T是是G的的生成树生成树. 图图G中不在生成树的边叫做中不在生成树的边叫做弦弦.定理定理3 图图G=(V,E)有生成树的充要条件是图有生成树的充要条件是图G是连是连 通的通的.证明证明 必要性必要性是显然的是显然的.（II）找图中生成树的方法）找图中生成树的方法可分为两种：避圈法和破圈法可分为两种：避圈法和破圈法 A 避圈法避圈法 : 深探法和广探法深探法和广探法

40、B 破圈法破圈法 A 避圈法避圈法 定理定理3的充分性的证明提供了一种构造图的生的充分性的证明提供了一种构造图的生成树的方法成树的方法. 这种方法就是在已给的图这种方法就是在已给的图G中，每步选出一中，每步选出一条边使它与已选边不构成圈，直到选够条边使它与已选边不构成圈，直到选够n-1条边为条边为止止. 这种方法可称为这种方法可称为“避圈法避圈法”或或“加边法加边法” 在避圈法中，按照边的选法不同，找图中生在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：成树的方法可分为两种：深探法深探法和和广探法广探法.a) 深探法深探法 若这样的边的另一端均已有标号，就退到标号为若这样的边的另一

41、端均已有标号，就退到标号为步骤如下：步骤如下：i) 在点集在点集V中任取一点中任取一点u,ii) 若某点若某点v已得标号，检已得标号，检端是否均已标号端是否均已标号. 若有边若有边vw之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给以标号给以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边vw.令令例例用深探法求出下图用深探法求出下图10的一棵生成树的一棵生成树 图1001234567891011121313a) 深探法深探法图10012345678

42、9101112步骤如下：步骤如下： 若这样的边的另一端均已有标号，就退到标号为若这样的边的另一端均已有标号，就退到标号为i) 在点集在点集V中任取一点中任取一点u,ii) 若某点若某点v已得标号，检已得标号，检端是否均已标号端是否均已标号. 若有边若有边vw之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给给u以标号以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边vw.令令例例用深探法求出下图用深探法求出下图10的一棵生成树的一棵生成树 3b)广探法

43、广探法步骤如下：步骤如下：i) 在点集在点集V中任取一点中任取一点u,ii) 令所有标号令所有标号i的点集为的点集为是否均已标号是否均已标号. 对所有未标对所有未标号之点均标以号之点均标以i+1,记下这些记下这些 iii) 对标号对标号i+1的点重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.Vi,检查检查Vi,VVi中的边端点中的边端点边边.例例用广探法求出下图用广探法求出下图10的一棵生成树的一棵生成树 图101012213212234标号为止标号为止.图103b)广探法广探法步骤如下：步骤如下：i) 在点集在点集V中任取一点中任取一点u,ii) 令所有

44、标号令所有标号i的点集为的点集为是否均已标号是否均已标号. 对所有未标对所有未标号之点均标以号之点均标以i+1,记下这些记下这些 iii) 对标号对标号i+1的点重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.Vi,检查检查Vi,VVi中的边端点中的边端点边边.例例用广探法求出下图用广探法求出下图10的一棵生成树的一棵生成树 图101012213212234标号为止标号为止.显然图显然图10的生成树的生成树不唯一不唯一.B 破圈法 相对于避圈法，还有一种求生成树的方法叫做相对于避圈法，还有一种求生成树的方法叫做“破圈法破圈法”. 这种方法就是在图这种方法就是

45、在图G中任取一个圈，中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤任意舍弃一条边，将这个圈破掉，重复这个步骤直到图直到图G中没有圈为止中没有圈为止.例例 用破圈法求出用破圈法求出下图的一棵生成树下图的一棵生成树.B 破圈法例例 用破圈法求出下图的另一棵生成树用破圈法求出下图的另一棵生成树.不难发现，图不难发现，图的生成树不是的生成树不是唯一的唯一的 .3) 最小生成树与算法最小生成树与算法 介绍最小树的两种算法：介绍最小树的两种算法：Kruskal算法算法（或（或避圈法避圈法）和）和破圈法破圈法. A Kruskal算法（或避圈法）算法（或避圈法）步骤如下：步骤如下： 1) 选择边选

46、择边e1，使得，使得w(e1)尽可能小；尽可能小；2) 若已选定边若已选定边 ，则从，则从ieee,.,21,.,21ieeeE中选取中选取 ，使得，使得:1iei) 为无圈图，为无圈图，,.,121ieeeG ii) 是满足是满足i)的尽可能小的权，的尽可能小的权，)(1iew 3) 当第当第2)步不能继续执行时，则停止步不能继续执行时，则停止.定理定理4 由由Kruskal算法构作的任何生成树算法构作的任何生成树,.,121*eeeGT都是最小树都是最小树.,876432eeeeee例例10用用Kruskal算法求下图的最小树算法求下图的最小树.在左图中在左图中 权值权值,.,821eee

47、最小的边有最小的边有 任取一条任取一条 ,51ee,1e 在在 中选取权值中选取权值,.,832eee,5e最小的边最小的边 中权值最小边有中权值最小边有 , 从中选从中选：73,ee;3e任取一条边任取一条边,87642eeeee会与已选边构成圈会与已选边构成圈,故停止故停止,得得中选取在中选取中选取在中选取,7e,42ee在 中选取中选取 . 但但 与与 都都,86ee84,ee4e8eB破圈法算法算法2 步骤如下：步骤如下： 1) 从图从图G中任选一棵树中任选一棵树T1.2) 加上一条弦加上一条弦e1，T1+e1中中 立即生成一个圈立即生成一个圈. 去掉此去掉此 圈中最大权边，得到新圈中最大权边，得到新树树T2,以以T2代代T1,重复重复2)再再检查剩余的弦，直到全检查剩余的弦，直到全部弦检查完毕为止部弦检查完毕为止.例例11用破圈法求下图的最小树用破圈法求下图的最小树.先求出上图的一棵生成树先求出上图的一棵生成树. 加以弦加以弦 e2,得到的圈得到的圈v1v3v2v1,去掉最大的权边去掉最大的权边e2,得到一棵新得到一棵新树仍是原来的树；树仍是原来的树；2e 再加上弦再加上弦e7，得到圈