1、1第三部第三部分分 图论图论本部分主要内容本部分主要内容l 图的基本概念图的基本概念l 树树l 几种特殊的图几种特殊的图引言引言 图论最早起源于一些数字游戏的难题研究图论的最早论文是1736年瑞士数学家欧拉（Leonhard Euler）所写，从而使欧拉成为图论的创始人。图论研究图论研究图的逻辑结构与性质图的逻辑结构与性质.引引 言言 图论是组合数学的一个分支，图论是组合数学的一个分支，研究集合上的二研究集合上的二元关系的工具，是建立数学模型的一个重要手段元关系的工具，是建立数学模型的一个重要手段。在通信编码、资源配置、在通信编码、资源配置、GPSGPS路径规划、任务分配、路径规划、任务分配、
2、算法设计等算法设计等各方面都取得了丰硕的成果。计算机的各方面都取得了丰硕的成果。计算机的迅速发展，使得图论成为数学领域里发展最快的分迅速发展，使得图论成为数学领域里发展最快的分支之一。支之一。引引 言言哥尼斯堡七桥问题哥尼斯堡七桥问题 18世纪东普鲁士的首府世纪东普鲁士的首府哥尼斯堡（Konigsberg）城（现名加里宁格勒,属俄罗斯）的居民有郊游的习惯，在城郊的普雷格尔（Pregel）河畔，河中有两个小岛，七座桥将两个小岛和河岸连接起来，如图所示，问一个人能否不重复地走遍七座小桥，最后回到出发地点？（欧拉回路问题）（欧拉回路问题）四色问题四色问题1852年毕业于伦敦大学的弗年毕业于伦敦大学的
3、弗南西斯南西斯格思里（其弟弟是德格思里（其弟弟是德摩根的学生）发现了一种有摩根的学生）发现了一种有趣的现象：趣的现象：“看来，每幅地看来，每幅地图都可以用四种颜色着色，图都可以用四种颜色着色，使得有共同边界的国家都被使得有共同边界的国家都被着上不同的颜色。着上不同的颜色。”这个现这个现象能不能从数学上加以严格象能不能从数学上加以严格证明呢？证明呢？1890年，希伍德证明了任何平面图都是年，希伍德证明了任何平面图都是5-可着色的。可着色的。1976年，阿佩尔和黑肯（美）运用反证年，阿佩尔和黑肯（美）运用反证法，用计算机分析了存在的反例的可能法，用计算机分析了存在的反例的可能的的2000种情况，都
4、未导致反例，证明之。种情况，都未导致反例，证明之。（平面图着色问题）（平面图着色问题）四色问题四色问题Hamilton问题问题 1856年，英国数学家年，英国数学家Hamilton设计了一个名为周游世设计了一个名为周游世界的游戏：他用一个正十二面体的二十个端点表示世界上的界的游戏：他用一个正十二面体的二十个端点表示世界上的二十座大城市（见图），提出的问题是要求游戏者找一条沿二十座大城市（见图），提出的问题是要求游戏者找一条沿着十二面体的棱通过每个端点恰好一次的行走路线。着十二面体的棱通过每个端点恰好一次的行走路线。此路线称为：此路线称为：哈密尔顿回路哈密尔顿回路，而此图称为：而此图称为：哈密尔
5、顿图哈密尔顿图。8第第9 9章章 图的基本概念图的基本概念主要内容主要内容l 图图l 通路与回路通路与回路l 图的连通性图的连通性l 图的矩阵表示图的矩阵表示预备知识预备知识l 普通集合普通集合元素是相异的元素是相异的a,b,c,dl 多重集合多重集合元素可以重复出现的集合元素可以重复出现的集合a,a,a,b,b,c,dl 笛卡儿积笛卡儿积A B=|x A y B.（当（当x y时）时）l 无序无序积积A B=(x,y)|x A y B (x,y)=(y,x)9.1 图图定义定义9.1 无向图无向图G=,其中其中 (undirected Graph,Vertex,Edge)(1)V为非空有穷集
6、为非空有穷集,称为称为顶点集顶点集，其元素称为，其元素称为顶点顶点(2)E为为无无序积序积V V 的的多重多重有穷有穷集集（元素可以重复出现的集元素可以重复出现的集合合）,称为称为边集边集,其元素称为其元素称为无向边无向边,简称简称边边例例 无向图无向图G=,其中其中 V=v1,v2,v3,v4,v5,E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)10有向图有向图定义定义9.2 有向图有向图D=,其中其中 (Directed graph)(1)V 为非空有穷集为非空有穷集,称为称为顶点集顶点集，其元素称为，其元素称为顶点顶点(
7、2)E为为V V 的多重有穷集的多重有穷集,称为称为边集边集,其元素称为其元素称为有向边有向边,简简称称边边例例 有向图有向图D=,其中其中V=a,b,c,dE=,注意：图的集合表示与图形表示之间的对应注意：图的集合表示与图形表示之间的对应11相关概念相关概念1.无向图和有向图通称图无向图和有向图通称图.记顶点集记顶点集V(G),边集边集E(G).2.图的阶图的阶,n阶图阶图.-顶点数称作图的阶数（顶点数称作图的阶数（3,4,5阶）阶）3.n 阶零图阶零图Nn,平凡图平凡图N1.一条边也没有的图为零图（一条边也没有的图为零图（3阶零图）阶零图）。一阶零图称为平凡图一阶零图称为平凡图 。4.空图
8、空图.顶点集为空集的图为空图顶点集为空集的图为空图5.标定图与非标定图标定图与非标定图.每个顶点和边有标号（符号）的图称为标定图，否则非标定图每个顶点和边有标号（符号）的图称为标定图，否则非标定图。6.有向图的基图有向图的基图.将有向图的各条边改成无向边后所得到的无向图将有向图的各条边改成无向边后所得到的无向图7.无向图中边与顶点的关联及关联次数无向图中边与顶点的关联及关联次数,顶点与顶点、边与边的相顶点与顶点、边与边的相邻关系邻关系.ek=（vi，vj）vi，vj为为ek的端点的端点 若若 vi vj，则则 ek 与与 vi（vj）的关联次数为的关联次数为1.若若 vi=vj，则则 ek 与
9、与 vi的关联次数为的关联次数为2，ek 为环为环.若若 vi 不和不和 ek 关联，则关联，则ek 与与 vi 的关联次数为的关联次数为0.若两个顶点之间有一条边连接，则这两个顶点相若两个顶点之间有一条边连接，则这两个顶点相 邻邻 若两条边至少有一个公共端点，则称这两条边相若两条边至少有一个公共端点，则称这两条边相 邻邻8.有向图中边与顶点的关联有向图中边与顶点的关联,顶点与顶点、边与边的相邻关系顶点与顶点、边与边的相邻关系.ek=vi，vj为为ek的端点的端点,vi 为为ek 的始点，的始点，vj为终点为终点 若若 vi vj，则则 ek 与与 vi（vj）的关联的关联 若若 vi=vj，
10、则则 ek 为环为环.若两个顶点之间有一条有向边若两个顶点之间有一条有向边，则称这两个顶点相邻则称这两个顶点相邻 若两条边中一条边终点是另一条边的始点，则这两条边相邻若两条边中一条边终点是另一条边的始点，则这两条边相邻 9.环环,孤立点孤立点.ek=（vi，vj），），vi=vj，ek为环为环没有关联的顶点称为孤立点没有关联的顶点称为孤立点15多重图与简单图多重图与简单图定义定义9.3 无向图中关联同一对顶点的无向图中关联同一对顶点的2条和条和2条以上的边称为条以上的边称为平行边平行边.有向图中有向图中2条和条和2条以上始点、终点相同的边称为条以上始点、终点相同的边称为平行边平行边.平行边的条
11、数称为平行边的条数称为重数重数.含平行边的图称为含平行边的图称为多重图多重图,不含平行边和环的图称为不含平行边和环的图称为简单图简单图.e5和e6是平行边 e2和e3是，e6和e7不是平行边定义定义9.4 设设G=为无向图为无向图,v V,称称v作为边的端点的次作为边的端点的次数之和为数之和为v的的度数度数,简称简称度度,记作记作d(v).设设D=为有向图为有向图,v V,称称v作为边的始点的次数之和作为边的始点的次数之和为为v的的出度出度,记作记作d+(v);称称v作为边的终点的次数之和为作为边的终点的次数之和为v的的入入度度,记作记作d(v);称称d+(v)+d(v)为为v的的度数度数,记
12、作记作d(v).注：无向图中，顶点注：无向图中，顶点v上的环以上的环以v作作2次端点次端点有向图中，顶点有向图中，顶点v上的环以上的环以v作一次始点和一次终点，共作作一次始点和一次终点，共作2次端点次端点17 顶顶点的度数点的度数设设G=为无向图为无向图,G的的最大度最大度(G)=maxd(v)|v V G的的最小度最小度 (G)=mind(v)|v V 设设D=为有向图为有向图,D的的最大度最大度(D)=maxd(v)|v V D的的最小度最小度 (D)=mind(v)|v V D的的最大出度最大出度+(D)=maxd+(v)|v V D的的最小出度最小出度 +(D)=mind+(v)|v
13、V D的的最大入度最大入度 (D)=maxd(v)|v V D的的最小入度最小入度 (D)=mind(v)|v V 悬挂顶点悬挂顶点:度数为度数为1的顶点的顶点,悬挂边悬挂边:与悬挂顶点关联的边与悬挂顶点关联的边.偶度偶度(奇度奇度)顶点顶点:度数为偶数度数为偶数(奇数奇数)的顶点的顶点18实例实例d(v1)=4,d(v2)=4,d(v3)=2,d(v4)=1,d(v5)=3.=4,=1.v4是悬挂点是悬挂点,e7是悬挂边是悬挂边.d+(a)=4,d(a)=1,d(a)=5,d+(b)=0,d(b)=3,d(b)=3,d+(c)=2,d(c)=1,d(c)=3,d+(d)=1,d(d)=2,d
14、(d)=3,+=4,+=0,=3,=1,=5,=3.19握手定理：有握手定理：有n个人握手个人握手（顶点数），（顶点数），每人握手每人握手x次次(度数度数)，握，握手总次数为手总次数为m（边数），（边数），必有必有m=nx/2。定理定理9.1 在任何无向图中在任何无向图中,所有顶点的度数之和等于边数的所有顶点的度数之和等于边数的2倍倍.证证:G中每条边中每条边(包括环包括环)均有两个端点，均有两个端点，所以在计算所以在计算G中各顶点度数之和时，中各顶点度数之和时，每条边均提供每条边均提供2度，度，m 条边共提供条边共提供 2m 度度.握手定理握手定理定理定理9.2 在任何有向图中，所有顶点的度
15、数之和等于边数的在任何有向图中，所有顶点的度数之和等于边数的2倍倍;所有顶点的入度之和等于所有顶点的出度之和所有顶点的入度之和等于所有顶点的出度之和,都等于边数都等于边数.推论推论 任何图任何图(无向或有向无向或有向)中，奇度顶点的个数是偶数中，奇度顶点的个数是偶数.证证 由握手定理由握手定理,所有顶点的度数之和是偶数所有顶点的度数之和是偶数,而偶度顶点的而偶度顶点的度数之和是偶数度数之和是偶数,故奇度顶点的度数之和也是偶数故奇度顶点的度数之和也是偶数.所以奇所以奇度顶点的个数必是偶数度顶点的个数必是偶数21例例1 无向图无向图G有有16条边，条边，3个个4度顶点，度顶点，4个个3度顶点，其余
16、度顶点，其余均为均为2度顶点度，问度顶点度，问G的阶数的阶数n为几？为几？(即几个顶点？即几个顶点？)解解 本题的关键是应用握手定理本题的关键是应用握手定理.设除设除3度与度与4度顶点外，还有度顶点外，还有x个顶点个顶点,由握手定理由握手定理,16 2=32=3 4+4 3+2x解得解得 x=4,阶数阶数 n=4+4+3=11.握手定理应用握手定理应用定理定理9.3 设设G为任意为任意n阶阶无向简单图无向简单图，则最大度，则最大度(G)n 1图的同构图的同构定义定义9.5 设设G1=,G2=为两个无向图为两个无向图(两个有向两个有向图图)，若存在双射函数，若存在双射函数f:V1V2,使得使得
17、vi,vj V1,(vi,vj)E1 当且仅当当且仅当(f(vi),f(vj)E2 （E1 当且仅当当且仅当 E2)并且并且,(vi,vj)（）与与(f(vi),f(vj)（）的重数相的重数相同，则称同，则称G1与与G2是是同构同构的，记作的，记作G1 G2.例例 23图同构的实例图同构的实例 (1)(2)(3)(4)(1)与与(2),(3)与与(4),(5)与与(6)均不同构均不同构.(5)(6)说明说明:1.图的同构关系具有自反性、对称性和传递性图的同构关系具有自反性、对称性和传递性.2.判断两个图同构是个难题判断两个图同构是个难题图同构的实例图同构的实例所有所有4阶阶3条边非同构的简单无
18、向图条边非同构的简单无向图24所有所有3阶阶2条边非同构的简单有向图条边非同构的简单有向图补图补图与自补图与自补图定义定义9.6 设设G=为为n阶无向简单图，令阶无向简单图，令 =(u,v)|u V v V u v(u,v)E,称称 =为为G的的补图补图 若若G 则称则称G是是自补图自补图 EEGG例例 (b)与与(c)互为补图，互为补图，(a)是自补图是自补图26完全图与竞赛图完全图与竞赛图定义定义9.7 (1)n(n 1)阶阶无向完全图无向完全图每个顶点与其余顶点均相邻的无每个顶点与其余顶点均相邻的无向简单图，记作向简单图，记作 Kn.简单性质简单性质:边数边数m=n(n-1)/2,最大度
19、数最大度数=最小度数最小度数=n-1(2)n(n 1)阶阶有向完全图有向完全图每对顶点之间均有两条每对顶点之间均有两条方向相反的有向边的有向简单图方向相反的有向边的有向简单图.简单性质：简单性质：m=n(n-1),=2(n-1)+=+=n-1(3)n(n 1)阶阶竞赛图竞赛图基图为基图为Kn的的有向简单图有向简单图.简单性质：简单性质：m=n(n-1)/2,=n-1 正则图正则图定义定义9.8 k-正则图正则图=k 的无向简单图的无向简单图简单性质：边数简单性质：边数m=kn/2,当当k是奇数时是奇数时,n必为偶数必为偶数.例例 n阶无向完全图阶无向完全图Kn是是(n 1)-正则图，正则图，彼
20、得松图彼得松图是是3-正则正则图图 子图子图定义定义9.9 设两个图设两个图G=,G =（同为无向图或（同为无向图或同为有向图）同为有向图）,若若V V且且EE，则称，则称G 是是G的的子图子图，G为为G 母图母图，记作，记作G G.又若又若V V或或E E，则称，则称G 为为G的的真真子图子图.若若G G且且V=V，则称，则称G 为为G的的生成子图生成子图 设设V1 V且且V1,称以称以V1为顶点集为顶点集,以以G中两个端点都在中两个端点都在V1中的边组成边集的图为中的边组成边集的图为G中中V1的的导出子图导出子图,记作记作GV1.设设E1 E且且E1,称以称以E1为边集为边集,以以E1中边
21、关联的顶点为顶点中边关联的顶点为顶点集的图为集的图为G中中E1的的导出子图导出子图,记作记作GE1例例 G Ga,b,c Ge1,e329定义定义9.10 设设G=为无向图为无向图 (1)设设e E，用，用G e表示从表示从G中去掉边中去掉边e，称为，称为删除边删除边e又又设设E E，用，用 G E 表示从表示从G中删除中删除E 中的所有边，称为中的所有边，称为删除删除E 删除删除,收缩与加新边收缩与加新边(2)设设v V，用，用G v表示从表示从G中去掉中去掉v及所关联的所有边，称为及所关联的所有边，称为删除顶点删除顶点v又设又设V V，用，用G V 表示从表示从G中删除中删除V 中所中所有
22、的顶点，称为有的顶点，称为删除删除V(3)设设e=(u,v)E，用，用Ge表示从表示从G中删除中删除e后，将后，将e的两个端的两个端点点u,v用一个新的顶点用一个新的顶点w（可以用（可以用u或或v充当充当w）代替，并使）代替，并使w关联除关联除e以外以外u,v关联的所有边，称为关联的所有边，称为收缩边收缩边e (4)设设u,v V（u,v可能相邻，也可能不相邻），用可能相邻，也可能不相邻），用G(u,v)（或（或G+(u,v)）表示在）表示在u,v之间加一条边之间加一条边(u,v)，称，称为为加新边加新边 在收缩边和加新边过程中可能产生环和平行边在收缩边和加新边过程中可能产生环和平行边 329
23、.2 通路与回路通路与回路定义定义9.11 设图设图G=(无向或有向的无向或有向的),G中顶点与边的交中顶点与边的交替序列替序列 =v0e1v1e2elvl，其中其中vi 1,vi 是是 ei 的端点的端点(始点和终始点和终点点),1 i l,则称则称 为为v0到到vl的的通路通路.v0,vl分别称作分别称作 的的始点始点和和终终点点.中的边数中的边数l称作它的称作它的长度长度.又又若若 v0=vl,则称则称 为为回路回路.若所有的边各异若所有的边各异,则称则称 为为简单通路简单通路.又若又若v0=vl,则称则称 为为简单回路简单回路.若若 中所有顶点各异中所有顶点各异(除除v0和和vl可能相
24、同外可能相同外)且所有边也各异且所有边也各异,则则称称 为为初级通路初级通路或或路径路径.若又有若又有v0=vl,则称则称 为为初级回路初级回路或或圈圈.长度为奇数的圈称为长度为奇数的圈称为奇圈奇圈,长度为偶数的圈称为长度为偶数的圈称为偶圈偶圈.若若 中有边重复出现中有边重复出现,则则 称为称为复杂通路复杂通路.若又有若又有v0=vl,则称则称 为为复杂回路复杂回路.33通路与回路通路与回路定理定理9.4 在在n 阶图阶图G中，若从顶点中，若从顶点u 到到v（u v）存在通路，则）存在通路，则从从u 到到 v 存在长度小于或等于存在长度小于或等于n 1 的通路的通路.推论推论 在在 n 阶图阶
25、图G中，若从顶点中，若从顶点u 到到 v（u v）存在通路，则）存在通路，则从从u 到到v 存在长度小于或等于存在长度小于或等于n 1的初级通路（路径）的初级通路（路径）（点边各异）（点边各异）.定理定理9.5 在在n 阶图阶图G中，若存在中，若存在 v 到自身的回路，到自身的回路，则一定存在则一定存在v 到自身长度小于或等于到自身长度小于或等于 n 的回路的回路.推论推论 在在n 阶图阶图G中，若存在中，若存在 v 到自身的简单到自身的简单回路回路（边各异）边各异），则一定存在则一定存在v 到自身的长度小于到自身的长度小于或等于或等于n 的初级回路的初级回路（点边各异）（点边各异）.34同构
26、意义下和定义意义下的圈同构意义下和定义意义下的圈例例2 无向完全图无向完全图Kn（n 3）中有几种非同构的圈）中有几种非同构的圈？（初级初级回路（点边各异的通路）回路（点边各异的通路）解解 长度相同的圈都是同构的长度相同的圈都是同构的.易知易知Kn(n 3)中含长度中含长度3,4,n的圈，共有的圈，共有n 2种非同构的圈种非同构的圈长度相同的圈都是同构的长度相同的圈都是同构的,因此在因此在同构意义下同构意义下给定长度的圈给定长度的圈只有一个只有一个.在标定图中在标定图中,圈表示成顶点和边的标记序列圈表示成顶点和边的标记序列.如果只要两个圈如果只要两个圈的标记序列不同的标记序列不同,称这两个圈在
27、称这两个圈在定义意义下定义意义下不同不同.例例3 无向完全图无向完全图K3的顶点依次标定为的顶点依次标定为a,b,c在定义意义下在定义意义下K3中有多少个不同的长度为中有多少个不同的长度为3的圈？的圈？解解 在定义意义下在定义意义下,不同起点不同起点(终点终点)的圈是不同的的圈是不同的,顶点间排顶点间排列顺序不同的圈也是不同的列顺序不同的圈也是不同的,因而因而K3中有中有3!=6个不同的长为个不同的长为3的圈：的圈：abca，acba，bacb，bcab，cabc，cbac35带权图与最短路径带权图与最短路径定义定义9.12 设图设图G=(无向图或有向图无向图或有向图),对对G的每一条边的每一
28、条边e,给定一个数给定一个数W(e),称作边称作边e的的权权.把这样的图称为把这样的图称为带权图带权图,记作记作G=.当当e=(u,v)()时时,把把W(e)记作记作W(u,v).设设P是是G中的一条通路中的一条通路,P中所有边的权之和称为中所有边的权之和称为P的的长度长度,记作记作W(P).类似地类似地,可定义回路可定义回路C的长度的长度W(C).设带权图设带权图G=(无向图或有向图无向图或有向图),其中每一条边其中每一条边e的的权权W(e)为非负实数为非负实数.u,v V,当当u和和v连通连通(u可达可达v)时时,称从称从u到到v长度最短的路径为从长度最短的路径为从u到到v的的最短路径最短
29、路径,称其长度为从称其长度为从u到到v的的距离距离,记作记作d(u,v).约定约定:d(u,u)=0;当当u和和v不连通不连通(u不可达不可达v)时时,d(u,v)=+.最短路问题是网络分析中的一个基本问题，它不仅可以直接应用于于解决最短路问题是网络分析中的一个基本问题，它不仅可以直接应用于于解决生产实际的许多问题，若管道铺设、线路安排、厂区布局等，而且经常被生产实际的许多问题，若管道铺设、线路安排、厂区布局等，而且经常被作为一个基本工具，用于解决其它的优化问题作为一个基本工具，用于解决其它的优化问题.37最短路问题最短路问题(迪杰斯特拉算法迪杰斯特拉算法)最短路问题最短路问题:给定带权图给定
30、带权图G=及顶点及顶点u和和v,其中每一条其中每一条边边e的权的权W(e)为非负实数为非负实数,求从求从u到到v的最短路径的最短路径.Dijkstra标号法标号法(求从求从s到其余各点的最短路径和距离到其余各点的最短路径和距离)Dijkstra算法思想为：从起点出发，逐步向外探寻最短路。算法思想为：从起点出发，逐步向外探寻最短路。把把图中顶点集合图中顶点集合V分成两组，第一组为已求出最短路径的顶点集分成两组，第一组为已求出最短路径的顶点集合合（用（用S表示，初始时表示，初始时S中只有一个源点中只有一个源点s，以后每求得一条最，以后每求得一条最短路径短路径,就将加入到集合就将加入到集合S中，直到
31、全部顶点都加入到中，直到全部顶点都加入到S中，算中，算法就结束了），法就结束了），第二组为其余未确定最短路径的顶点集合（第二组为其余未确定最短路径的顶点集合（用用U表示），按最短路径长度的递增次序依次把第二组的顶点表示），按最短路径长度的递增次序依次把第二组的顶点加入加入S中。中。在加入的过程中，总保持从源点在加入的过程中，总保持从源点s到到S中各顶点的最中各顶点的最短路径长度不大于从源点短路径长度不大于从源点s到到U中任何顶点的最短路径长度。中任何顶点的最短路径长度。此外，每个顶点对应一个距离，此外，每个顶点对应一个距离，S中的顶点的距离就是从中的顶点的距离就是从s到此到此顶点的最短路径长度
32、，顶点的最短路径长度，U中的顶点的距离，是从中的顶点的距离，是从s到此顶点只到此顶点只包括包括S中的顶点为中间顶点的当前最短路径长度。中的顶点为中间顶点的当前最短路径长度。步骤步骤（1）初始时，）初始时，S只包含源点只包含源点s，即，即Ss，s的距离为的距离为0。U包含包含除除s外的其他顶点，外的其他顶点，U中顶点中顶点u的距离为边上的权或的距离为边上的权或+。（2）从）从U中选取一个距离源点中选取一个距离源点s最近的顶点最近的顶点k，把，把k加入加入S中中（该选定的距离就是（该选定的距离就是s到到k的最短路径长度）。的最短路径长度）。（3）以）以k为新考虑的中间点，修改为新考虑的中间点，修改
33、U中各顶点的距离；若从中各顶点的距离；若从源点源点s到顶点到顶点u的距离（经过顶点的距离（经过顶点k）比原来距离（不经过）比原来距离（不经过顶点顶点k）短，则修改顶点）短，则修改顶点u的距离值，修改后的距离值为顶的距离值，修改后的距离值为顶点点k的距离加上边上的权。的距离加上边上的权。（4）重复步骤（）重复步骤（2）和（）和（3）直到所有顶点都包含在）直到所有顶点都包含在S中。中。http:/ V-s),i1,l(s)是永久标号是永久标号,其余标号均为临时标号其余标号均为临时标号,us2.for 与与u关联的临时标号的顶点关联的临时标号的顶点v 3.if l2(u)+W(u,v)l2(v)th
34、en 令令l(v)(u,l2(u)+W(u,v)4.计算计算l2(t)=min l2(v)|v V且有临时标号且有临时标号,l(t)改为永久标号改为永久标号5.if in then 令令ut,ii+1,转转2对每一个对每一个u,d(s,u)=l2(u),根据根据l1(v)回溯找到回溯找到s到到u的最短路径的最短路径.40实例实例例例9.5 一个总部和一个总部和6个工地个工地,求从总部到各工地的最求从总部到各工地的最短路径短路径.解解 12345671510364451726总部总部12345671510364451726 (s,0)(s,+)(s,+)(s,+)(s,+)(s,+)(s,+)4
35、112345671510364451726 (s,0)(1,15)(1,10)(s,+)(s,+)(s,+)(s,+)u=112345671510364451726 (s,0)(3,13)(1,10)(s,+)(3,14)(s,+)(s,+)u=342实例实例12345671510364451726 (s,0)(3,13)(1,10)(2,19)(3,14)(2,30)(s,+)u=212345671510364451726 (s,0)(3,13)(1,10)(5,18)(3,14)(2,30)(5,16)u=543实例实例12345671510364451726 (s,0)(3,13)(1,
36、10)(5,18)(3,14)(6,22)(5,16)u=612345671510364451726(s,0)(3,13)(1,10)(5,18)(3,14)(6,22)(5,16)u=444实例实例v1v3v2,d(v1,v2)=13 v1v3,d(v1,v3)=10v1v3v5v4,d(v1,v4)=18 v1v3v5,d(v1,v5)=14v1v3v5v6,d(v1,v6)=16 v1v3v5v6v7,d(v1,v7)=2212345671510364451726 (s,0)(3,13)(1,10)(5,18)(3,14)(6,22)(5,16)u=7459.3 图的连通性图的连通性定义
37、定义9.13 设无向图设无向图G=，若，若u,v V之间存在通路，则称之间存在通路，则称u,v是是连通的连通的，记作，记作uv.规定规定:v V,vv 若无向图若无向图G是平凡图或是平凡图或G中任何两个顶点都是连通的，则中任何两个顶点都是连通的，则称称G为为连通图连通图，否则称，否则称G为为非连通图非连通图是是V上的等价关系上的等价关系,具有自反性、对称性和传递性具有自反性、对称性和传递性定义定义9.14 设无向图设无向图G=，Vi是是V关于顶点之间连通关关于顶点之间连通关系的一个等价类，称导出子图系的一个等价类，称导出子图GVi为为G的一个的一个连通分支连通分支.G的的连通分支数连通分支数记
38、为记为p(G)46点割集与边割集点割集与边割集定义定义9.15 设无向图设无向图G=.若若V V使得使得p(G V )p(G),且且对于任意的对于任意的V V,均有均有p(G V)=p(G),则称则称V 是是G的的点割集点割集.若若V =v,则称则称v为为割点割点定义定义9.16 设无向图设无向图G=,若若E E使得使得p(G E )p(G),且且对于任意的对于任意的E E,均有均有p(G E)=p(G),则称则称E 是是G的的边割集边割集，简称为简称为割集割集.若若E =e,则称则称e为为割边割边或或桥桥例例3 v1,v4，v6是点割集，是点割集，v6是割点是割点.v2,v5不是不是e1,e
39、2，e1,e3,e5,e6，e8等等是边割集，是边割集，e8是桥是桥.而而e7,e9,e5,e6 不是不是.47点连通度与边连通度点连通度与边连通度定义定义9.17 G为连通为连通非完全图非完全图,称称 (G)=min|V|V 为点割集为点割集 为为G的的点连通度点连通度,简称简称连通度连通度.若若(G)k，则称，则称G为为 k-连通图连通图.规定规定 (Kn)=n 1,非连通图的连通度为非连通图的连通度为0.定义定义9.18 设设G为连通图为连通图,称称 (G)=min|E|E 为边割集为边割集为为G的的边连通度边连通度.若若(G)r，则，则称称G是是 r 边边-连通图连通图.规定非连通图的
40、边连通度为规定非连通图的边连通度为0.v1v2v3v4v5e1e2e3e4e5e6e7例例 =2,2-连通图连通图,也是也是1-连通连通.=2,2边边-连通图连通图,也是也是1边边-连通连通.48几点说明几点说明l n(n 1)阶无向完全图阶无向完全图每个顶点与其余顶点均相邻的无向简单图，每个顶点与其余顶点均相邻的无向简单图，记作记作 Kn.l (Kn)=(Kn)=n 1l G非连通，则非连通，则 =0l 若若G中有割点，则中有割点，则=1，若有桥，则，若有桥，则=1l 若若(G)=k,则则G是是1-连通图，连通图，2-连通图，连通图，k-连通图，但不是连通图，但不是(k+s)-连连通图，通图
41、，s 1l 若若(G)=r,则则G是是1边边-连通图，连通图，2边边-连通图，连通图，r边边-连通图，但不是连通图，但不是(r+s)-边连通图，边连通图，s 1定理定理9.6 (G)(G)(G)点连通度，边连通度，最小度数点连通度，边连通度，最小度数=2，=249有向图的连通性及分类有向图的连通性及分类定定义义9.19 设设D=为一个有向图为一个有向图,vi,vj V,若从若从vi到到vj存在存在通路通路,则称则称vi可达可达vj,记作记作vivj.规定规定vi vi.若若vivj且且vjvi，则称则称vi与与vj是是相互可达相互可达的的,记作记作vivj.规定规定vivi性质性质:具有自反性
42、具有自反性(vi vi)、传递性、传递性 具有自反性、对称性、传递性具有自反性、对称性、传递性 定义定义9.20 若有向图若有向图D=V,E)的基图是连通图的基图是连通图,则称则称D是是弱连通弱连通图图,简称为简称为连通图连通图.若若 vi,vj V,vivj与与vjvi至少有一个成立，至少有一个成立，则称则称 D是是单向连通图单向连通图.若若 vi,vj V,均有均有vivj,则称则称D是是强连强连通图通图 强连通强连通 单向连通单向连通 弱连通弱连通50有向图的连通性有向图的连通性定理定理9.7 有向图有向图D=是强连通图当且仅当是强连通图当且仅当D中存在经过每个中存在经过每个顶点至少一次
43、的回路顶点至少一次的回路证证 充分性显然充分性显然.证必要性证必要性.已知已知D强连通，强连通，设设V=v1,v2,vn,i为为vi到到vi+1的通路的通路(i=1,2,n 1),n为为vn到到v1的通路的通路.依次连接依次连接 1,2,n 1,n所得到的回路经过所得到的回路经过D中每个顶点至少一次中每个顶点至少一次定理定理9.8 有向图有向图D是单向连通图当且仅当是单向连通图当且仅当D中存在经过每个顶点中存在经过每个顶点至少一次的通路至少一次的通路扩大路径法扩大路径法设设G=为无向图为无向图,为为G中一条路径中一条路径.若此路径的两个端若此路径的两个端点都不与通路外的顶点相邻点都不与通路外的
44、顶点相邻,则称则称 是是极大路径极大路径.任取一条边任取一条边,如果它有一个端点与其他的顶点相邻如果它有一个端点与其他的顶点相邻,就将这条就将这条边延伸到这个顶点边延伸到这个顶点.继续这一过程继续这一过程,直至得到一条极大路径为直至得到一条极大路径为止止.称此种方法为称此种方法为“扩大路径法扩大路径法”.用扩大路径法总可以得到用扩大路径法总可以得到一条极大路径一条极大路径.在有向图中可类似讨论在有向图中可类似讨论.例例 由一条路径扩大出的极大路径不惟一，极大路径不一定是由一条路径扩大出的极大路径不惟一，极大路径不一定是最长的路径最长的路径52扩大路径法的应用扩大路径法的应用例例4 设设 G 为
45、为 n（n 3）阶无向简单图，）阶无向简单图，最小度最小度 (G)2，证明，证明G 中存在中存在长度长度 +1 的圈的圈.证证 设设 =v0v1vl 是一条极大路径。是一条极大路径。因为因为v0 不与不与 外外顶点相邻顶点相邻,又又 d(v0),因而在因而在 上除上除 v1外外,至少还存在至少还存在 1个个顶点与顶点与 v0 相邻相邻.设设 vx 是离是离 v0 最远的顶点最远的顶点,于是于是v0v1vxv0 为为 G 中长度中长度 +1 的圈的圈.539.4 图的矩阵表示图的矩阵表示无向图的关联矩阵无向图的关联矩阵定义定义9.21 无向图无向图G=，|V|=n，|E|=m，令，令 mij为为
46、 vi 与与 ej的关联次数，称的关联次数，称(mij)n m为为G 的的关联矩阵关联矩阵，记为，记为M(G).10000110000011001112)(GM例例e1 e2 e3 e4 e5v1v2v3v454无向图关联矩阵的性质无向图关联矩阵的性质是孤立点平行边的列相同imjijjiijimjijniijvmmmnivdmmjm0)5()4(2)3(,.,2,1,)()2(,.,2,1,2)1(1,11每列之和每行之和 55 的的终终点点为为，不不关关联联与与，的的始始点点为为jijijiijevevevm10,1定义定义9.22 设有向图有向图D=中无环，令中无环，令则称则称(mij)n
47、 m为为D的的关联矩阵关联矩阵，记为，记为M(D).例例有向图(无环)的关联矩阵 11100110000011100011)(DMe1 e2 e3 e4 e5v1v2v3v456(1)每列恰好有一个每列恰好有一个+1和一个和一个-1(2)-1的个数等于的个数等于+1的个数，都等于边数的个数，都等于边数m.(3)第第i行中，行中，+1的个数等于的个数等于d+(vi)出度，出度，-1的个数等于的个数等于d(vi)入度入度(4)平行边对应的列相同（如平行边对应的列相同（如e4,e5e4,e5）有向图关联矩阵的性质57有向图的邻接矩阵有向图的邻接矩阵定义定义9.23 设有向图设有向图D=,V=v1,v
48、2,vn,令令 为顶点为顶点 vi 邻接到顶点邻接到顶点 vj 边的条数边的条数，称，称()为为D的的邻接矩阵邻接矩阵，记作，记作A(D)，或简记为，或简记为A.)1(ija)1(ija 1100100001000120A例例58有向图邻接矩阵的性质有向图邻接矩阵的性质的的回回路路数数中中长长度度为为的的通通路路数数中中长长度度为为1)4(1)3(,.,2,1),()2(,.,2,1),()1(1)1(,)1(1)1(1)1(DaDmanjvdanivdaniiijiijjniijinjij 行之和等于出度列之和等于入度定理定理9.9 设设 A为有向图为有向图 D 的邻接矩阵的邻接矩阵,顶点集
49、顶点集V=v1,v2,vn，则则 A 的的 l 次幂次幂 Al（l 1）中元素）中元素推论推论 设设Bl=A+A2+Al(l 1),则则 ninjlijb11)(niliib1)(为长度小于或等于为长度小于或等于 l 的回路数的回路数.为长度小于或等于为长度小于或等于 l 的通路数的通路数,邻接矩阵的应用邻接矩阵的应用为长度为 l 的通路总数，)(lija)(liia ninjlija11)(niliia1)(为vi 到vj长度为 l 的通路数，为vi到自身长度为 l 的回路数，为长度为为长度为 l 的回路总数的回路总数.60例例5 有向图有向图D如图所示，求如图所示，求 A,A2,A3,A4
50、，并回答诸问题：，并回答诸问题：(1)D 中长度为中长度为1,2,3,4的通路各有多少条？其中回路分别为多的通路各有多少条？其中回路分别为多少条？少条？(2)D 中长度小于或等于中长度小于或等于4的通路为多少条？其中有多少条回路？的通路为多少条？其中有多少条回路？邻接矩阵实例邻接矩阵实例 0101100101020001A61 100401041005000101031003010400011002010210030001432AAA(1)D中长度为中长度为1的通路为的通路为8条，其中有条，其中有1条是回路条是回路.D中长度为中长度为2的通路为的通路为11条，其中有条，其中有3条是回路条是回路
