图论图基本概念.pptx

《图论图基本概念.pptx》由会员分享，可在线阅读，更多相关《图论图基本概念.pptx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论图论(t ln)图基本概念图基本概念 第一页，共21页。3 3 3 3、邻接、邻接、邻接、邻接 (1)(1)(1)(1)边的相邻：边的相邻：边的相邻：边的相邻：ekekekek，elEelEelEelE若若若若ekekekek与与与与elelelel至少有一个公共端点，则称至少有一个公共端点，则称至少有一个公共端点，则称至少有一个公共端点，则称ekekekek与与与与elelelel是相邻的是相邻的是相邻的是相邻的 (2)(2)(2)(2)顶点的相邻：顶点的相邻：顶点的相邻：顶点的相邻：若若若若 etEetEetEetE，使得，使得，使得，使得et=viet=viet=viet=vjvjv

2、j，并称并称并称并称vivivivi邻接到邻接到邻接到邻接到vjvjvjvj，vjvjvjvj邻接于邻接于邻接于邻接于vi vi vi vi 两个结点为一条边的端点，则称两个结点互为邻接点两个结点为一条边的端点，则称两个结点互为邻接点两个结点为一条边的端点，则称两个结点互为邻接点两个结点为一条边的端点，则称两个结点互为邻接点4 4 4 4、平行边：、平行边：、平行边：、平行边：在无向图中，关联一对顶点的无向边如果多于在无向图中，关联一对顶点的无向边如果多于在无向图中，关联一对顶点的无向边如果多于在无向图中，关联一对顶点的无向边如果多于1 1 1 1条，则称这些边为平行边，平行条，则称这些边为平

3、行边，平行条，则称这些边为平行边，平行条，则称这些边为平行边，平行边的条数称为重数边的条数称为重数边的条数称为重数边的条数称为重数(zhn sh)(zhn sh)(zhn sh)(zhn sh)在有向图中，关联一对顶点的有向边如果多于在有向图中，关联一对顶点的有向边如果多于在有向图中，关联一对顶点的有向边如果多于在有向图中，关联一对顶点的有向边如果多于1 1 1 1条，并且这些边的始点与终点条，并且这些边的始点与终点条，并且这些边的始点与终点条，并且这些边的始点与终点相同相同相同相同(也就是它们的方向相同也就是它们的方向相同也就是它们的方向相同也就是它们的方向相同)，则称这些边为平行边，则称这

4、些边为平行边，则称这些边为平行边，则称这些边为平行边 5 5 5 5、多重图和简单图：含平行边的图称为多重图、多重图和简单图：含平行边的图称为多重图、多重图和简单图：含平行边的图称为多重图、多重图和简单图：含平行边的图称为多重图 既不含平行边也不含环的图称为简单图既不含平行边也不含环的图称为简单图既不含平行边也不含环的图称为简单图既不含平行边也不含环的图称为简单图二、结点的度二、结点的度二、结点的度二、结点的度 1 1 1 1）定义）定义）定义）定义4 4 4 4 设设设设G G G GVVVEEE为无向图，为无向图，为无向图，为无向图，v V v V v V v V，称，称，称，称v v v

5、 v作为边的端点次数之和为作为边的端点次数之和为作为边的端点次数之和为作为边的端点次数之和为v v v v的度的度的度的度数，简记为度记作数，简记为度记作数，简记为度记作数，简记为度记作d G(v)d G(v)d G(v)d G(v)，简记为简记为简记为简记为d(v)d(v)d(v)d(v)即为：结点即为：结点即为：结点即为：结点v v v v 所关联的边的总条数所关联的边的总条数所关联的边的总条数所关联的边的总条数 关于有向图关于有向图关于有向图关于有向图D D D DVVV E E E 有：有：有：有：v Vv Vv Vv V，称，称，称，称v v v v 作为边的始点的次数之和为作为边的

6、始点的次数之和为作为边的始点的次数之和为作为边的始点的次数之和为v v v v的出度，记作的出度，记作的出度，记作的出度，记作d+(v)d+(v)d+(v)d+(v)，称称称称v v v v作为边的终点的次数之和为作为边的终点的次数之和为作为边的终点的次数之和为作为边的终点的次数之和为v v v v的入度，记作的入度，记作的入度，记作的入度，记作d-(v)d-(v)d-(v)d-(v)，称称称称d+(v)+d-(v)d+(v)+d-(v)d+(v)+d-(v)d+(v)+d-(v)为为为为 v v v v的度数，记作的度数，记作的度数，记作的度数，记作d(v)d(v)d(v)d(v)2 2 2

7、 2）度为偶数）度为偶数）度为偶数）度为偶数(奇数奇数奇数奇数)的顶点称为偶度的顶点称为偶度的顶点称为偶度的顶点称为偶度(奇度奇度奇度奇度)顶点顶点顶点顶点 第1页/共21页第二页，共21页。3 3 3 3、握手定理（欧拉）、握手定理（欧拉）、握手定理（欧拉）、握手定理（欧拉）1)1)1)1)定理定理定理定理1 1 1 1 设设设设G G G G为任意为任意为任意为任意(rny)(rny)(rny)(rny)无向图无向图无向图无向图,V,V,V,Vv1v1v1v1，v2v2v2v2，vn,vn,vn,vn,E E E E=m=m=m=m，则则则则 d(vi)d(vi)d(vi)d(vi)2 m

8、 (2 m (2 m (2 m (所有结点的度数值和为边数的所有结点的度数值和为边数的所有结点的度数值和为边数的所有结点的度数值和为边数的2 2 2 2倍倍倍倍)2)2)2)2)定理定理定理定理2 2 2 2 设设设设D D D D为任意为任意为任意为任意(rny)(rny)(rny)(rny)有向图有向图有向图有向图,V,V,V,Vv1v1v1v1，v2v2v2v2，vn,|E|=m vn,|E|=m vn,|E|=m vn,|E|=m，则则则则 d+(vi)d+(vi)d+(vi)d+(vi)d-(vi)=m d-(vi)=m d-(vi)=m d-(vi)=m 且且且且d(vi)d(vi

9、)d(vi)d(vi)2 m2 m2 m2 m3)3)3)3)推论推论推论推论 任何图任何图任何图任何图(无向的或有向的无向的或有向的无向的或有向的无向的或有向的)中，奇度顶点的个数是偶数中，奇度顶点的个数是偶数中，奇度顶点的个数是偶数中，奇度顶点的个数是偶数4)4)4)4)结点的度数序列结点的度数序列结点的度数序列结点的度数序列 (1)(1)(1)(1)设设设设G G G GVVVEEE为一个为一个为一个为一个n n n n阶无向图，阶无向图，阶无向图，阶无向图，V V V Vv1v1v1v1，v2v2v2v2，vnvnvnvn 称称称称d(v1)d(v1)d(v1)d(v1)，d(v2)d

10、(v2)d(v2)d(v2)，d(vn)d(vn)d(vn)d(vn)为为为为G G G G的度数列的度数列的度数列的度数列 条件：奇度数的结点个数应该是偶数个条件：奇度数的结点个数应该是偶数个条件：奇度数的结点个数应该是偶数个条件：奇度数的结点个数应该是偶数个 （2 2 2 2）序列的可图化：）序列的可图化：）序列的可图化：）序列的可图化：d=(d1,d2,dn)d=(d1,d2,dn)d=(d1,d2,dn)d=(d1,d2,dn)对一个整数序列对一个整数序列对一个整数序列对一个整数序列d,d,d,d,若存在以若存在以若存在以若存在以n n n n个顶点的个顶点的个顶点的个顶点的n n n

11、 n阶无向图阶无向图阶无向图阶无向图G G G G，有，有，有，有d(vi)=di d(vi)=di d(vi)=di d(vi)=di 称该序列是可图化的称该序列是可图化的称该序列是可图化的称该序列是可图化的（3 3 3 3）定理）定理）定理）定理 设非负整数列设非负整数列设非负整数列设非负整数列d d d d(d1(d1(d1(d1，d2d2d2d2，dn)dn)dn)dn)，则，则，则，则d d d d是可图化的当且仅当是可图化的当且仅当是可图化的当且仅当是可图化的当且仅当 di=0(mod 2)(di=0(mod 2)(di=0(mod 2)(di=0(mod 2)(序列之和必须是偶数

12、序列之和必须是偶数序列之和必须是偶数序列之和必须是偶数)（4 4 4 4）由于简单图中没有平行边及环）由于简单图中没有平行边及环）由于简单图中没有平行边及环）由于简单图中没有平行边及环 结论：结论：结论：结论：n n n n个结点的简单图中结点的最大度数（个结点的简单图中结点的最大度数（个结点的简单图中结点的最大度数（个结点的简单图中结点的最大度数（G)G)G)G)）应小于等于）应小于等于）应小于等于）应小于等于n-1n-1n-1n-1 每个结点至多与其他每个结点至多与其他每个结点至多与其他每个结点至多与其他n-1n-1n-1n-1个结点相邻个结点相邻个结点相邻个结点相邻第2页/共21页第三页

13、，共21页。三、图的同构三、图的同构三、图的同构三、图的同构定义定义定义定义 设设设设G1G1G1G1VlVlVl E1 E1 E1，G2=V2G2=V2G2=V2G2=E2E2E2为两个无向图为两个无向图为两个无向图为两个无向图(两个有向图两个有向图两个有向图两个有向图)，若存在双射函数若存在双射函数若存在双射函数若存在双射函数f f f f：V1 V2 V1 V2 V1 V2 V1 V2 顶点的一一对应顶点的一一对应顶点的一一对应顶点的一一对应 对于对于对于对于 vi vi vi vi，vjV1vjV1vjV1vjV1，(vi(vi(vi(vi，vj)E1(vivj)E1(vivj)E1(

14、vivj)E1(E1)vj E1)vj E1)vj E1)当且仅当当且仅当当且仅当当且仅当(f(vi)(f(vi)(f(vi)(f(vi)，f(vj)E2(f(vi)f(vj)E2(f(vi)f(vj)E2(f(vi)f(vj)E2(E2)f(vj)E2)f(vj)E2)f(vj)E2)，边的对应边的对应边的对应边的对应 并且并且并且并且(vi(vi(vi(vi，vj)()vj)()vj)()vj)()与与与与(f(vi),f(vj)()(f(vi),f(vj)()(f(vi),f(vj)()(f(vi),f(vj)()的重数相同，的重数相同，的重数相同，的重数相同，则称则称则称则称G1G1G

15、1G1与与与与G2G2G2G2是同构的，记作是同构的，记作是同构的，记作是同构的，记作Gl Gl Gl Gl G2 G2 G2 G2 注：注：注：注：1)1)1)1)互为同构的两个图（必要条件）互为同构的两个图（必要条件）互为同构的两个图（必要条件）互为同构的两个图（必要条件）有相同样的阶数（结点有相同样的阶数（结点有相同样的阶数（结点有相同样的阶数（结点(ji din)(ji din)(ji din)(ji din)）和同样数量的边数及顶点的度数序列）和同样数量的边数及顶点的度数序列）和同样数量的边数及顶点的度数序列）和同样数量的边数及顶点的度数序列 2)2)2)2)图之间的同构关系可看成全

16、体图集合上的二元关系图之间的同构关系可看成全体图集合上的二元关系图之间的同构关系可看成全体图集合上的二元关系图之间的同构关系可看成全体图集合上的二元关系 同构的图为一个等价类，在同构的意义之下都可以看成是一个图。同构的图为一个等价类，在同构的意义之下都可以看成是一个图。同构的图为一个等价类，在同构的意义之下都可以看成是一个图。同构的图为一个等价类，在同构的意义之下都可以看成是一个图。第3页/共21页第四页，共21页。四、特殊图完全图与正则图四、特殊图完全图与正则图四、特殊图完全图与正则图四、特殊图完全图与正则图 1 1 1 1）完全图）完全图）完全图）完全图 定义定义定义定义 设设设设G G

17、G G为为为为n n n n阶无向简单图，若阶无向简单图，若阶无向简单图，若阶无向简单图，若G G G G中每个顶点中每个顶点中每个顶点中每个顶点(dngdin)(dngdin)(dngdin)(dngdin)均与均与均与均与其余的其余的其余的其余的n1n1n1n1个顶点个顶点个顶点个顶点(dngdin)(dngdin)(dngdin)(dngdin)相邻，则称相邻，则称相邻，则称相邻，则称G G G G为为为为n n n n阶无向完全图，阶无向完全图，阶无向完全图，阶无向完全图，简称简称简称简称n n n n阶完全图，记作阶完全图，记作阶完全图，记作阶完全图，记作Kn(n1)Kn(n1)Kn

18、(n1)Kn(n1)设设设设D D D D为为为为n n n n阶有向简单图，若阶有向简单图，若阶有向简单图，若阶有向简单图，若D D D D中每个顶点中每个顶点中每个顶点中每个顶点(dngdin)(dngdin)(dngdin)(dngdin)都邻都邻都邻都邻接到其余的接到其余的接到其余的接到其余的n1n1n1n1个顶点个顶点个顶点个顶点(dngdin)(dngdin)(dngdin)(dngdin)，又邻接于其余的，又邻接于其余的，又邻接于其余的，又邻接于其余的n1n1n1n1个个个个顶点顶点顶点顶点(dngdin)(dngdin)(dngdin)(dngdin)，则称，则称，则称，则称D

19、 D D D是是是是n n n n阶有向完全图阶有向完全图阶有向完全图阶有向完全图 可画图表示（无向图可画图表示（无向图可画图表示（无向图可画图表示（无向图K3,K4,K5K3,K4,K5K3,K4,K5K3,K4,K5、有向图、有向图、有向图、有向图3 3 3 3阶）阶）阶）阶）2)2)2)2)完全图的性质：完全图的性质：完全图的性质：完全图的性质：n n n n阶无向完全图阶无向完全图阶无向完全图阶无向完全图G G G G的边数与结点的关系的边数与结点的关系的边数与结点的关系的边数与结点的关系 m=n(n-1)/2 m=n(n-1)/2 m=n(n-1)/2 m=n(n-1)/2 n n

20、n n阶有向完全图阶有向完全图阶有向完全图阶有向完全图G G G G的边数与结点的关系的边数与结点的关系的边数与结点的关系的边数与结点的关系 m=n(n-1)m=n(n-1)m=n(n-1)m=n(n-1)3)3)3)3)正则图正则图正则图正则图 定义定义定义定义 设设设设G G G G为为为为n n n n阶无向简单图，若阶无向简单图，若阶无向简单图，若阶无向简单图，若 v V(G)v V(G)v V(G)v V(G)，均有，均有，均有，均有d(v)d(v)d(v)d(v)k k k k，则称则称则称则称G G G G为是为是为是为是 k-k-k-k-正则图正则图正则图正则图 k-k-k-k

21、-正则图的边数与结点个数的关系正则图的边数与结点个数的关系正则图的边数与结点个数的关系正则图的边数与结点个数的关系 ：m=k n/2 m=k n/2 m=k n/2 m=k n/2 可画可画可画可画 3 3 3 3正则图和正则图和正则图和正则图和4 4 4 4正则图正则图正则图正则图第4页/共21页第五页，共21页。五、子图、生成子图、导出子图五、子图、生成子图、导出子图五、子图、生成子图、导出子图五、子图、生成子图、导出子图 1 1 1 1、定义、定义、定义、定义 设设设设G G G GVVVEEE，GGGGVVVEEE为两个图为两个图为两个图为两个图(同为无向图或同为有向图同为无向图或同为

22、有向图同为无向图或同为有向图同为无向图或同为有向图)若若若若VVVV V V V V 且且且且 E E E E E E E E，则称则称则称则称GGGG是是是是G G G G的子图，的子图，的子图，的子图，G G G G为为为为GGGG的母图，的母图，的母图，的母图，记作记作记作记作GGGG G G G G，又若又若又若又若VVVV V V V V 或或或或 E E E E E E E E 则称则称则称则称GGGG为为为为G G G G的真子图的真子图的真子图的真子图 若若若若VVVVV (V (V (V (且且且且EEEE E)E)E)E)则称则称则称则称GGGG为为为为G G G G的生成

23、子图的生成子图的生成子图的生成子图 2 2 2 2、设、设、设、设G G G GVVVEEE为图，为图，为图，为图，V1V1V1V1 V V V V 且且且且V1 V1 V1 V1 ，称以，称以，称以，称以V1V1V1V1为顶点集，以为顶点集，以为顶点集，以为顶点集，以G G G G中两个端点都在中两个端点都在中两个端点都在中两个端点都在V1V1V1V1中的边组成中的边组成中的边组成中的边组成(z(z(z(z chn)chn)chn)chn)边集边集边集边集E1E1E1E1的图为的图为的图为的图为G G G G的的的的V1V1V1V1导出的子图，记作导出的子图，记作导出的子图，记作导出的子图，

24、记作GV1GV1GV1GV1 可画图表示可画图表示可画图表示可画图表示 G G G G 及及及及 G G G GV1V1V1V1 （由部分结点导出的子图）（由部分结点导出的子图）（由部分结点导出的子图）（由部分结点导出的子图）又设又设又设又设E1 E1 E1 E1 E E E E且且且且 E1 E1 E1 E1 ，称以，称以，称以，称以 E1 E1 E1 E1为边集，以为边集，以为边集，以为边集，以E1E1E1E1中边关联的顶点为顶点集中边关联的顶点为顶点集中边关联的顶点为顶点集中边关联的顶点为顶点集V1V1V1V1的图为的图为的图为的图为G G G G的的的的E1E1E1E1导导导导出的子图

25、，记作出的子图，记作出的子图，记作出的子图，记作GE1GE1GE1GE1 （由部分边导出的子图）（由部分边导出的子图）（由部分边导出的子图）（由部分边导出的子图）3 3 3 3、补图、补图、补图、补图 1 1 1 1）定义）定义）定义）定义 设设设设G G G G V V VE E E 为为为为n n n n阶无向简单图，阶无向简单图，阶无向简单图，阶无向简单图，图图图图G G G G V V V E E E 以以以以V V V V为顶点集为顶点集为顶点集为顶点集 以以以以E=(u,v):u V vV uv (u,v)EE=(u,v):u V vV uv (u,v)EE=(u,v):u V v

26、V uv (u,v)EE=(u,v):u V vV uv (u,v)E为边的图为边的图为边的图为边的图 称为称为称为称为G G G G的补图，记作的补图，记作的补图，记作的补图，记作G G G G 2 2 2 2）自补图：若图）自补图：若图）自补图：若图）自补图：若图 G G(G G(G G(G G(同构同构同构同构)则称则称则称则称G G G G为自补图为自补图为自补图为自补图第5页/共21页第六页，共21页。14.2 14.2 14.2 14.2 通路、回路通路、回路通路、回路通路、回路一、通路与回路一、通路与回路一、通路与回路一、通路与回路1 1 1 1、通路、通路、通路、通路 1 1

27、1 1）定义：给定有向图）定义：给定有向图）定义：给定有向图）定义：给定有向图D D D D中的任何一个边序列中的任何一个边序列中的任何一个边序列中的任何一个边序列L L L L，如果其中的任何一条边的，如果其中的任何一条边的，如果其中的任何一条边的，如果其中的任何一条边的终点，都是继之出现的边终点，都是继之出现的边终点，都是继之出现的边终点，都是继之出现的边(如果存在的话如果存在的话如果存在的话如果存在的话)的始点，的始点，的始点，的始点，则称这样则称这样则称这样则称这样(zhyng)(zhyng)(zhyng)(zhyng)的边的序列是图的边的序列是图的边的序列是图的边的序列是图G G G

28、 G的通路。的通路。的通路。的通路。若序列中首尾结点相同，则称若序列中首尾结点相同，则称若序列中首尾结点相同，则称若序列中首尾结点相同，则称L L L L为回路为回路为回路为回路 2 2 2 2）定义：有向图）定义：有向图）定义：有向图）定义：有向图D D D D中边序列中的各条边全都是互不相同的通路，称为简单中边序列中的各条边全都是互不相同的通路，称为简单中边序列中的各条边全都是互不相同的通路，称为简单中边序列中的各条边全都是互不相同的通路，称为简单通路通路通路通路 3 3 3 3）定义：有向图）定义：有向图）定义：有向图）定义：有向图D D D D中，序列中的每一个结点仅出现一次的通路，称

29、为初级中，序列中的每一个结点仅出现一次的通路，称为初级中，序列中的每一个结点仅出现一次的通路，称为初级中，序列中的每一个结点仅出现一次的通路，称为初级通路通路通路通路 若序列中首尾结点相同，则称通路为初级回路或圈若序列中首尾结点相同，则称通路为初级回路或圈若序列中首尾结点相同，则称通路为初级回路或圈若序列中首尾结点相同，则称通路为初级回路或圈 4 4 4 4）定义：序列中边的条数称为它的长度）定义：序列中边的条数称为它的长度）定义：序列中边的条数称为它的长度）定义：序列中边的条数称为它的长度2 2 2 2、简单通路和初级通路的关系、简单通路和初级通路的关系、简单通路和初级通路的关系、简单通路和

30、初级通路的关系 有向图中的每一条初级通路，也都必定是简单通路。有向图中的每一条初级通路，也都必定是简单通路。有向图中的每一条初级通路，也都必定是简单通路。有向图中的每一条初级通路，也都必定是简单通路。反之不成立反之不成立反之不成立反之不成立 回路也可分为简单回路和初级回路。回路也可分为简单回路和初级回路。回路也可分为简单回路和初级回路。回路也可分为简单回路和初级回路。3 3 3 3、通路的表示：可仅用通路中的边序列表示：、通路的表示：可仅用通路中的边序列表示：、通路的表示：可仅用通路中的边序列表示：、通路的表示：可仅用通路中的边序列表示：e1e2eke1e2eke1e2eke1e2ek 也可仅

31、用通路中所经过的结点的序列表示：也可仅用通路中所经过的结点的序列表示：也可仅用通路中所经过的结点的序列表示：也可仅用通路中所经过的结点的序列表示：v1v2v3vk v1v2v3vk v1v2v3vk v1v2v3vk 第6页/共21页第七页，共21页。4 4 4 4、性质：、性质：、性质：、性质：1 1 1 1）定理）定理）定理）定理 在在在在n n n n阶图阶图阶图阶图D D D D中，若从顶点中，若从顶点中，若从顶点中，若从顶点vivivivi到到到到vj(vivj)vj(vivj)vj(vivj)vj(vivj)存在通路，则从存在通路，则从存在通路，则从存在通路，则从vivivivi到

32、到到到vjvjvjvj存在长度小于或等于存在长度小于或等于存在长度小于或等于存在长度小于或等于(n1)(n1)(n1)(n1)的通路的通路的通路的通路 若大于若大于若大于若大于n-1n-1n-1n-1，则存在相同节点（有回路），将回路删去可得，则存在相同节点（有回路），将回路删去可得，则存在相同节点（有回路），将回路删去可得，则存在相同节点（有回路），将回路删去可得 2 2 2 2）在）在）在）在n n n n阶图阶图阶图阶图D D D D中，若从顶点中，若从顶点中，若从顶点中，若从顶点vivivivi到到到到vjvjvjvj存在通路，则存在通路，则存在通路，则存在通路，则vivivivi到到

33、到到vjvjvjvj一定存在长度小于或等于一定存在长度小于或等于一定存在长度小于或等于一定存在长度小于或等于n1n1n1n1的初级的初级的初级的初级(chj)(chj)(chj)(chj)通路通路通路通路(路径路径路径路径)3 3 3 3）定理）定理）定理）定理 在一个在一个在一个在一个n n n n阶图阶图阶图阶图D D D D中，若存在中，若存在中，若存在中，若存在vivivivi到自身的回路，则一定存在到自身的回路，则一定存在到自身的回路，则一定存在到自身的回路，则一定存在vivivivi到自身长度小于或等于到自身长度小于或等于到自身长度小于或等于到自身长度小于或等于n n n n的的的

34、的回路回路回路回路 4 4 4 4）在一个）在一个）在一个）在一个n n n n阶图阶图阶图阶图D D D D中，若存在中，若存在中，若存在中，若存在vivivivi到自身的简单回路，则一定存在长度小于或等于到自身的简单回路，则一定存在长度小于或等于到自身的简单回路，则一定存在长度小于或等于到自身的简单回路，则一定存在长度小于或等于n n n n的初级的初级的初级的初级(chj)(chj)(chj)(chj)回路回路回路回路 以上概念均可用在无向图以上概念均可用在无向图以上概念均可用在无向图以上概念均可用在无向图G G G G中中中中14.3 14.3 14.3 14.3 图的连通性图的连通性

35、图的连通性图的连通性 一、无向图的连通性一、无向图的连通性一、无向图的连通性一、无向图的连通性 1 1 1 1、结点的连通：、结点的连通：、结点的连通：、结点的连通：设无向图设无向图设无向图设无向图G G G GVVVEEE，u,v V u,v V u,v V u,v V，若，若，若，若u u u u，v v v v之间存在通路，则称之间存在通路，则称之间存在通路，则称之间存在通路，则称u,vu,vu,vu,v是连通是连通是连通是连通的，记作的，记作的，记作的，记作u u u u v v v v，u V u V u V u V，规定，规定，规定，规定u u u uu u u u 2 2 2 2

36、、结点的连通关系是等价关系、结点的连通关系是等价关系、结点的连通关系是等价关系、结点的连通关系是等价关系 若定义：若定义：若定义：若定义：uuu uv uv uv u，vVvVvVvV且且且且 u u u u与与与与v v v v之间有通路之间有通路之间有通路之间有通路 此关系是自反，对称的，传递的，因而是此关系是自反，对称的，传递的，因而是此关系是自反，对称的，传递的，因而是此关系是自反，对称的，传递的，因而是V V V V上的等价关系上的等价关系上的等价关系上的等价关系 第7页/共21页第八页，共21页。3 3 3 3、无向图的连通图、无向图的连通图、无向图的连通图、无向图的连通图 定义定

37、义定义定义1414141413 13 13 13 若无向图若无向图若无向图若无向图G G G G是平凡图或是平凡图或是平凡图或是平凡图或G G G G中任何两个顶点都是连通的，则称中任何两个顶点都是连通的，则称中任何两个顶点都是连通的，则称中任何两个顶点都是连通的，则称G G G G 为连通图，为连通图，为连通图，为连通图，否则称否则称否则称否则称G G G G为非连通图或分离图（各子图为连通分支）为非连通图或分离图（各子图为连通分支）为非连通图或分离图（各子图为连通分支）为非连通图或分离图（各子图为连通分支）4 4 4 4、结点之间的距离、结点之间的距离、结点之间的距离、结点之间的距离 1

38、1 1 1）定义：设）定义：设）定义：设）定义：设u u u u，v v v v为无向图为无向图为无向图为无向图G G G G中任意两个顶点中任意两个顶点中任意两个顶点中任意两个顶点 若若若若u u u u v v v v，称，称，称，称u u u u，v v v v之间长度最短的通路为之间长度最短的通路为之间长度最短的通路为之间长度最短的通路为u u u u，v v v v之间的短程线之间的短程线之间的短程线之间的短程线 短程线的长度称为短程线的长度称为短程线的长度称为短程线的长度称为u u u u，v v v v之间的距离，记作之间的距离，记作之间的距离，记作之间的距离，记作 d(u d(

39、u d(u d(u，v)v)v)v)当当当当u u u u，v v v v不连通时，规定不连通时，规定不连通时，规定不连通时，规定d(ud(ud(ud(u，v)v)v)v)2 2 2 2）无向图结点的距离有以下性质：）无向图结点的距离有以下性质：）无向图结点的距离有以下性质：）无向图结点的距离有以下性质：1 1 1 1d(ud(ud(ud(u，v)0v)0v)0v)0，u=uu=uu=uu=u时，等号成立时，等号成立时，等号成立时，等号成立 2 2 2 2具有对称性：具有对称性：具有对称性：具有对称性：d(ud(ud(ud(u，v)v)v)v)d(vd(vd(vd(v，u)u)u)u)3 3

40、3 3满足三角不等式：满足三角不等式：满足三角不等式：满足三角不等式：u,v u,v u,v u,v，w V(G)w V(G)w V(G)w V(G)，则，则，则，则 d(u d(u d(u d(u，v)+d(vv)+d(vv)+d(vv)+d(v，w)d(uw)d(uw)d(uw)d(u，w)w)w)w)二、有向图的连通性二、有向图的连通性二、有向图的连通性二、有向图的连通性 1 1 1 1、结点的可达性、结点的可达性、结点的可达性、结点的可达性 定义：定义：定义：定义：设设设设D D D DVVVEEE为一个为一个为一个为一个(y)(y)(y)(y)有向图有向图有向图有向图 vi,vj V

41、 vi,vj V vi,vj V vi,vj V，若从，若从，若从，若从vivivivi到到到到vjvjvjvj存存存存在通路在通路在通路在通路 则称则称则称则称vivivivi可达可达可达可达vj,vj,vj,vj,记作记作记作记作vi vj vi vj vi vj vi vj。规定规定规定规定vivivivi总是可达自身的，即总是可达自身的，即总是可达自身的，即总是可达自身的，即vi vivi vivi vivi vi 第8页/共21页第九页，共21页。2 2 2 2、结点的相互可达、结点的相互可达、结点的相互可达、结点的相互可达 若若若若vi vj vi vj vi vj vi vj 且

42、且且且vj vi vj vi vj vi vj vi 则称则称则称则称vivivivi与与与与vjvjvjvj是相互可达的，记作是相互可达的，记作是相互可达的，记作是相互可达的，记作:vi:vi:vi:vi vj vj vj vj 规定规定规定规定vi vi vi vi vi vi vi vi 3 3 3 3、结点的可达关系为结点的可达关系为结点的可达关系为结点的可达关系为V V V V上的二元关系，但不是等价关系（不满足对称性）。上的二元关系，但不是等价关系（不满足对称性）。上的二元关系，但不是等价关系（不满足对称性）。上的二元关系，但不是等价关系（不满足对称性）。相互可达关系为相互可达关系

43、为相互可达关系为相互可达关系为V V V V上的二元关系，且是上的二元关系，且是上的二元关系，且是上的二元关系，且是V V V V上的等价关系上的等价关系上的等价关系上的等价关系 有向图中顶点之间的可达关系既无对称性，也无反对称性有向图中顶点之间的可达关系既无对称性，也无反对称性有向图中顶点之间的可达关系既无对称性，也无反对称性有向图中顶点之间的可达关系既无对称性，也无反对称性4 4 4 4、有向图中结点的距离、有向图中结点的距离、有向图中结点的距离、有向图中结点的距离(jl)(jl)(jl)(jl)定义：设定义：设定义：设定义：设D D D DVVVEEE为有向图为有向图为有向图为有向图 v

44、i,vj V vi,vj V vi,vj V vi,vj V，若，若，若，若 vi vj vi vj vi vj vi vj，称，称，称，称vivivivi到到到到vivivivi长度最短的通路为长度最短的通路为长度最短的通路为长度最短的通路为vivivivi到到到到vjvjvjvj的短程线的短程线的短程线的短程线 短程线的长度为短程线的长度为短程线的长度为短程线的长度为vivivivi到到到到vjvjvjvj的距离的距离的距离的距离(jl)(jl)(jl)(jl)，记作，记作，记作，记作dvidvidvidvjvjvj 注：该定义与无向图中顶点注：该定义与无向图中顶点注：该定义与无向图中顶点

45、注：该定义与无向图中顶点vivivivi与与与与vjvjvjvj之间的距离之间的距离之间的距离之间的距离(jl)d(vi(jl)d(vi(jl)d(vi(jl)d(vi，vj)vj)vj)vj)的区别：无对称性的区别：无对称性的区别：无对称性的区别：无对称性 一般地：一般地：一般地：一般地：dvidvidvid d d d d vi vi vi（可能（可能（可能（可能dvidvidvid vj vj vj 不存在）不存在）不存在）不存在）5 5 5 5、弱连通图、单向连通图和强连通图、弱连通图、单向连通图和强连通图、弱连通图、单向连通图和强连通图、弱连通图、单向连通图和强连通图 定义定义定义定

46、义1 1 1 1 设设设设D D D DVVVV，E)E)E)E)为一个有向图为一个有向图为一个有向图为一个有向图 若若若若D D D D的作为无向图是连通图，则称的作为无向图是连通图，则称的作为无向图是连通图，则称的作为无向图是连通图，则称D D D D是弱连通图，简称为连通图是弱连通图，简称为连通图是弱连通图，简称为连通图是弱连通图，简称为连通图 定义定义定义定义2 2 2 2 设设设设D D D DVVVV，E)E)E)E)为一个有向图，为一个有向图，为一个有向图，为一个有向图，若若若若 vi,vj V,vi vj vi,vj V,vi vj vi,vj V,vi vj vi,vj V,

47、vi vj与与与与vj vivj vivj vivj vi至少成立其一，则称至少成立其一，则称至少成立其一，则称至少成立其一，则称D D D D是单向连通图是单向连通图是单向连通图是单向连通图 若若若若 vi,vj V vi,vj V vi,vj V vi,vj V，均有，均有，均有，均有vi vi vi vi vj vj vj vj，则称，则称，则称，则称D D D D是强连通图是强连通图是强连通图是强连通图 注：三种图的关系：强连通图一定是单向连通图，反之不成立注：三种图的关系：强连通图一定是单向连通图，反之不成立注：三种图的关系：强连通图一定是单向连通图，反之不成立注：三种图的关系：强连

48、通图一定是单向连通图，反之不成立 单向连通图一定是弱连通图反之不成立单向连通图一定是弱连通图反之不成立单向连通图一定是弱连通图反之不成立单向连通图一定是弱连通图反之不成立 第9页/共21页第十页，共21页。6 6 6 6、有关、有关、有关、有关(yugun)(yugun)(yugun)(yugun)强连通图与单向连通图的判定强连通图与单向连通图的判定强连通图与单向连通图的判定强连通图与单向连通图的判定 （1 1 1 1）定理：）定理：）定理：）定理：设有向图设有向图设有向图设有向图D D D DVVVEEE，V V V Vv1v1v1v1，v2v2v2v2，vnvnvnvn D D D D是强

49、连通图当且仅当是强连通图当且仅当是强连通图当且仅当是强连通图当且仅当D D D D中存在经过每个顶点至少一次的回路中存在经过每个顶点至少一次的回路中存在经过每个顶点至少一次的回路中存在经过每个顶点至少一次的回路 (2)(2)(2)(2)定理定理定理定理 设设设设D D D D是是是是n n n n阶有向图阶有向图阶有向图阶有向图 D D D D是单向连通图当且仅当是单向连通图当且仅当是单向连通图当且仅当是单向连通图当且仅当D D D D中存在经过每个顶点至少一次的通路中存在经过每个顶点至少一次的通路中存在经过每个顶点至少一次的通路中存在经过每个顶点至少一次的通路例例2 2设有向图设有向图D D

50、是单向是单向(dn xin)(dn xin)连通图，但不是强连通图，问在连通图，但不是强连通图，问在D D中至少加几条边所中至少加几条边所得图得图DD就能成为强连通图就能成为强连通图?14.4 14.4 图的矩阵表示图的矩阵表示一、图的矩阵表示一、图的矩阵表示 用矩阵表示图之前，必须将图的顶点或边标定成顺序，使其成为标定图用矩阵表示图之前，必须将图的顶点或边标定成顺序，使其成为标定图1 1、无向图的关联矩阵、无向图的关联矩阵1 1）定义）定义141424 24 设无向图设无向图G GVE，V Vv1,v2,v1,v2,，vnvn。E=e1,e2,e3E=e1,e2,e3，emem令令mijmi