离散数学图论

1、第八章 图论ABCD一一. . 图的概念图的概念 一个图一个图 G=, 其中其中 V(G): 是是G的结点的非空集合的结点的非空集合. (V(G),简记成简记成V. E(G): 是是G的边的集合的边的集合. 有时简记成有时简记成E.v 结点结点(Vertices): 用用 表示表示, 旁边标上该结点的名称旁边标上该结点的名称.v 边边(Edges): 有向边有向边: 带箭头的弧线带箭头的弧线.从从u到到v的边表示成的边表示成 无向边无向边:不带箭头的弧线不带箭头的弧线.u和和v间的边表示成间的边表示成 (u,v)r w eV(G1)=r,e,wE(G1)=,A B C De1e5e7e6e3e

2、4e2G1 :G2 :V(G2)=A,B,C,DE(G2)=e1,e2,e3,e4,e5,e6,e7 8-1. 图的基本概念在图中在图中, 结点的相对位置、边的曲直、长短无关紧要结点的相对位置、边的曲直、长短无关紧要.v邻接点邻接点: 与一边关联的两个结点与一边关联的两个结点. v邻接边邻接边: 关联同一个结点的两条边关联同一个结点的两条边. v环环:只关联一个结点的边只关联一个结点的边. v平行边平行边:在两个结点之间关联的多条边在两个结点之间关联的多条边. v二二. 有向图与无向图有向图与无向图 有向图有向图:只有有向边的图只有有向边的图. 无向图无向图:只有无向边的图只有无向边的图.三三

3、. 零图与平凡图零图与平凡图 孤立结点孤立结点:不与任何边关联的结点不与任何边关联的结点. 零图零图:仅由一些孤立结点构成的图仅由一些孤立结点构成的图. 即此图的边的集合即此图的边的集合E= 平凡图平凡图:仅由一个孤立结点构成的零图仅由一个孤立结点构成的零图. |V(G)|=1, |E(G)|=0 u uv abvabce1e2四四. 简单图与多重图简单图与多重图 简单图简单图:不含有环和平行边的图不含有环和平行边的图. 多重图多重图: 含有平行边的图含有平行边的图. 五五. 图中结点图中结点v的度的度: 1.定义定义:G是个图是个图, vV(G), 结点结点v所关联边数所关联边数,称之为结称

4、之为结点点v的度的度. 记作记作 deg(v).(或或d(v).deg(a)=3 deg(b)=5 deg(c)=4 deg(d)=2 一个环给结点的度是一个环给结点的度是2. 2.图的结点度序列图的结点度序列:令令G=是图是图, V=v1,v2,v3,vn, 则称则称: (der(v1), der(v2),der(v3), ,der(vn) 为图为图G的结点度序的结点度序列列.例如上图的结点度序列为例如上图的结点度序列为:(3,5,4,2) 3.图的最大度图的最大度(G)与最小度与最小度(G) :G=是图是图, (G) =maxdeg(v)|vG (G) =mindeg(v)|vGA B C

5、 De1e5e7e6e3e4e2 cb a c a b d4. 定理定理8-1.1 每个图中所有结点度总和等于边数的每个图中所有结点度总和等于边数的2倍倍.即即证明证明:因为图中每条边关联两个结点因为图中每条边关联两个结点,因此每条边给予它所因此每条边给予它所关联的两个结点的度各是关联的两个结点的度各是1, 即一条边对应的度数是即一条边对应的度数是2, 所所以整个图的度数总和为边数的以整个图的度数总和为边数的2倍倍.定理定理8-1.2(握手定理握手定理)每个图中每个图中,奇数度的结点必为偶数奇数度的结点必为偶数个个.(一次集会中一次集会中,与奇数个人握手的人与奇数个人握手的人,必是偶数个必是偶

6、数个.)证明证明:令令G=是图是图,将将V分成两个子集分成两个子集V1 和和V2,其中其中 V1 -是度数是奇数的结点集合是度数是奇数的结点集合, V2 -是度数是偶数的结点集合是度数是偶数的结点集合 也是偶数也是偶数, 于是奇数度的结点数是偶数于是奇数度的结点数是偶数.deg(v)=2|E|vVdeg(v) + deg(v) =2|E|vV1 vV2而而deg(v)是偶数是偶数vV2所以所以deg(v)vV1六六. k-正则图正则图:一个无向简单图一个无向简单图G中中,如果如果(G)=(G)=k则称则称G为为k-正则图正则图.课堂练习课堂练习:1.下面哪些数的序列下面哪些数的序列,可能是一个

7、图的度数序列可能是一个图的度数序列?如果可能如果可能,请试画出它的图请试画出它的图. 哪些可能不是简单图哪些可能不是简单图? a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4)2.已知无向简单图已知无向简单图G中中,有有10条边条边,4个个3度结点度结点,其余结点的其余结点的度均小于或等于度均小于或等于2,问问G中至少有多少个结点中至少有多少个结点?为什么为什么? 1. a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4)解解:a)不是不是, 因为有三个数字是奇数因为有三个数字是奇数. b) 可能是可能是,如下图所示如下

8、图所示: c) 可能是可能是,如下图所示如下图所示:2.解解:已知边数已知边数|E|=10, deg(v)=2|E|=20其中有其中有4个个3度结点度结点, 余下结点度之和为余下结点度之和为: 20-34=8因为因为G是简单图是简单图, 其余每个结点度数其余每个结点度数2, 所以至少还有所以至少还有4个结点个结点. 所以所以G中至少有中至少有8个结点个结点. 七七. 有向图结点的出度和入度有向图结点的出度和入度:(in degree out degree) G=是有向图是有向图,vV v的出度的出度: 从结点从结点v发出的边数发出的边数. 记作记作deg+(v) 或或 dego(v) v的入度

9、的入度: 指向结点指向结点v的边数的边数. 记作记作deg-(v) 或或 degi(v)degi(a)=2 degi(b)=2 degi(c)=1 degi(d)=1dego(a)=2 dego(b)=3 dego(c)=1 dego(d)=0定理定理8-1.3 G=是有向图是有向图, 则则G的所有结点的出度之的所有结点的出度之和等于入度之和和等于入度之和.证明证明: 因为图中每条边对应一个出度和一个入度因为图中每条边对应一个出度和一个入度. 所以所有结点的出度之和与所有结点的入度之和都等于所以所有结点的出度之和与所有结点的入度之和都等于有向边数有向边数.必然有所有结点的出度之和等于入度之和必

10、然有所有结点的出度之和等于入度之和.a bc d八八. 完全图完全图1.无向完全图无向完全图 定义定义:G是个简单图是个简单图, 如果每对不同结点之间都有边相连如果每对不同结点之间都有边相连则称则称G是个完全图是个完全图. n个结点的无向完全图个结点的无向完全图G记作记作Kn.定理定理8-1.4 无向完全图无向完全图Kn, 有边数有边数证明证明: 因为因为Kn中每个结点都与其余中每个结点都与其余n-1个结点关联个结点关联 即每个结点的度均为即每个结点的度均为n-1所以所以Kn的所有结点度数总和为的所有结点度数总和为n(n-1) 设边数为设边数为|E| 于是于是n(n-1)=2|E| 所以所以|

11、E|= K2K3K4K5) 1(21nn) 1(21nn2. 有向图的完全图有向图的完全图 (注注:这里的定义与教材不同这里的定义与教材不同) 1).有向简单完全图有向简单完全图:G是个是个有向简单图有向简单图,如果任何两个如果任何两个不不同同结点之间都有结点之间都有相互连接相互连接的边的边,则称它是有向简单完全则称它是有向简单完全图图.例如例如: 定理定理8-1.5: 有有n个结点的有向简单完全图有边数为个结点的有向简单完全图有边数为n(n-1).证明证明: 显然它的边数是显然它的边数是Kn边数的边数的2倍倍.所以是所以是n(n-1). 2).有向完全图有向完全图(有向全图有向全图) (它与

12、完全关系图一致它与完全关系图一致) G是个有向图是个有向图,如果如果任何两个结点任何两个结点之间都有相互连接的之间都有相互连接的边边,则称它是有向完全图则称它是有向完全图. 其图形如下其图形如下: 所以有所以有n个结点的有向完全图个结点的有向完全图, 有边数有边数 n2.九九.子图和生成子图子图和生成子图1.子图子图:设设G=是图是图,如果如果G=且且V V, V, E E, 则称则称G是是G的子图的子图.可见可见G1,G2,G3都是都是K5的子图的子图. b cd e ab c ab cd eG1G2G3K5 ab cd e2. 生成子图生成子图设设G=是图是图, G=, G是是G的子图的子

13、图,如果如果V=V, 则称则称G是是G的生成子图的生成子图.上例中上例中, G1是是K5的生成子图的生成子图.十十. 补图补图由由G的的所有结点所有结点和为使和为使G变成完全图变成完全图,所需要添加的那些所需要添加的那些边组成的图边组成的图, 称之为称之为G相对完全图的补图相对完全图的补图,简称简称G的补图的补图,记作记作 G K5 G Gb cd e ab c ab cd eG1G2G3K5 ab cd e十一十一.相对补图相对补图设设G1=是图是图G=的子图的子图,如果有如果有G2= 使得使得E2=E-E1且且V2中仅包含中仅包含E2中的边所关联的结点中的边所关联的结点,则称则称G2是是G

14、1相对相对G的补图的补图.可见可见G1是是G3相对相对G的补图的补图. G3也是也是G1相对相对G的补图的补图.而而G2不是不是G3相对相对G的补图的补图(多了一个结点多了一个结点).但是但是G3是是G2相对相对G的补图的补图.可见可见: 相对补图无相互性相对补图无相互性. ab cd eGG2 ab cd e cd b eG1 ab cd eG3十二十二. 图的同构图的同构设设G=和和G=是图是图,如果存在双射如果存在双射f:VV 且且任何任何vi,vjV,若边若边(vi,vj)E,当且仅当当且仅当 边边(f(vi),f(vj)E,(或或若边若边E,当且仅当当且仅当 边边E),则称则称G与与

15、G同构同构,记作记作G G. (同构图要保持边的同构图要保持边的“关联关联”关系关系)例如例如:右边所示的两个图右边所示的两个图:G= G=构造映射构造映射f:VV两个图同构的必要条件两个图同构的必要条件:1.结点个数相等结点个数相等. 2.边数相等边数相等.3.度数相同的结点数相等度数相同的结点数相等. 4. 对应结点的度数相等对应结点的度数相等.a bc d1 43 2a 1b 2c 3d 4下面是否同构的图下面是否同构的图?右面两个图不同构右面两个图不同构:左图中四个左图中四个3度结点度结点构成四边形构成四边形,而右图而右图则不然则不然.a fb ec d 3 51 62 4 31 2

16、ab c ab ec d 13 45 2 练习练习:请画出请画出K4的所有不同构的生成子图的所有不同构的生成子图.本节要求本节要求:准确掌握如下基本概念和定理准确掌握如下基本概念和定理:1.有向边有向边,无向边无向边,孤立结点孤立结点,平行边平行边,环环.2.有向图有向图,无向图无向图,零图零图,平凡图平凡图,简单图简单图,多重图多重图,完全图完全图,子图子图,生成子图生成子图,补图补图,相对补图相对补图3.四个定理四个定理(关于结点度关于结点度,以及结点度与边数关系以及结点度与边数关系)4.图的同构图的同构 (会判断会判断).作业作业: P279 (1) (2) (4) (5) 8-2. 路

17、与回路 在实际应用中在实际应用中,比如在市内乘出租车去参观一个博览会比如在市内乘出租车去参观一个博览会, 一定要司机选一条最短的路一定要司机选一条最短的路. 到博览会后到博览会后, 最好选一条这最好选一条这样到路径样到路径,使得每个展台都参观一次后使得每个展台都参观一次后,再回到原来存包再回到原来存包处处. 这就是路与回路的问题这就是路与回路的问题.一一. 路的概念路的概念 1.路的定义路的定义: 给定图给定图G=设设v0 ,v1,v2,vnV, e1,e2,enE 其中其中ei是关联是关联vi-1 ,vi的边的边, 则称则称结点和边的交叉序列结点和边的交叉序列v0 e1v1 e2v2envn

18、是连接是连接v0到到vn的路的路. v0是此路的起点是此路的起点,vn是此路的终点是此路的终点. 路中含有的路中含有的边数边数 n称之为路的长度称之为路的长度.例如上图中例如上图中 v0 e2v3 e6v2是一条长度为是一条长度为2的路的路. v3 v2v1 v0e1e2e3e4e5e6如果图是个如果图是个简单图简单图, 则路可以只用结点序列表示则路可以只用结点序列表示. 如右图中如右图中, 路路:abcad如果图是个如果图是个有向图有向图, 则路可以则路可以只用边序列表示只用边序列表示. 如右边有向图中如右边有向图中 e1 e5e2e3 e6 是一条路是一条路.2. 回路回路:如果一条路的起

19、点和终点是一个结点如果一条路的起点和终点是一个结点,则称此路是则称此路是一个回路一个回路. 如右图中如右图中 L1=v0 e1v1 e5v3 e6v2e4v0 L2= v0 e1v1 e5v3e2v03. 迹与闭迹迹与闭迹 如果一条路中如果一条路中,所有所有边都不同边都不同,则称此路为则称此路为迹迹. 如果一条如果一条回路回路中中,所有所有边都不同边都不同,则称此回路为则称此回路为闭迹闭迹. v3 v2v1 v0e1e2e3e4e5e6 cb a d v3 v2v1 v0e1e2e3e4e5e64. 通路与圈通路与圈如果一条路中如果一条路中,所有所有结点都不同结点都不同,则称此路为则称此路为通

20、路通路.如果一条如果一条回路回路中中,除起点和终点外除起点和终点外,其余其余结点都不同结点都不同,则称则称此回路为此回路为圈圈.例如右图中例如右图中:L1=v0 e1v1 e5v3 e6v2e4v0 L2= v0 e1v1 e5v3e2v0L3=v0 e1v1 e5v3 e2v0 e3v3 e6v2e4v0 L1和和L2是闭迹是闭迹, 也是圈也是圈.L3是闭迹是闭迹,而不是圈而不是圈. v3 v2v1 v0e1e2e3e4e5e6定理定理8-2.1 在一个有在一个有n个结点的图中个结点的图中,如果从结点如果从结点vi到到vj存存在一条路在一条路,则从则从vi到到vj必存在一条长度不多于必存在一

21、条长度不多于n-1的路的路.*证明证明: 设设vi到到vj存在一条路存在一条路: vivi+1vi+2,vj ,设此路的长度为设此路的长度为k.假设假设kn-1, 则此路中有则此路中有 k+1个结点个结点, k+1n, 而而G中只有中只有n个结点个结点, 所以此路中必有两个结点相同所以此路中必有两个结点相同, 假设假设vs=vt, (ts)于是此路为于是此路为:从图看出从图看出,此路中有一个从此路中有一个从vs到到vt的回路的回路, 此回路中此回路中,有有t-s条边条边( t-s1), 如果删去这个回路如果删去这个回路, 就得到一条就得到一条vi到到vj更更短的路短的路.如果新的路长度还大于如

22、果新的路长度还大于n-1, 说明此路中还有回路说明此路中还有回路,再删去再删去回路回路, 如此进行下去如此进行下去. 最后必可找到长度小于最后必可找到长度小于n-1的路的路. vs-1 vi+1 vt+1 vs = vt vs+1vi vt-1 vj vj-1.二二. 无向图的连通性无向图的连通性1.两个结点是连通的两个结点是连通的: 在无向图中在无向图中,结点结点u和和v之间之间如果存在一条路如果存在一条路, 则称则称u与与v是连通的是连通的. 我们规定我们规定: 对任何结点对任何结点u, u与与u是连通的是连通的.2.结点之间的连通关系是个等价关系结点之间的连通关系是个等价关系. 令令G=

23、是无向图是无向图, R是是V上连通关系上连通关系, 即即 R=|u和和v是连通的是连通的 显然显然R具有自反、对称和传递性具有自反、对称和传递性.于是可以求商集于是可以求商集V/R.例例1. 给定图给定图G1如右上图所示如右上图所示: V/R=a,b,g,c,d,e,f,h例例2.给定图给定图G2如右下图所示如右下图所示: V/R=1,3,5,2,4,6 gh a b ef c d 26 4 51 33.连通分支连通分支:令令G=是无向图是无向图, R是是V上连通关系上连通关系, 设设R对对V的的商集商集中有等价类中有等价类V1,V2,V3, Vn ,这这n个个等价类等价类构成构成的的n个子图

24、分别记作个子图分别记作G(V1),G(V2),G(V3), G(Vn),并称它并称它们为们为G的连通分支的连通分支. 并用并用W(G)表示表示G中连通分支数中连通分支数.下边例中下边例中4.连通图连通图: 如果一个图如果一个图G只有一个连通分支只有一个连通分支(W(G)=1),则称则称G是连通图是连通图. W(G3)=1 , G3是连通图是连通图 gh a b ef c dG1 26 4 51 3G2 G3W(G1)=3W(G2)=2W(G3)=1定理定理8-2.2: 图图G=是连通图是连通图,当且仅当当且仅当 对对V的任何分的任何分成成V1、V2的划分的划分,恒存在一条边恒存在一条边, 使得

25、它的两个端点分别使得它的两个端点分别属于属于V1和和V2.*证明证明:必要性必要性. 已知已知G是连通的是连通的. 令令V1,V2是是V的一个划分的一个划分.任取任取v1V1, v2V2, 由于由于G是连通的是连通的, 必存在一条路必存在一条路 v1 . v2, 在此路上必存在结点在此路上必存在结点u和和v,使得使得uV1, vV2 ,且且(u,v)是此路中是此路中的一条边的一条边. 充分性充分性:已知对已知对V的任何分成的任何分成V1、V2的划分的划分,恒存在一条边恒存在一条边,使它的两个端点分别属于使它的两个端点分别属于V1和和V2 (反证法反证法)假设假设G不是连通的不是连通的. 则则G

26、至少有两个连通分支至少有两个连通分支G1、 G2,令令V1 =V(G1) V2=V-V(G1), 根据连通分支定义知根据连通分支定义知, 不不存在端点分别属于存在端点分别属于V1和和V2的边的边, 与已知矛盾与已知矛盾. 所以所以G是是连通的连通的.V1V2u vv1 v2.三三. 割集割集 (Cut Set) 割集在图论中是个重要概念割集在图论中是个重要概念, 在图论的理论和应用中在图论的理论和应用中, 都具有重要地位都具有重要地位. 比如有交通图比如有交通图:结点结点u, 边边e就是就是至关重要的至关重要的.割集就是使得原来连通的图割集就是使得原来连通的图, 变成不连通变成不连通, 需要删

27、去的需要删去的结点集合或边的集合结点集合或边的集合.1.点割集与割点点割集与割点:令令G=是是连通无向图连通无向图, 结点集合结点集合V1 , V1 V, 如果删去如果删去V1中所有结点后中所有结点后,G就变得不连通了就变得不连通了, 而删而删去去V1的任何真子集中的所有结点的任何真子集中的所有结点,得到的子图仍然连通得到的子图仍然连通.则则称称V1是是G的一个的一个点割集点割集. 如果点割集如果点割集V1中只有一个结点中只有一个结点, 则称此结点为则称此结点为割点割点.注注:在图中删除结点在图中删除结点u,是指把是指把u以及与以及与u关联的边都删除关联的边都删除.在图中删除某边在图中删除某边

28、,仅需把该边删除仅需把该边删除. u e左上图中左上图中:b,f, b,g, f,k,k,g以及以及a,d,i,l是点割集是点割集.不存在割点不存在割点.2. 点连通度点连通度:若若G不是完全图不是完全图, 定义定义: k(G)=min | V1 | | V1是是G的点割集的点割集 为为G的的点连通度点连通度. 点连通度点连通度k(G)是表示为使是表示为使G不连通不连通,至少要删去的结点数至少要删去的结点数. 上例中上例中 k(G)=2 具有割点图的点连通度具有割点图的点连通度 k(G)=1,如右图如右图 g ca i ej d h l k g ca b i ej f d h l k g c

29、b ej f h k u 定理定理8-2.3 :一个连通图中结点一个连通图中结点v是是割点割点的充分且必要条件的充分且必要条件是存在两个结点是存在两个结点u和和w, 使得从使得从u到到w的任何路都通过的任何路都通过 v .证明证明:略略上边是通过删去结点的办法使连通图变得不连通的上边是通过删去结点的办法使连通图变得不连通的. 也可以通过删去边的办法使连通图变得不连通也可以通过删去边的办法使连通图变得不连通.3. 边割集与割边边割集与割边(桥桥)令令G=是是连通无向图连通无向图, 边的集合边的集合E1,E1 E, 如果删去如果删去E1中所有边后中所有边后,G就变得不连通了就变得不连通了, 而删去

30、而删去E1的任何真子集的任何真子集中的所有边中的所有边,得到的子图仍然连通得到的子图仍然连通.则称则称E1是是G的一个的一个边割边割集集. 如果边割集如果边割集E1中只有一条边中只有一条边, 则称此边为则称此边为割边割边, 也称之也称之 为为桥桥.如右图中如右图中e就是桥就是桥. e4.边连通度边连通度:若若G不是平凡图不是平凡图, 定义定义: (G)=min |E1| | E1是是G的边割集的边割集为图为图G的的边连通度边连通度. 边连通度边连通度(G)是表示为使是表示为使G不连通不连通,至少要删去的边数至少要删去的边数.显然显然,如果如果G不是连通图不是连通图, 则则 k(G)=(G)=0

31、*定理定理8-2.4 对于任何一个图对于任何一个图G,有有 k(G)(G)(G)证明证明: 略略(可参考书可参考书P283中定理中定理7-2.2)四四. 有向图的连通性有向图的连通性 1.结点间的可达性结点间的可达性: G=是有向图是有向图, u,vV, 如果从如果从 u到到v有一条路有一条路, 则称从则称从u到到v可达可达. 右图中右图中 a可达可达b和和d, 但是但是a不可达不可达c. 显然结点间的可达关系显然结点间的可达关系,具有具有自反性和传递性自反性和传递性. 2. 结点结点u到到v的距离的距离: 如果如果u可达可达v, 可能从可能从u到到v有多条路有多条路,其其中中最短的路最短的路

32、的长度的长度,称之为从称之为从u到到v的距离的距离.记作记作d. 上例中上例中 d=1 d=2 d=0 d= 3. 可达性的性质可达性的性质: 1). d0 2) d=0 3) d + dd (如上图的如上图的c,a,b) 4) 如果从如果从u到到v不可达不可达,则则d= (如如b,c) 5)如从如从u可达可达v,从从v也可达也可达u, 但但d不一定等于不一定等于d. 例如例如 dd dc a b4. 图的直径图的直径: G是个图是个图, 定义定义 为图为图G的直径的直径.上图中上图中, 图的直径图的直径D= (因为因为d=)5. 强连通、单侧连通和弱连通强连通、单侧连通和弱连通 在在简单有向

33、图简单有向图G中中,如果如果任何任何两个结点间两个结点间相互相互可达可达, 则称则称G是是强连通强连通. 如果任何一对结点间如果任何一对结点间, 至少至少有一个结点到另有一个结点到另一个结点可达一个结点可达, 则称则称G是是单侧连通单侧连通. 如果将如果将G看成无向图后看成无向图后(即把有向边看成无向边即把有向边看成无向边)是连通的是连通的,则称则称G是是弱连通弱连通.(a)强连通强连通.(b)a到到d, d到到a, 都不可达都不可达 是弱连通是弱连通.(c)单侧连通单侧连通. dc a bD=maxd u,vV dc a b dc a b dc a b(a)(b)(c)定理定理8-2.5:一

34、个一个有向图有向图G是强连通的是强连通的,当且仅当当且仅当G中有一个中有一个回路回路, 此回路至少包含每个结点一次此回路至少包含每个结点一次.证明证明:充分性充分性: 显然成立显然成立. 因为如果因为如果G中有一个回路中有一个回路, 它至少包含每个结点一次它至少包含每个结点一次就使得任何两个结点间相互可达就使得任何两个结点间相互可达 所以所以G是强连通的是强连通的. 必要性必要性:如果如果G是强连通的是强连通的,则任何两个结点间相互可达则任何两个结点间相互可达.所以可以构造一个回路经过所有结点所以可以构造一个回路经过所有结点. 否则必有一个回路不包含某个结点否则必有一个回路不包含某个结点v所以

35、所以v与回路上的各结点都不相互可达与回路上的各结点都不相互可达.这与这与G是强连通条件矛盾是强连通条件矛盾.所以所以G必有回路至少包含每个结点一次必有回路至少包含每个结点一次. 可以应用此定理判断可以应用此定理判断G是否为强连通是否为强连通, 就是看它是否有包就是看它是否有包含每个结点的回路含每个结点的回路.6. 强分图、单侧分图和弱分图强分图、单侧分图和弱分图在在简单有向图简单有向图中中,具有强连通性质的最大子图具有强连通性质的最大子图,称为称为强分图强分图.具有单侧连通的最大子图具有单侧连通的最大子图,称为称为单侧分图单侧分图. 具有弱连通的具有弱连通的最最大子图大子图,称为称为弱分图弱分

36、图. 这些这些分图用结点的集合表示分图用结点的集合表示. 例如例如,给定有向图给定有向图G,如图所示如图所示:求它的强分图、单侧分图和求它的强分图、单侧分图和弱分图弱分图.解解: 强分图强分图:由由a,g,hbc def导出的子图导出的子图.单侧分图单侧分图:由由a,g,h,b,f,d,eb,c,f,d,e导出的子图导出的子图.弱分图弱分图:G本身是弱分图本身是弱分图. ef c d gh a b定理定理8-2.6 在有向图中在有向图中,每个结点必位于一个且只位于一每个结点必位于一个且只位于一个个强分图中强分图中.证明证明:令令G=是有向图是有向图, 任取结点任取结点vV, 令令S是所有与是所

37、有与v 相互可达的结点集合相互可达的结点集合, 当然当然vS S, 而而S是一个是一个强分图强分图, 所以所以v必位于一个强分图中必位于一个强分图中. 如果如果v位于两个不同的强分图位于两个不同的强分图S1、S2中中, 于是于是 v与与S1中中每个结点相互可达每个结点相互可达, v也与也与 S2中每个结点相互可达中每个结点相互可达, 所所以以S1中每个结点都与中每个结点都与S2中每个结点通过中每个结点通过v相互可达相互可达, 这这说明说明S1与与S2是一个强分图是一个强分图, 与已知与已知S1、S2是两个不同的是两个不同的强分图矛盾强分图矛盾. 所以每个结点必位于一个且只位于一个强分图中所以每

38、个结点必位于一个且只位于一个强分图中.在给定的简单有向图中找强分图在给定的简单有向图中找强分图-回路中的结点构成回路中的结点构成一个强分图一个强分图, 不在回路中的结点不在回路中的结点,自己构成一个强分图自己构成一个强分图. 作业作业 P286 (3) (5) (8)8-3. 图的矩阵表示图的矩阵表示不仅是给出图的一种表示方法图的矩阵表示不仅是给出图的一种表示方法, 还可以通过还可以通过这些矩阵讨论有关图的若干性质这些矩阵讨论有关图的若干性质, 更重要的是可以用矩阵更重要的是可以用矩阵形式将图存入计算机中形式将图存入计算机中, 在计算机中对图作处理在计算机中对图作处理. 这里主要讨论图的三种矩

39、阵这里主要讨论图的三种矩阵.一一. 邻接矩阵邻接矩阵 这是以这是以结点结点与与结点结点之间的邻接关系确定的矩阵之间的邻接关系确定的矩阵.1.定义定义:设设G=是个简单图是个简单图,V=v1,v2,v3,vn , 一个一个nn阶矩阵阶矩阵A=(aij)称为称为G的邻接矩阵的邻接矩阵. 其中其中:aij =1 vi与与vj邻接邻接, 即即(vi,vj)E 或或 E0 vi与与vj不邻接或不邻接或i=j例如例如, 给定无向图给定无向图G1和有向图和有向图G2如图所示如图所示:2.从邻接矩阵看图的性质从邻接矩阵看图的性质: 无向图无向图:每行每行1的个数的个数=每列每列1的个数的个数=对应结点的度对应

40、结点的度 有向图有向图:每每行行1的个数的个数=对应结点的对应结点的出度出度 每每列列1的个数的个数=对应结点的对应结点的入度入度v1 v5v4 v2 v3G1v3 v2 v4 v5v1 G20100010010010010100000100)(0110010010100110110100110)(21GAGA3.邻接矩阵的乘积邻接矩阵的乘积在在(A(G1)2 中中a342 =2 表示从表示从v3到到v4有长度为有长度为2的路有的路有2条条: 在在(A(G1)3中中a233 =6 表示从表示从v2到到v3有长度为有长度为3的路有的路有6条条:v2v1v2v3 , v2v4v2v3 , v2v3

41、v2v3 , v2v3v1v3 , v2v3v5v3 , v2v4v5v3 .2002102201023112013111112)(0110010010100110110100110)(211GAGAv1 v5v4 v2 v3G1045124015251264156242244201100100101001101101001102002102201023112013111112)(31GAv3 v2v4 , v3 v5v4定理定理8-3.1设设G=是简单图是简单图,令令V=v1,v2,v3,vn, G的的邻接矩阵邻接矩阵(A(G)k中的第中的第 i行第行第j列元素列元素aijk=m, 表示在图

42、表示在图G中从中从vi到到vj长度为长度为k的路有的路有m条条.可以用归纳法证明可以用归纳法证明.(见教材见教材P290)在实际应用中在实际应用中,有时只关心从一个结点到另一个结点是否有时只关心从一个结点到另一个结点是否有路有路,而不关心路有多长而不关心路有多长,比如电话网络比如电话网络. 这就促使我们定这就促使我们定义可达矩阵义可达矩阵.二二.可达性矩阵可达性矩阵1.定义定义:设设G=是个简单图是个简单图,V=v1,v2,v3,vn , 一个一个nn阶矩阵阶矩阵P=(pij)称为称为G的可达性矩阵的可达性矩阵. 其中其中:pij =1 vi到到vj可达可达, (至少有一条路至少有一条路) 0

43、 其它情况其它情况2.求可达矩阵求可达矩阵 可以根据邻接矩阵可以根据邻接矩阵A求可达矩阵求可达矩阵. 设设|V(G)|=n 令令A(k)是将是将Ak中的非中的非0元素都写成元素都写成1,而得到的只含有而得到的只含有0和和1的的0-1矩阵矩阵.于是可达矩阵于是可达矩阵P为为: P=AA(2)A(3).A(n) 其中其中是逻辑或是逻辑或. 有两种方法求有两种方法求P 方法方法1. 按照矩阵相乘分别求出按照矩阵相乘分别求出A(k) (k2), 然后再然后再. 方法方法2.用求传递闭包的用求传递闭包的Warshall算法算法,见见P124.例如例如,G2如图所示如图所示, 求它的求它的可达矩阵可达矩阵

44、P. v3 v2 v4 v5v1 G2 P=AA(2)A(3)A(4)A(5)3.用用可达矩阵可达矩阵求强分图求强分图. 以以G2为例为例 从图看出有两个强分图从图看出有两个强分图:v1,v3和和v2,v4,v5下面看怎样用下面看怎样用P求强分图求强分图.0010000010100100100100010A=1001001011011010001001001A(2) =0110101011100100100000010A(3) =1001001011011010001001001A(4) =A(2)A(5)=A(3)1111101011111110101101011P=v3 v2 v4 v5v

45、1 G2先将先将P=(pij)转置得转置得PT=(pTij), 如果如果vi与与vj相互可达相互可达,则则 pij= pTij =1进而求进而求PPT对对PPT进行初等变换进行初等变换 第第2行与第行与第3行交换行交换,再第再第2列与第列与第3列交换列交换最后得两个强分图最后得两个强分图:v1,v3和和v2,v4,v5三三.完全关联矩阵完全关联矩阵 此矩阵是按照此矩阵是按照结点结点与与边边之间的关联关系确定的矩阵之间的关联关系确定的矩阵.1111101011111110101101011P=1010011111101001111111111PT=PPT=10100010111010001011

46、010111100011000001110011100111初等变换得v1v3v2v4v51.无向图的完全关联矩阵无向图的完全关联矩阵 1).定义定义:设设G=是个无向图是个无向图,V=v1,v2,v3,vm , E=e1,e2,e3,en ,一个一个mn阶矩阵阶矩阵M=(mij)称为称为G的完的完全关联矩阵全关联矩阵. 其中其中:2).从关联矩阵看图的性质从关联矩阵看图的性质: a)每列每列只有二个只有二个1. (因为每条边只关联两个结点因为每条边只关联两个结点) b)每行中每行中1的个数为对应的个数为对应 结点的度数结点的度数. c)如果两列相同如果两列相同,则说明对应的则说明对应的 两条

47、边是平行边两条边是平行边.mij = 1 vi与与ej关联关联 0 否则否则e1e2e3e5e7e6e4v1 v5v4 v2 v3 e1 e2 e3 e4 e5 e6 e7v1 1 1 0 0 0 0 0 v2 1 0 1 1 1 0 0 v3 0 1 1 1 0 1 0v4 0 0 0 0 1 0 1v5 0 0 0 0 0 1 1M=2.有向图的完全关联矩阵有向图的完全关联矩阵 1).定义定义:设设G=是个简单有向是个简单有向图图,V=v1,v2,v3,vm , E=e1,e2,e3,en , 一个一个mn阶矩阵阶矩阵M=(mij)称为称为G的完全关联矩的完全关联矩阵阵. 其中其中: 2)

48、.从关联矩阵看图的性质从关联矩阵看图的性质: a)每列只有一个每列只有一个1和一个和一个-1. (每条边有一个起点一个终点每条边有一个起点一个终点) b)每行中每行中1的个数为对应结点的个数为对应结点 的出度的出度.-1个数是结点入度个数是结点入度mij = 1 vi是是ej的起点的起点 -1 vi是是ej的终点的终点 0 vi与与ej不关联不关联 e1 e2 e3 e4 e5 e6 e7v1 -1 1 0 0 0 0 0 v2 1 0-1 0-1 0 0 v3 0-1 1-1 0-10v4 0 0 0 1 1 0 1v5 0 0 0 0 0 1-1M=v1 v5v4 v2 v3e1e2e3e

49、5e7e6e4本节重点掌握本节重点掌握: 图的三个矩阵的求法图的三个矩阵的求法 由图的矩阵由图的矩阵,看图的性质看图的性质. 作业作业 P300 (3)一一.欧拉图欧拉图: 1.欧拉路欧拉路:在无孤立结点的图在无孤立结点的图G中中,如果存在一条如果存在一条路路,它经过图它经过图中每条边一次且仅一次中每条边一次且仅一次, 称此路为欧拉路称此路为欧拉路. 2.欧拉回路欧拉回路:在无孤立结点的图在无孤立结点的图G中中,若存在一条若存在一条回路回路,它经过它经过图中每条边一次且仅一次图中每条边一次且仅一次,称此回路为欧拉回路称此回路为欧拉回路. 称此图为欧拉图称此图为欧拉图,或或E图图.(Euler)

50、 在在G1中中:有欧拉路有欧拉路:acbefgdcfh在在G2中中:有欧拉回路有欧拉回路:v1v2v3v4v5v2v4v6v5v3v1如何判定一个图中是否有欧拉路如何判定一个图中是否有欧拉路,或有欧拉回路或有欧拉回路?a ge b d hc f G1v1 v5v4 v2 v3 v6G28-4. 欧拉图与汉密尔顿图欧拉图与汉密尔顿图3.有欧拉路与有欧拉回路的判定有欧拉路与有欧拉回路的判定:定理定理8-4.1:无向图无向图G具有具有欧拉路欧拉路,当且仅当当且仅当G是连通的是连通的,且有且有零个零个或或两个两个奇数度的结点奇数度的结点.*证明证明:必要性必要性.(见教材见教材P302)充分性充分性,

51、(证明的过程就是一个构造欧拉路的过程证明的过程就是一个构造欧拉路的过程) 如果如果G有两个奇数度结点有两个奇数度结点:就从一个奇数度结点出发就从一个奇数度结点出发,每每当到达一个偶数度结点当到达一个偶数度结点,必然可以再经过另一条边离开此必然可以再经过另一条边离开此结点结点,如此重复下去如此重复下去,经过所有边后到达另一个奇数度结点经过所有边后到达另一个奇数度结点 如果如果G无奇数度结点无奇数度结点,则可以从任何一个结点出发则可以从任何一个结点出发,去构去构造一条欧拉路造一条欧拉路.推论推论:无向图无向图G具有具有欧拉回路欧拉回路,当且仅当当且仅当G是连通的是连通的,且所有且所有结点的度都是偶

52、数结点的度都是偶数.用此推论判断用此推论判断,七桥问题的图是不是欧拉图七桥问题的图是不是欧拉图?4.求欧拉回路的算法求欧拉回路的算法:A B C De1e5e7e6e3e4e2G有有E回路回路?停止停止N选结点选结点v 以以v为起点找闭迹为起点找闭迹E1 E1包含所有包含所有 边边Y打印打印 E1在在G-E1中找一个闭迹中找一个闭迹E2 使使 E1与与 E2至少有一个公共点至少有一个公共点N以某以某公共点公共点为起、末点为起、末点,对对 E1E2中的边重新排序得中的边重新排序得 新的闭迹新的闭迹C E1:=CY不是不是用上述算法求右图中欧拉回路用上述算法求右图中欧拉回路.此图中所有结点度均为偶

53、数此图中所有结点度均为偶数,所以有欧拉回路所以有欧拉回路.a) 选以选以1为起点的闭迹为起点的闭迹E1:1261b) E1不包含所有边不包含所有边.c) 在在G- E1中找新闭迹中找新闭迹E2: 6356 ( 6是是E1与与E2的公共点的公共点)d)以公共点以公共点6为起点为起点,对对E1E2中的边排序中的边排序:C=6356126e) E1 := Cf) E1不包含所有边不包含所有边.g) 在在G- E1中找新闭迹中找新闭迹E2: 52345 ( 5是是E1与与E2的公共点的公共点)h)以公共点以公共点5为起点为起点,对对E1E2中的边排序中的边排序: C=52345612635i) E1

54、:= Cj) E1包含所有边包含所有边. k)打印打印E1 =52345612635 l)停止停止. 16 25 3 4 16 25 3 4欧拉路与欧拉回路问题欧拉路与欧拉回路问题, 也称一笔画问题也称一笔画问题.*5.欧拉图的应用欧拉图的应用-计算机鼓轮的设计计算机鼓轮的设计早期向计算机输入数据早期向计算机输入数据, 为简单为简单,以输入八进制数为例以输入八进制数为例 (0,1,2,3,4,5,6,7,即即000,001,010,011,100,101,110,111)鼓轮表面分成鼓轮表面分成23等分等分,每一等分分别用绝缘体或导体组成每一等分分别用绝缘体或导体组成,绝缘部分输出绝缘部分输出

55、0,导体部分输出导体部分输出1. 有三个触点分别与三个有三个触点分别与三个部分接触部分接触,以读取三个数字以读取三个数字. 如图所示如图所示:转动鼓轮转动鼓轮,分别输出分别输出8个数个数:000,001,010,011,100,101,110,111 下面介绍此鼓轮的设计过程下面介绍此鼓轮的设计过程:00001111 此轮的设计此轮的设计:以两位二进制数以两位二进制数V=00,01,10,11为结点为结点,画带权图画带权图(即边上标有数字即边上标有数字-称为边的权称为边的权), 从任何从任何a1a2V结点画有向边结点画有向边,标的权标的权0(或或1), 该边指向结点该边指向结点a20(或或a2

56、1),于是构成边于是构成边a1a20, (或或a1a21),这八条边分别表示这八条边分别表示八个二进制数八个二进制数:000,001,010,011,100,101,110,111从此图上取一个回路从此图上取一个回路: e0e1e2e5 e3e7e6e4将上述各边的末位数字写成序列将上述各边的末位数字写成序列:01011100,于是就按照此序列将鼓轮进行加工于是就按照此序列将鼓轮进行加工,标标0部分部分用绝缘体用绝缘体,标标1部分用导体部分用导体.001001111e0 =000e1 =001e3 =011e4 =100e5 =101e2 =010110 = e6e7 =11100001111

57、 二二. 汉密尔顿图汉密尔顿图(H图图) (Hamilton图图)Hamilton是英国数学家是英国数学家,在在1959年年,他提出他提出Hamilton回路回路.H图起源于一种游戏图起源于一种游戏,这个游戏就是所谓周游世界问题这个游戏就是所谓周游世界问题. 例如例如,某个城市的街道如图所示某个城市的街道如图所示:该城市的所有交叉路口都有形象各该城市的所有交叉路口都有形象各异的精美的雕塑异的精美的雕塑,吸引着许多游客吸引着许多游客,人人都想找到这样的路径人人都想找到这样的路径:游遍各游遍各个景点再回到出发点个景点再回到出发点-H回路回路.1.定义定义:设设G=是个无向有限图是个无向有限图, 汉

58、密尔顿路汉密尔顿路:通过通过G中每个结点恰好一次的路中每个结点恰好一次的路. 汉密尔顿回路汉密尔顿回路(H回路回路):通过通过G中每个结点恰好一次的回中每个结点恰好一次的回路路. 汉密尔顿图汉密尔顿图(H图图):具有汉密尔顿回路具有汉密尔顿回路(H回路回路)的图的图.例如右图中例如右图中,就是就是H图图因为它有因为它有H回路回路:12345612.汉密尔顿图的判定汉密尔顿图的判定: 到目前为止并到目前为止并没有没有判定判定H图的充要条件图的充要条件.定理定理8-4.2 (充分条件充分条件):G是完全图是完全图,则则G是是H图图.证明证明:略略定理定理8-4.3(充分条件充分条件)设设G是有是有

59、n个结点的简单图个结点的简单图,若对若对G中中每对结点度数之和大于等于每对结点度数之和大于等于n-1(n),则则G有一条有一条H路路(H回路回路)证明证明: 先证明先证明G是连通的是连通的.(反证法反证法) 见书见书P307 再构造再构造H路路(H回路回路) 16 25 3 4 K2K3K4K5在图在图G1中中满足充分条件满足充分条件(G)=4 (G)=2任意两个结点度数之和大于任意两个结点度数之和大于5,所以是所以是H图图. 注意注意:上述条件只是充分条件上述条件只是充分条件,而不是必要条件而不是必要条件即不满足这个条件的即不满足这个条件的, 也可能有也可能有H路路.例如例如:在图在图G2中

60、中并不满足任意两个结点度数之和大于并不满足任意两个结点度数之和大于3, 但是却有但是却有H路路. 15 24 3G1d c a b G2定理定理8-4.4:(必要条件必要条件) 若图若图G=有有H回路回路,则对则对V的任何非空的任何非空子有限集子有限集S, 均有均有W(G-S)|S|, 其中其中W(G-S)是从是从G中删去中删去S中所中所有结点及与这些结点关联的边所得到的子图的连通分支数有结点及与这些结点关联的边所得到的子图的连通分支数.证明证明:设设C是图是图G的一条的一条H回路回路,则对于则对于V的任何非空子集的任何非空子集S,在在C中删去中删去S中任意一个结点中任意一个结点v1后后, 则