离散数学图.

1、第第7章章 图图第第1节节图的基本概念图的基本概念第第2节节子图与图的运算子图与图的运算第第3节节路径、回路和连通性路径、回路和连通性第第4节节图的矩阵表示图的矩阵表示第第5节节欧拉图和哈密顿图欧拉图和哈密顿图第第6节节平面图与欧拉公式平面图与欧拉公式第第7节节二部图与匹配二部图与匹配第第8节节树树第第9节节根树及其应用根树及其应用第第1节节 图的基本概念图的基本概念1、图的定义图的定义2、无向图、有向图、混合图、无向图、有向图、混合图3、邻接结点、邻接边、邻接结点、邻接边4、自环、平行边、简单图、自环、平行边、简单图5、度（入度、出度）、度（入度、出度）6、奇结点、偶结点、奇结点、偶结点7、

2、孤立结点、端点（悬挂点）、悬挂边、孤立结点、端点（悬挂点）、悬挂边8、零图、平凡图、零图、平凡图、d度正则图、完全图度正则图、完全图9、图同构、图同构10、判断两个图同构的必要条件、判断两个图同构的必要条件1、图的定义图的定义图图G是一个三元组是一个三元组: GV(G), E(G),非空结点集合非空结点集合边的集合边的集合从从E(G)到结点无到结点无序偶（有序偶）序偶（有序偶）集合上的集合上的函数函数有向边、无向边有向边、无向边边的曲、直、长、短以及结点的位置是无关紧要的边的曲、直、长、短以及结点的位置是无关紧要的G(e i)=(vi,vj)结点的无序偶结点的无序偶无向边无向边用连接用连接vi

3、和和vj的无向线段表示的无向线段表示G(e i)=结点的有序偶结点的有序偶有向边有向边用连接用连接vi和和vj的有向线段表示的有向线段表示vi为边为边ei的起点的起点vj为边为边ei的终点的终点vivjvivje ie i图的举例图的举例G= V(G),E(G), G= V(G)=a,b,c,d V(G)=a,b,c,d E(G)=E(G)=e1 , , e2, , e3 , , e4 , , e5 , , e6 G G( (e1)=(a,b)=(a,b)，G G ( (e2)=(a,c) )=(a,c) G G ( (e3)=(b,d)=(b,d) ) G G ( (e4)=(b,c) )=

4、(b,c) G G ( (e5)=(d,c) )=(d,c) ，G G ( (e6)=(a,d)=(a,d)请画出对应的无向图。abdce1e2e3e4e5e6abdce1e2e3e4e5e62、无向图、有向图、混合图、无向图、有向图、混合图（1）有向图有向图：若图：若图G中所有的边都是有向边。中所有的边都是有向边。（2）无向图无向图：若图：若图G中所有的边都是无向边。中所有的边都是无向边。（3）混合图混合图：若图：若图G中一些边是有向边，另一些中一些边是有向边，另一些边是无向边。边是无向边。只讨论有向图和无向图只讨论有向图和无向图3、邻接结点、邻接边、邻接结点、邻接边关联同一个结点的两条边关

5、联同一个结点的两条边邻接结点邻接结点: 由一条边相连接的两个结点由一条边相连接的两个结点vivje ivi和和 vj邻接邻接邻接边邻接边:vivje iei和和 ej邻接邻接vke j邻接结点、邻接边举例邻接结点、邻接边举例a a、b b、c c、d d四个结点中的任意两个结点四个结点中的任意两个结点都是邻接结点；都是邻接结点； e e1 1和和e e5 5不邻接；不邻接； e e4 4和和e e6 6不邻接；不邻接； e e2 2和和e e3 3不邻接。不邻接。4、自环、平行边、简单图、自环、平行边、简单图图图G=（1）自环）自环:关联于同一个结点的边关联于同一个结点的边（2）平行边）平行边

6、: 关联于同一对结点的两条边关联于同一对结点的两条边（3）简单图）简单图: 无平行边和自环的图无平行边和自环的图平行边举例平行边举例在有向图中，如果边在有向图中，如果边e e1 1和和e e2 2关联于同一关联于同一对结点，但方向相反，则它们不是平行边。对结点，但方向相反，则它们不是平行边。5、度（入度、出度）、度（入度、出度）图图G=vV(G)与结点与结点v相关联的边的条数相关联的边的条数（1）v的度的度:G是无向图是无向图,deg(v)（2）v的出度的出度:G是有向图是有向图, 以以v为起点的边的条数为起点的边的条数deg+(v)v的入度的入度:以以v为终点的边的条数为终点的边的条数deg

7、-(v)v的度的度: v的出度和入度之和的出度和入度之和deg(v)自环的度自环的度对于无向图中的一个自环，给该结点的对于无向图中的一个自环，给该结点的度增加度增加2；对于有向图中的自环，给该结点对于有向图中的自环，给该结点增加一增加一个出度和一个入度个出度和一个入度，故该结点的度也增加，故该结点的度也增加2。结点度的举例结点度的举例给出图给出图1 1各结点的度；各结点的度；给出图给出图2 2各结点的出度、入度、度。各结点的出度、入度、度。解答解答deg(v1)=deg(v4)=3deg(v2)=deg(v3)=2deg+(v1)=1, deg-(v1)=1, deg(v1)=2deg+(v2

8、)=1, deg-(v2)=2, deg(v2)=3deg+(v3)=2, deg-(v3)=0, deg(v3)=2deg+(v4)=2, deg-(v4)=1, deg(v4)=3deg+(v5)=0, deg-(v5)=2, deg(v5)=2(n,m)图图图图n个结点个结点m条边条边(n,m)图图定理定理mvnii2)deg(1(n,m)图图所有结点的度之和等于边数的两倍所有结点的度之和等于边数的两倍证明证明因为因为 ：每条边必关联两个结点：每条边必关联两个结点一条边给它所关联的两个结点的度各增加一条边给它所关联的两个结点的度各增加1为整个图的度数增加为整个图的度数增加2所以：结点的度

9、数总和恰好为边数的两倍。所以：结点的度数总和恰好为边数的两倍。定理验证定理验证m=5deg(v1)+deg(v2)+deg(v3)+deg(v4)=3+2+2+3=10=2m定理定理mvvininii)(deg)(deg11(n,m)有向图有向图所有结点的出度之和等于入度之和等于边数所有结点的出度之和等于入度之和等于边数定理验证定理验证m=6deg+(v1)+ deg+(v2)+ deg+(v3) +deg+(v4)+ deg+(v5)=1+1+2+2+0=mdeg-(v1)+ deg-(v2)+ deg-(v3) +deg-(v4)+ deg-(v5)=1+2+0+1+2=m6、奇结点、偶结

10、点、奇结点、偶结点偶结点：偶结点：奇结点：奇结点： 度数为奇数的结点度数为奇数的结点度数为偶数的结点度数为偶数的结点定理定理在任何图中，必有偶数个奇结点。在任何图中，必有偶数个奇结点。证明证明mvvjVvVviji2)(deg)(deg21)(deg2jVvvj)(deg1Vviiv图图G=|E|=mV1:V2:V中奇结点集合中奇结点集合V中偶结点集合中偶结点集合偶结点的度数之和偶结点的度数之和偶数偶数偶数偶数奇结点的度数之和奇结点的度数之和偶数偶数|V1|偶数偶数偶数个奇结点偶数个奇结点7、孤立结点、端点（悬挂点）、悬挂边、孤立结点、端点（悬挂点）、悬挂边图图G= vV(G)（1）孤立结点）

11、孤立结点:deg(v)=0（2）端点）端点:deg(v)=1悬挂点悬挂点（3）悬挂边）悬挂边: 与悬挂点关联的边与悬挂点关联的边孤立结点、悬挂点、悬挂边举例孤立结点、悬挂点、悬挂边举例V V5 5是是悬挂点；悬挂点；(v(v4 4,v,v5 5) )是是悬挂边悬挂边; ;V V6 6是孤立结点是孤立结点8、零图、平凡图、零图、平凡图、d度正则图、完全度正则图、完全图图G=: 简单无向图简单无向图（1）零图）零图: E=(n,0)图图（2）平凡图）平凡图:|V|=1 E=(1,0)图图（3）d度正则图度正则图: 每个结点的度均为每个结点的度均为d（4）完全图：）完全图： 任意两点间恰有一条边连接

12、任意两点间恰有一条边连接Kn举例举例9、图同构、图同构两个图两个图G=G=双射函数双射函数g：V V v iVg(vi)= vi (g(vi),g(vj) E（1）无向图）无向图:(vi, vj) E（2）有向图）有向图: E EG与与G同构同构解释解释（1）无向图）无向图:双射函数双射函数g:VV: 保持结点间的邻接关系保持结点间的邻接关系（2）有向图）有向图:双射函数双射函数g:VV:保持结点间的邻接关系保持结点间的邻接关系保持边的方向一致保持边的方向一致无向图同构举例无向图同构举例证明下面两个无向图同构。证明下面两个无向图同构。证明证明双射函数双射函数g:V V:g(vi)=vi(i=1

13、,2,3,4,5,6)(v1,v4) E(v1, v4) E(v1,v5) E(v1, v5) E(v1,v6) E(v1, v6) E(v2,v4) E(v2, v4) E(v2,v5) E(v2, v5) E(v2,v6) E(v2, v6) E(v3,v4) E(v3, v4) E(v3,v5) E(v3, v5) E(v3,v6) E(v3, v6) E有向图同构举例有向图同构举例证明下面两个有向图同构。证明下面两个有向图同构。证明证明双射函数双射函数g:V V:g(i)=vi (i=1,2,3,4) E E E E E E E E10、判断两个图同构的必要条件、判断两个图同构的必要条

14、件（1）结点数相同；）结点数相同；（2）边数相同；）边数相同；（3）度数相同的结点数相同度数相同的结点数相同。解释解释1）如果两个图同构，则）如果两个图同构，则(1)、(2)、(3)成立；成立；2）(1)、(2)、(3)成立两个图不一定同构；成立两个图不一定同构；3）如果）如果(1)、(2)、(3)不成立，则两个图一定不成立，则两个图一定不同构；不同构；定理应用举例定理应用举例判定以下两个有向图是否同构？判定以下两个有向图是否同构？证明证明(1)|V|=|V|=5(2)|E|=|E|=8(3)d+(1)=2结点1:结点a:d-(1)=2d(1)=4;d+(a)=2d-(a)=2d(a)=4;d

15、+(2)=1结点2:结点b:d-(2)=2d(2)=3;d+(b)=1d-(b)=2d(b)=3;d+(3)=2结点3:结点c:d-(3)=1d(3)=3;d+(c)=2d-(c)=1d(c)=3;d+(4)=1结点4:结点d:d-(4)=2d(1)=3;d+(d)=2d-(d)=1d(d)=3;d+(5)=2结点5:结点e:d-(5)=1d(5)=3;d+(e)=2d-(e)=1d(e)=3;证明（续）证明（续）双射函数双射函数g:V V:g(5)=eg(1)=ag(2)=bg(3)=cg(4)=d E E E E E E E E E E E E E E第第2节节 子图与图的运算子图与图的运

16、算一、子图一、子图二、图的运算二、图的运算一、子图一、子图1、子图、子图2、真子图、真子图3、生成子图、生成子图4、结点导出子图、结点导出子图5、边导出子图、边导出子图1、子图、子图两个图两个图G=G=V VE EG是是G的的子图子图2、真子图、真子图两个图两个图G=G=V VE EG是是G的的真子图真子图3、生成子图、生成子图两个图两个图G=G=V=VE EG是是G的的生成子图生成子图子图的举例子图的举例4 4、结点导出子图、结点导出子图G=V VVV为结点集合为结点集合起点和终点均在起点和终点均在V中的边的全体为边集合中的边的全体为边集合由由V导出的导出的G的子图的子图GVV V导出子图导

17、出子图GV-VG-V结点导出子图举例结点导出子图举例求求: :(1)(1)由结点集合由结点集合V V=a,b,d,e =a,b,d,e 导出的导出的G G的子图的子图Ga,b,d,eGa,b,d,e(2)G-a,d(2)G-a,d解答解答5 5、边导出子图、边导出子图G=E EEV=v| v V ( e)(e E v与与e关联关联)以以V为结点集合为结点集合以以E为边集为边集由由E导出的子图导出的子图边导出子图举例边导出子图举例求求: :由边集合由边集合E=eE=e1 1,e ,e2 2,e ,e5 5,e ,e7 7 导出的导出的G G的子图的子图GeGe1 1,e ,e2 2,e ,e5

18、5,e ,e7 7 解答解答二、图的运算二、图的运算1、可运算的、可运算的2、边不相交的、边不相交的3、点不相交的、点不相交的4、图的交、图的交5、图的并、图的并6、图的差、图的差7、图的环和、图的环和8、相对于图、相对于图G的补图的补图9、相对于完全图的补图、相对于完全图的补图1、可运算的、可运算的G1=G2=同为无向图或同为有向图同为无向图或同为有向图对任意的对任意的e E1E2 1(e)= 2(e)G1与与G2是可运算的是可运算的2、边不相交的、边不相交的G1=G2=同为无向图或同为有向图同为无向图或同为有向图G1与与G2是不相交的是不相交的E1E2 = V1V2 =G1与与G2是边不相

19、交是边不相交E1E2 = 3、点不相交的、点不相交的G1与与G2是点不相交的是点不相交的G1=G2=同为无向图或同为有向图同为无向图或同为有向图V1V2 =可运算的举例可运算的举例问：问： G G1 1和和G G2 2是否是可运算的？是否是可运算的？解答解答E1E2 =e1,e2,e5 1(e1)= (a,b) 2(e1)= (a,b) 1(e2)= (a,d) 2(e2)= (a,d) 1(e5)= (b,d) 2(e5)= (b,d)G1和和G2是可运算的是可运算的4、图的交、图的交G1=G2=是可运算的是可运算的V1V2为结点集为结点集E1E2为边集合为边集合G1和和G2的交的交G1G2

20、5、图的并、图的并G1=G2=是可运算的是可运算的V1 V2为结点集为结点集E1 E2为边集合为边集合G1和和G2的并的并G1 G26、图的差、图的差G1=G2=是可运算的是可运算的G1与与G2的差的差:在在G1中去掉中去掉G2的边所得到的图的边所得到的图G1 - G27、图的环和、图的环和G1=G2=是可运算的是可运算的V1 V2为结点集为结点集E1 E2为边集合为边集合G1和和G2的环和的环和G1 G2图运算的举例图运算的举例与如下图所示，求：与如下图所示，求：G G1 1G G2 2 G G1 1G G2 2 G G1 1- -G G2 2 G G2 2- -G G1 1 ， G G1

21、1 G G2 2 。G G1 1G G2 2V V1 1V V2 2E1 1E2 2=a,b,d= e1 1,e2 2,e5 5G G1 1G G2 2V V1 1V V2 2e1 1,e2 2,e3 3 , e4 4,e5 5,e6 6 ,e7 7 , e8 8,e9 9,e1010=a,b,c,d,eE1 1E2 2 =G G1 1 - -G G2 2G G2 2 G G1 1G G1 1 G G2 2E E1 1 E E2 2 =V V1 1V V2 2=a,b,c,d,ee3 3 , e4 4,e6 6 ,e7 7 , e8 8,e9 9,e10108、相对于图、相对于图G的补图的补图

22、G=的子图的子图:G=:给定另一个图给定另一个图G=（1）E E-E（2）V是是E中的边所关联的结点集合中的边所关联的结点集合G是子图是子图G的相对于图的相对于图G的补图的补图解释解释(1)EE (2)EE E(3) V仅是仅是E中的边所关联的结点集合，不中的边所关联的结点集合，不包含别的结点包含别的结点: GG G(4) G与与G的关系不是互逆的。的关系不是互逆的。相对补图的举例相对补图的举例图图G和图和图G 如下图所示如下图所示:求图求图G 相对于图相对于图G的补图。的补图。解答解答EEE-E= (a,e),(c,e),(d,e)V a,c,d,e图图G 相对于图相对于图G的补图为的补图为

23、GG相对于图相对于图G的补图为的补图为G 不是不是G没有结点没有结点e9、相对于完全图的补图、相对于完全图的补图补图是互逆的补图是互逆的给定一个图给定一个图GG中所有结点中所有结点能使能使G成为完全图所添加的边成为完全图所添加的边图图G相对于完全图的补图相对于完全图的补图G的补图的补图G补图举例补图举例求求G G1 1和和G G2 2的补图。的补图。解答解答解答解答第第3节节 路径、回路和连通性路径、回路和连通性一、路径一、路径二、连通性二、连通性一、路径一、路径1、路径、路径2、可达的、不可达的、可达的、不可达的1、路径、路径(1)路径路径(2)回路回路(3)简单路径、基本路径简单路径、基本

24、路径(1)路径路径路径是结点和边的路径是结点和边的交替序列交替序列图图G=v0,v1vn Ve1,e2en Eei:关联关联vi-1和和vi序列序列v0e1v1e2envn :从从v0到到vn的路的路路径路径路径的起点路径的起点路径的终点路径的终点路径的长度路径的长度: 路径中边的数目路径中边的数目(2)回路回路起点和终点为同一个结点的路径起点和终点为同一个结点的路径(3)简单路径、基本路径简单路径、基本路径简单路径简单路径:简单回路简单回路:基本路径基本路径:基本回路基本回路:边不重复的路径边不重复的路径边不重复的回路边不重复的回路点不重复的路径点不重复的路径点不重复的回路点不重复的回路路径

25、举例路径举例(1)AaAcBgChF:(2)AbDdEeBfChF:(3)AbDdEeBcA:从从A到到F的路径的路径长度为长度为4简单路径简单路径不是基本路径不是基本路径从从A到到F的路径的路径长度为长度为5简单路径简单路径 基本路径基本路径从从A到到A的回路的回路长度为长度为4简单回路简单回路 基本回路基本回路路径举例路径举例v1e2v2e3v3e4v4v4e1v1e2v2e3v3e4v4e1v1简单路径简单路径基本路径基本路径不是基本路径不是基本路径不是简单路径不是简单路径定理定理寻找基本路径的方法寻找基本路径的方法：v和和v是图是图G中的结点中的结点存在从存在从v到到v的路径的路径存在

26、从存在从v到到v的基本路径的基本路径从路径中去掉所有的回路从路径中去掉所有的回路证明证明从从v到到v存在路径存在路径P vv : v0e1v1e2elvlvv若若Pvv不是基本路径不是基本路径结点结点vi在该路径中不止一次出现在该路径中不止一次出现v0e1v1e2eivi ei+1 ejvjej+1elvlvi=vj在该路径中去掉从在该路径中去掉从vi到到vj的边的边v0e1v1e2eiviej+1elvl从从v0到到vl的路径的路径如此反复去掉所有的回路如此反复去掉所有的回路从从v0到到vl的基本路径的基本路径定理应用举例定理应用举例(1)ae2be10de9ae2be4c:(2)ae1ae

27、2be4c:求从求从a到到c的基本路径的基本路径是从是从a到到c的一条路径的一条路径,是从是从a到到c的一条路径的一条路径,求从求从a到到c的基本路径的基本路径解答解答(1)ae2be10de9ae2be4c:不是基本路径不是基本路径去掉回路去掉回路ae2be10de9aae2be4c基本路径基本路径(2)ae1ae2be4c:不是基本路径不是基本路径去掉回路去掉回路ae1aae2be4c基本路径基本路径定理定理n阶图中的基本路径的长度小于阶图中的基本路径的长度小于n。证明证明基本路径基本路径:点不重复的路径点不重复的路径在一个基本路径中有在一个基本路径中有l个不同的结点个不同的结点 v0,v

28、1,vl-1有有l-1条边条边:e1,e2,el-1v0e1v1e2el-1vl-1基本路径基本路径n阶图阶图: 有有n个不同的结点个不同的结点最多有最多有n-1条边出现在基本路径上条边出现在基本路径上n阶图中的基本路径的长度小于阶图中的基本路径的长度小于n2、可达的、不可达的、可达的、不可达的v1,v2:图图G中的结点中的结点存在从存在从v1到到v2的路径的路径从从v1到到v2 是可达的是可达的否则否则:从从v1到到v2不可达不可达v1可达可达v2 在无向图中在无向图中:在有向图中在有向图中:v2可达可达v1 V2不一定不一定可达可达v1 二、连通性二、连通性1、连通图、连通图2、基础图、基

29、础图3、强连通、单向连通、弱连通、强连通、单向连通、弱连通4、极大子图、极大子图5、分支、分支1、连通图、连通图G:无向图无向图任意两个结点都相互可达任意两个结点都相互可达连通图连通图否则否则:G是非连通图是非连通图2、基础图、基础图把每条把每条有向边改为无向边有向边改为无向边而得到的无向图而得到的无向图有向图的基础图有向图的基础图3、强连通、单向连通、弱连通、强连通、单向连通、弱连通G:有向图有向图(1)强连通图强连通图: 任意两结点均互相可达任意两结点均互相可达(2)单向（侧）连通图单向（侧）连通图:任意两结点必有一结点可达另一个结点任意两结点必有一结点可达另一个结点(3)弱连通图弱连通图

30、: G的基础图是连通的的基础图是连通的连通性举例连通性举例判断图判断图G G1 1,G,G2 2,G,G3 3是强连通图、单向连通是强连通图、单向连通图还是弱连通图？图还是弱连通图？解答解答v2不可达不可达v3v3也不可达也不可达v2G1不是单向连通图不是单向连通图G1的基础图是连通图的基础图是连通图 G1是弱连通图是弱连通图解答解答v1可达可达v3v3不可达不可达v1G2不是强连通图不是强连通图v2可达可达v3v2可达可达v1G2是单向连通图是单向连通图解答解答v1可达可达v2v2可达可达v1v1可达可达v3v3可达可达v1v2可达可达v3v3可达可达v2G3是强连通图是强连通图4、极大子图

31、、极大子图G:G的子图的子图G具有连通性具有连通性对于对于G的任意的具有连通性的子图的任意的具有连通性的子图GG GG=GG是是G的极大的极大 连通连通 子图子图强连通性强连通性强连通性强连通性强连通强连通单向连通性单向连通性单向连通性单向连通性单向连通单向连通弱连通性弱连通性弱连通性弱连通性弱连通弱连通5、分支、分支无向图无向图G的极大连通子图的极大连通子图 G的分支（分图）的分支（分图）:G的强分支（强分图）的强分支（强分图）:有向图有向图G的极大强连通子图的极大强连通子图G的单向分支（单向分图）的单向分支（单向分图）:有向图有向图G的极大单向连通子图的极大单向连通子图G的弱分支（弱分图）

32、的弱分支（弱分图）:有向图有向图G的极大弱连通子图的极大弱连通子图定理定理连通无向图恰有一个分支连通无向图恰有一个分支非连通无向图有一个以上的分支非连通无向图有一个以上的分支举例举例图图G G是一个连通无向图是一个连通无向图其只有一个极大连通子图，就是其本身其只有一个极大连通子图，就是其本身G G。举例举例图图G G是一个非连通无向图是一个非连通无向图其有两个极大连通子图其有两个极大连通子图G1G1和和G2G2。定理定理强强 连连 通有向图恰有一个通有向图恰有一个 强强 分支分支非非 强强 连连 通通 有向图有一个以上的有向图有一个以上的 强强 分支分支单向连通单向连通单向分支单向分支单向连通

33、单向连通单向分支单向分支弱连通弱连通弱连通弱连通弱分支弱分支弱分支弱分支定理定理G=:简单有向图简单有向图每一个结点都每一个结点都恰恰处于一个强分支中处于一个强分支中分支举例分支举例求求G G1 1、G G2 2的强分支、单向分支、弱分支。的强分支、单向分支、弱分支。解答解答解答解答定理定理无向图无向图G（连通或不连通）恰有两个奇结点（连通或不连通）恰有两个奇结点必有连接此两结点的路径必有连接此两结点的路径证明证明设设G中的两个奇结点是中的两个奇结点是v1和和v2(1)若若G是连通图，则是连通图，则v1和和v2之间必有路径；之间必有路径；(2)若若G是非连通图，则是非连通图，则G至少有两个以上

34、的至少有两个以上的分支分支因为，在任何一个图中因为，在任何一个图中必有偶数个奇结点必有偶数个奇结点所以：所以：v1和和v2必处于同一个分支中，即：必处于同一个分支中，即：V1和和v2之间必有路径。之间必有路径。第第4节节 图的矩阵表示图的矩阵表示一、邻接矩阵一、邻接矩阵二、可达性矩阵二、可达性矩阵三、完全关联矩阵三、完全关联矩阵一、邻接矩阵一、邻接矩阵1、简单无向图的邻接矩阵、简单无向图的邻接矩阵2、简单有向图的邻接矩阵、简单有向图的邻接矩阵3、矩阵、矩阵AAT4、矩阵、矩阵ATA5、矩阵、矩阵Am1、简单无向图的邻接矩阵、简单无向图的邻接矩阵G:简单无向图简单无向图n阶方阵阶方阵 A=(ai

35、j)nnV=v1,v2,vn邻接矩阵邻接矩阵:aij=(vi,vj) E10否则否则邻接矩阵举例邻接矩阵举例写出简单无向图写出简单无向图G G对应的邻接矩阵对应的邻接矩阵A A。A=abcdea b c de1111 111111111100000000000简单无向图邻接矩阵的特点简单无向图邻接矩阵的特点(1)主对角线均为主对角线均为0的的对称阵；对称阵；(2)每一行（列）中每一行（列）中“1”的个数的个数是该行所对应的结是该行所对应的结点的点的度度；(3)所有元素所有元素均为均为“0”的邻接矩阵对应的是的邻接矩阵对应的是零图零图;(4)除主对角线外所有元素均为除主对角线外所有元素均为“1”

36、的邻接矩阵对的邻接矩阵对应的是应的是完全图完全图。2、简单有向图的邻接矩阵、简单有向图的邻接矩阵G:简单有向图简单有向图n阶方阵阶方阵 A=(aij)nnV=v1,v2,vn邻接矩阵邻接矩阵:aij= E10否则否则邻接矩阵举例邻接矩阵举例写出简单有向图写出简单有向图G G对应的邻接矩阵对应的邻接矩阵A A。A=v1v2v3v4v1v2v3v4010 1111010100000简单有向图邻接矩阵的特点简单有向图邻接矩阵的特点(1)不一定是对称阵；不一定是对称阵；(2)每一行中每一行中“1”的个数的个数是该行所对应的结点的是该行所对应的结点的出度出度；(3)每一列中每一列中“1”的个数的个数是该

37、列所对应的结点的是该列所对应的结点的入度入度；(4)第第i行中行中“1”的个数与第的个数与第i列中列中“1”的个数之和，恰的个数之和，恰为记点为记点vi的度。的度。3、矩阵、矩阵AATA:有向图有向图G的邻接矩阵的邻接矩阵AT:A的转置矩阵的转置矩阵A=(aij)nnB= AAT=(bij)nnbij =A=vivjai1aija1jainanjAT=a1iajiaj1aniajnai1 aj1+ ai2 aj2+ + ain ajn解释解释aik1ajk1aikajk1为为bij的求和中的值增加的求和中的值增加1aik1ajk1 E Evkvjvi由由vi,vj引出的边共同地终止于结点引出的

38、边共同地终止于结点vk1n矩阵矩阵AAT的特点的特点（1）矩阵）矩阵AAT中的第中的第i行第行第j列的记入值列的记入值bij，等于从等于从vi和和vj引出的边能引出的边能共同地终止于不同共同地终止于不同结点的数目结点的数目；（2）对角线上的记入值即为结点）对角线上的记入值即为结点vi的的出度出度。矩阵矩阵AAAAT T的举例的举例已知简单有向图已知简单有向图G G的邻接矩阵的邻接矩阵A A，求：求：矩阵矩阵AAAAT T，并指出各记入值的含义。，并指出各记入值的含义。解答解答AAT=v1v2v3v4v1v2v3v4112 0200012011103b11=1:v1的出度为的出度为1b22=2:

39、v2的出度为的出度为2b33=3:v3的出度为的出度为3b44=1:v4的出度为的出度为1b12=1:从从v1和和v2引出的边引出的边能共同地终止于能共同地终止于1个个结点结点v4b23=2:从从v2和和v3引出的边引出的边能共同地终止于能共同地终止于2个个结点结点v1,v44、矩阵、矩阵ATAnnijTbAAB)(ijbA:有向图有向图G的邻接矩阵的邻接矩阵AT:A的转置矩阵的转置矩阵A=(aij)nn=a1i a1j+ a2i a2j+ + ani anjviAT=a1iajiaj1aniajnA=vjai1aija1jainanj矩阵矩阵ATA的特点的特点（1）矩阵）矩阵ATA中的第中的

40、第i行第行第j列的记入值，等列的记入值，等于从图于从图G中其它结点引出的边中其它结点引出的边共同地终止共同地终止于于vi和和vj的结点的数目的结点的数目；（2）矩阵）矩阵ATA中对角线上的记入值即为结中对角线上的记入值即为结点点vi的的入度入度。矩阵矩阵A AT TA A的举例的举例已知简单有向图已知简单有向图G G的邻接矩阵的邻接矩阵A A，求：求：矩阵矩阵A AT TA A，并指出各记入值的含义。，并指出各记入值的含义。解答解答11b22b33b44b12b14bATA=v1v2v3v4v1v2v3v4110 1000101202321=2:v1的入度为的入度为2=1: v2的入度为的入度

41、为1=1: v3的入度为的入度为1=3: v4的入度为的入度为3=1:有一个结点引出的边能共同地终止于从有一个结点引出的边能共同地终止于从v1和和v2v3=2:有两个结点引出的边能共同地终止于从有两个结点引出的边能共同地终止于从v1和和v4v2,v35、矩阵、矩阵A2A:有向图有向图G的邻接矩阵的邻接矩阵A2=AA=(aij)nn (aij)nn= (aij(2)nnA=vivjai1aija1jainanj=ai1 a1j+ ai2 a2j+ + ain anj解释：解释：有一条从有一条从vi经经vk终止于终止于vj的长度为的长度为2的路径的路径aik1akj1aikakj1vivjvk矩阵

42、矩阵Am的特点的特点aij(2):从从vi到到vj长度为长度为2的路径数目的路径数目aii(2):起始于起始于vi又终止于又终止于vi的长度为的长度为2的回路的数目的回路的数目aij(m): 从从vi到到vj长度为长度为m的路径数目的路径数目aii(m):起始于起始于vi又终止于又终止于vi的长度为的长度为m的回路的数目的回路的数目矩阵矩阵A Amm的举例的举例求图求图G G的的A A2 2和和A A3 3, ,并说明其中个数据的含义。并说明其中个数据的含义。解答解答A2=v1v2v3v4v1v2v3v4001 1020110010111a13(2)=1: 从从v1到到v3长度为长度为2的路径

43、有的路径有1条条v1v4v3a23(2)=1: 从从v2到到v3长度为长度为2的路径有的路径有1条条v2v4v3a33(2)=1: 从从v3到到v3长度为长度为2的回路有的回路有1条条v3v4v3a44(2)=1: 从从v4到到v4长度为长度为2的回路有的回路有1条条v4v3v4解答解答A3=v1v2v3v4111 1121011101212a12(3)=1: 从从v1到到v2长度为长度为3的路径有的路径有1条条v1v4v3a23(3)=1: 从从v2到到v3长度为长度为3的路径有的路径有1条条v2v4v3a22(3)=1: 从从v2到到v2长度为长度为3的回路有的回路有1条条v2v4v2a1

44、1(3)=1: 从从v1到到v1长度为长度为3的回路有的回路有1条条v4v3v1v2v1v1v1v1v2v3v4定理定理G=: 简单有向图简单有向图V=v1,v2,vnA:G的邻接矩阵的邻接矩阵矩阵矩阵Am中的元素中的元素aij(m):从从vi到到vj长度为长度为m的路径数目的路径数目证明证明对对m进行归纳证明：进行归纳证明：(1)当当m=1时，时，Am=A，根据邻接矩阵的定，根据邻接矩阵的定义显然成立；义显然成立；(2)假设假设m=k时成立；时成立；(3)证明证明m=k+1时也成立时也成立证明（续）证明（续）aij(k)从从vi到到vj长度为长度为k的路径数目的路径数目Ak+1= AkA=a

45、i1(k)a1j+ ai2(k)a2j+ aih(k)ahj+ + ain(k)anj aih(k)从从vi到到vh长度为长度为k的路径数目的路径数目ahj从从vh到到vj长度为长度为1的路径数目的路径数目aih(k)ahj从从vi经经vh到到vj长度为长度为k+1的路径数目的路径数目对所有对所有h求和求和:aij(k+1)从从vi到到vj长度为长度为k+1的路径总数的路径总数 m=k+1时成立时成立举例举例求图求图G G的的A A2 2、A A3 3和和A A4 4 , ,并说明其中个数并说明其中个数据的含义。据的含义。解答解答a13(2)=1: 从从v1到到v3长度为长度为2的路径有的路径

46、有1条条v1 v2 v3a31(2)=1: 从从v3到到v1长度为长度为2的路径有的路径有1条条v3 v2 v1a33(2)=1: 从从v3到到v3长度为长度为2的路径有的路径有1条条v3 v2 v3a44(2)=1: 从从v4到到v4长度为长度为2的路径有的路径有1条条v4 v5 v4解答解答a12(3)=2: 从从v1到到v2长度为长度为3的路径有的路径有2条条v1 v2 v3 v2v1 v2 v1 v2a23(3)=2: 从从v2到到v3长度为长度为3的路径有的路径有2条条v2 v1 v2 v3v2 v3 v2 v3a45(3)=1:从从v4到到v5长度为长度为3的路径有的路径有1条条v

47、4 v5 v4 v5主对角线元素均为主对角线元素均为0不存在长度为不存在长度为3的回路的回路解答解答a13(4)=2: 从从v1到到v3长度为长度为4的路径有的路径有2条条a11(4)=2: 从从v1到到v1长度为长度为4的回路有的回路有2条条v1 v2 v3 v2 v3v1 v2 v1 v2 v3v1 v2 v3 v2 v1v1 v2 v3 v2 v1二、可达性矩阵二、可达性矩阵1、可达性矩阵可达性矩阵P2、求可达性矩阵、求可达性矩阵P的方法的方法1、可达性矩阵可达性矩阵PG:简单有向图简单有向图V=v1,v2,vnn阶方阵阶方阵 P=(pij)nnG的可达性矩阵的可达性矩阵pij=10从从

48、vi到到vj至少存在一条路径至少存在一条路径否则2、求可达性矩阵、求可达性矩阵P的方法的方法(1)回忆两个定理回忆两个定理(2)求可达性矩阵求可达性矩阵P的方法的方法(1)回忆两个定理回忆两个定理n若存在从若存在从vi到到vj的路径，则存在从的路径，则存在从vi到到vj的的基本路径；基本路径；nn阶图的基本路径长度小于阶图的基本路径长度小于n;(2)求可达性矩阵求可达性矩阵P的方法的方法A：aij表示表示从从vi到到vj长度为长度为1的路径的数目；的路径的数目；A2:aij(2)表示从表示从vi到到vj长度为长度为2的路径的数目；的路径的数目；An:aij(n)表示从表示从vi到到vj长度为长

49、度为n的路径的数目；的路径的数目；令：令：Bn=A+A2+An 其中：其中： Bn中第中第i行第行第j列的记入值列的记入值bij表明：从表明：从vi到到vj长度长度小于或等于小于或等于n的路径的数目的路径的数目若若bij 0，则表明从，则表明从vi到到vj可达。可达。求可达性矩阵求可达性矩阵P的方法（续）的方法（续）A:简单有向图简单有向图G的邻接矩阵的邻接矩阵（1）A2=AAA3=A2A ,An=An-1A（2）P= AA2An求可达性矩阵求可达性矩阵P P举例举例求图求图G G的邻接矩阵的邻接矩阵A A及可达性矩阵及可达性矩阵P P。A=v1v2v3v41001000010000000v1

50、v2v3v4v5v5000100001解答（续）解答（续）A=v1v2v3v4100 1000010000000v1v2v3v4v5v5000100 0 01解答（续）解答（续）由可达性矩阵由可达性矩阵P P可知：可知：v v1 1到到v v2 2,v,v4 4,v,v5 5可达；可达；v v2 2到到v v2 2,v,v4 4,v,v5 5可达；可达；v v3 3到到v v1 1 , v , v2 2,v,v4 4,v,v5 5可达；可达； v v4 4到到v v2 2,v,v4 4,v,v5 5可达；可达；v v5 5到到v v2 2,v,v4 4,v,v5 5可达；可达；三、完全关联矩阵

51、：三、完全关联矩阵：1、无向图的完全关联矩阵、无向图的完全关联矩阵2、有向图的完全关联矩阵、有向图的完全关联矩阵1、无向图的完全关联矩阵、无向图的完全关联矩阵G:无向图无向图V=v1,v2,vnE=e1,e2,emAe= (aij)nm图图G的完全关联矩阵的完全关联矩阵aij=10vi关联关联ej否则无向图的完全关联矩阵举例无向图的完全关联矩阵举例求无向图求无向图G G的完全关联矩阵的完全关联矩阵A AeAe=v1v2v3v41110111000001100e1e2e3e4e51001无向图的完全关联矩阵的特点无向图的完全关联矩阵的特点（1）每一）每一列列中只有中只有两个两个“1”；（2）每一

52、）每一行行中中“1”的个数的个数是该结点的是该结点的度度数；数；（3）若某）若某行行中的元素中的元素均为均为“0”，则该行所，则该行所对应的结点是对应的结点是孤立结点孤立结点；（4）平行边平行边所对应的所对应的两列相同两列相同；2、有向图的完全关联矩阵、有向图的完全关联矩阵G:有向图有向图V=v1,v2,vn E=e1,e2,emAe= (aij)nm图图G的完全关联矩阵的完全关联矩阵aij=10vi是是ej的起点的起点-1vi是是ej的终点的终点Vi与与ej不关联不关联有向图的完全关联矩阵举例有向图的完全关联矩阵举例求有向图求有向图G G的完全关联矩阵的完全关联矩阵AeAeAe=v1v2v3

53、v4-1-10-111000001100-1e1e2e3e4e501-10v5e61-1000000 0 0有向图的完全关联矩阵的特点有向图的完全关联矩阵的特点（1）每）每列列元素元素之和为之和为“0”；（2）每一）每一行行中中“1”的个数的个数是该行所对应结是该行所对应结点的点的出度出度；（3）每一）每一行行中中“-1”的个数的个数是该行所对应结是该行所对应结点的点的入度入度；（4）全为全为“0”的行的行所对应的结点为所对应的结点为孤立结孤立结点点。第第5节节 欧拉图和哈密顿图欧拉图和哈密顿图一、欧拉图一、欧拉图二、哈密顿图二、哈密顿图一、欧拉图一、欧拉图1、欧拉路径、欧拉路径2、欧拉回路、

54、欧拉回路3、欧拉图、欧拉图4、有向欧拉图、有向欧拉图欧拉图的起源1、欧拉路径、欧拉路径G:无孤立结点的无向图无孤立结点的无向图经过图中每条边一次且仅一次路径经过图中每条边一次且仅一次路径欧拉路径欧拉路径:2、欧拉回路、欧拉回路G:无孤立结点的无向图无孤立结点的无向图欧拉回路欧拉回路:经过图中每条边一次且仅一次回路经过图中每条边一次且仅一次回路3、欧拉图、欧拉图具有具有欧拉回路欧拉回路的图叫欧拉图。的图叫欧拉图。欧拉图举例欧拉图举例判断图判断图G1和和G2是否是欧拉图？是否是欧拉图？解答解答G G1 1：欧拉回路欧拉回路1234563726781欧拉图欧拉图G G2 2：125462341欧拉回

55、路欧拉回路欧拉图欧拉图定理定理无向连通图无向连通图G G是欧拉图是欧拉图G的的每个结点均为偶结点每个结点均为偶结点哥尼斯堡七桥问题哥尼斯堡七桥问题deg(Adeg(A)=deg(B)=deg(D)=3)=deg(B)=deg(D)=3，deg(Cdeg(C)=5)=5哥尼斯堡七桥问题无解。哥尼斯堡七桥问题无解。欧拉图应用举例欧拉图应用举例环卫工人清扫街道，清扫路线如图所示，试环卫工人清扫街道，清扫路线如图所示，试问是否存在清扫路线问是否存在清扫路线使环卫工人从使环卫工人从V V1 1出发通过出发通过所有路线而不重复且最后所有路线而不重复且最后回到回到V V1 1。 解答解答由于图中每个结点均为

56、偶次数，故由定理可知这样由于图中每个结点均为偶次数，故由定理可知这样的一条清扫路线是存在的。的一条清扫路线是存在的。 (v1, v5, v11, v7, v12, v8, v10, v6, v9, v11, v12, v10, v9, v5, v2, v6, v4, v8, v3, v7, v1)deg(vdeg(v1 1)=deg(v)=deg(v2 2)=deg(v)=deg(v3 3)= deg(v)= deg(v4 4)= 2)= 2，deg(vdeg(v5 5)=deg(v)=deg(v6 6)=deg(v)=deg(v7 7)=deg(v)=deg(v8 8)=deg(v)=deg

57、(v9 9) )=deg(v=deg(v1010)=deg(v)=deg(v11 11)= deg(v)= deg(v1212)= 4)= 4定理定理无向连通图无向连通图G中结点中结点vi与与vj间存在间存在欧拉路径欧拉路径vi与与vj的度数均为奇数的度数均为奇数其它结点的度数均为偶数其它结点的度数均为偶数定理应用举例定理应用举例一笔画问题：一笔画问题：判别图判别图(1)(1)、(2)(2)是否可以一笔画。是否可以一笔画。解答解答图图(1)A、B为奇结点为奇结点C,D,E为偶结点为偶结点欧拉路径欧拉路径:AEDCBECAB解答解答图图(2)A、B为奇结点为奇结点其余各点为偶结点其余各点为偶结点

58、A与与B两点间存在欧拉路径，即两点间存在欧拉路径，即从从A到到B可以一笔画。可以一笔画。定理应用举例定理应用举例判断图（判断图（3 3）是否可以一笔画）是否可以一笔画 。A,B,C,D均为奇结点均为奇结点图图(3)中无欧拉路径，中无欧拉路径，因此不可以一笔画。因此不可以一笔画。4、有向、有向欧拉图欧拉图G:有向图有向图经过图中每条边一次且仅一次的有向路径经过图中每条边一次且仅一次的有向路径有向欧拉路径有向欧拉路径:有向欧拉回路有向欧拉回路:经过图中每条边一次且仅一次的有向回路经过图中每条边一次且仅一次的有向回路有向欧拉图有向欧拉图:有有向欧拉回路的有向图有有向欧拉回路的有向图定理定理一个连通有

59、向图一个连通有向图G是有向欧拉图是有向欧拉图对对G中的所有结点中的所有结点v,有：有：d +(v)=d-(v)有向欧拉图举例有向欧拉图举例判断图判断图G G1 1和和G G2 2是否为有向欧拉图，如果是否为有向欧拉图，如果是，请给出有向欧拉回路。是，请给出有向欧拉回路。图图G1图图G2解答解答d d+ +(v(v1 1)=d)=d- -(v(v1 1)=1)=1d d+ +(v(v2 2)=d)=d- -(v(v2 2)=2)=2d d+ +(v(v3 3)=d)=d- -(v(v3 3)=1)=1d d+ +(v(v4 4)=d)=d- -(v(v4 4)=2)=2d d+ +(v(v5 5

60、)=d)=d- -(v(v5 5)=2)=2是有向欧拉图是有向欧拉图有向欧拉回路有向欧拉回路:v1e1v2e3v4e7v5e5v1e6v4e8v5e4v3e2v1解答解答d d+ +(v(v4 4)=1)=1 d d- -(v(v4 4)=3)=3d d+ +(v(v5 5)=3)=3 d d- -(v(v5 5)=1)=1不是有向欧拉图不是有向欧拉图定理定理G:连通有向图连通有向图G中两个结点中两个结点vi和和vjvi的出度比入度大的出度比入度大1vj的出度比入度小的出度比入度小1其它结点的出度和入度相等其它结点的出度和入度相等G中存在从中存在从vi到到vj的有向欧拉路径的有向欧拉路径二、哈