图论 图基本概念 .pptx

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

1、3 3、邻接、邻接 (1)(1)边的相邻边的相邻：e ek k，e el lEE若若e ek k与与e el l至少有一个公共端点，则称至少有一个公共端点，则称e ek k与与e el l是是相邻的相邻的 (2)(2)顶点的相邻顶点的相邻：若若 e et tEE，使得，使得e et t=vi=vj，并称并称vivi邻接到邻接到vjvj，vjvj邻接于邻接于vi vi 两个结点为一条边的端点，则称两个结点两个结点为一条边的端点，则称两个结点互为邻接点互为邻接点4 4、平行边：、平行边：在无向图中，关联一对顶点的无向边如果多于在无向图中，关联一对顶点的无向边如果多于1 1条，则称这些边为平条，则称

2、这些边为平行边，平行边的条数称为重数行边，平行边的条数称为重数 在有向图中，关联一对顶点的有向边如果多于在有向图中，关联一对顶点的有向边如果多于1 1条，并且这些边的条，并且这些边的始点与终点相同始点与终点相同(也就是它们的方向相同也就是它们的方向相同)，则称这些边为平行边，则称这些边为平行边 5 5、多重图和简单图：含平行边的图称为多重图、多重图和简单图：含平行边的图称为多重图 既不含平行边也不含环的图称为既不含平行边也不含环的图称为简单图简单图二、结点的度结点的度 1 1）定义）定义4 4 设设G GVE为无向图，为无向图，v Vv V，称，称v v作为边的端点次数之作为边的端点次数之和和

3、为为v v的度数，简记为度记作的度数，简记为度记作d d G G(v)(v)，简记为简记为d(v)d(v)即为：结点即为：结点v v 所关联的边的总条数所关联的边的总条数 关于有向图关于有向图D DV E 有：有：v Vv V，称，称v v 作为边的作为边的始点的次数之和始点的次数之和为为v v的出度，记作的出度，记作d d+(v)(v)，称称v v作为边的终点的次数之和为作为边的终点的次数之和为v v的入度，记作的入度，记作d d-(v)(v)，称称d d+(v)+d(v)+d-(v)(v)为为 v v的度数，记作的度数，记作d(v)d(v)2）度为偶数度为偶数(奇数奇数)的顶点称为的顶点称

4、为偶度偶度(奇度奇度)顶点顶点 第1页/共21页3 3、握手定理（欧拉）、握手定理（欧拉）1)1)定理定理1 1 设设G G为任意无向图为任意无向图,V,Vvv1 1，v v2 2，v vn n,E E =m m，则则 d(vd(vi i)2 m (2 m (所有结点的度数值和为边数的所有结点的度数值和为边数的2 2倍倍)2)2)定理定理2 2 设设D D为任意有向图为任意有向图,V,Vvv1 1，v v2 2，v vn n,|E|=m,|E|=m，则则 d d+(v(vi i)d d-(v(vi i)=m)=m 且且d(vd(vi i)2 m2 m3)3)推论推论 任何图任何图(无向的或有向

5、的无向的或有向的)中，中，奇度顶点的个数是偶数奇度顶点的个数是偶数4)4)结点的度数序列结点的度数序列 (1)(1)设设G GVE为一个为一个n n阶无向图，阶无向图，V Vvv1 1，v v2 2，v vn n 称称d(vd(v1 1)，d(vd(v2 2)，d(vd(vn n)为为G G的度数列的度数列 条件：条件：奇度数奇度数的结点个数应该是的结点个数应该是偶数个偶数个 （2 2）序列的可图化：）序列的可图化：d=(dd=(d1 1,d,d2 2,d dn n)对一个整数序列对一个整数序列d,d,若存在以若存在以n n个顶点的个顶点的n n阶无向图阶无向图G G，有，有d(vd(vi i

6、)=d)=di i 称该序列是可图化的称该序列是可图化的（3 3）定理）定理 设非负整数列设非负整数列d d(d1(d1，d2d2，dn)dn)，则，则d d是可图化的当是可图化的当且仅当且仅当 d di i=0(mod 2)=0(mod 2)(序列之和必须是偶数序列之和必须是偶数)（4 4）由于简单图中没有平行边及环）由于简单图中没有平行边及环 结论：结论：n n个结点的个结点的简单图简单图中结点的最大中结点的最大度数（度数（G)G)）应小于等）应小于等于于n-1n-1 每个结点至多与其他每个结点至多与其他n-1n-1个结点相邻个结点相邻第2页/共21页三、图的同构三、图的同构定义定义 设设

7、G1G1Vl E1，G2=V2G2=E2为两个无向图为两个无向图(两个有向图两个有向图)，若存在双射函数若存在双射函数f f：V1 V2 V1 V2 顶点的一一对顶点的一一对应应 对于对于 vivi，vjV1vjV1，(vi(vi，vj)E1(vivj)E1(E1)vj E1)当且仅当当且仅当(f(vi)(f(vi)，f(vj)E2(f(vi)f(vj)E2(E2)f(vj)E2)，边的边的对应对应 并且并且(vi(vi，vj)vj)()()与与(f(vi),f(vj(f(vi),f(vj)()()的重数的重数相同相同，则称则称G1G1与与G2G2是同构的，记作是同构的，记作Gl Gl G2

8、G2 注：注：1)1)互为互为同构的两个图（必要条件）同构的两个图（必要条件）有有相同样的阶数相同样的阶数（结点）和（结点）和同样数量的边数同样数量的边数及顶点的及顶点的度数序列度数序列 2)2)图之间的图之间的同构关系同构关系可看成全体图集合上的二元关系可看成全体图集合上的二元关系 同构的图为一个等价类，在同构的图为一个等价类，在同构的意义之下都可以看成是一个图。同构的意义之下都可以看成是一个图。第3页/共21页四、特殊图完全图与正则图四、特殊图完全图与正则图 1 1）完全图）完全图 定义定义 设设G G为为n n阶无向简单图，若阶无向简单图，若G G中每个顶点均与其余的中每个顶点均与其余的

9、n n1 1个顶点个顶点相邻，则称相邻，则称G G为为n n阶无向完全图，简称阶无向完全图，简称n n阶完全图阶完全图，记作，记作KnKn(n1)(n1)设设D D为为n n阶有向简单图，若阶有向简单图，若D D中每个顶点都中每个顶点都邻接到邻接到其余的其余的n n1 1个个顶点，又顶点，又邻接于邻接于其余的其余的n n1 1个顶点，则称个顶点，则称D D是是n n阶阶有向完全图有向完全图 可画图表示可画图表示（无向图（无向图K K3 3,K,K4 4,K,K5 5、有向图、有向图3 3阶）阶）2)2)完全图的性质：完全图的性质：n n阶无向完全图阶无向完全图G G的边数与结点的关系的边数与结

10、点的关系 m=m=n(n-1)/2n(n-1)/2 n n阶有向完全图阶有向完全图G G的边数与结点的关系的边数与结点的关系 m=m=n(n-1)n(n-1)3)3)正则图正则图 定义定义 设设G G为为n n阶无向简单图，若阶无向简单图，若 v V(G)v V(G)，均有，均有d(v)d(v)k k，则称则称G G为是为是 k-k-正则图正则图 k-k-正则图的正则图的边数与结点个数边数与结点个数的关系的关系 ：m=k n/2m=k n/2 可画可画 3 3正则图和正则图和4 4正则图正则图第4页/共21页五、子图、生成子图、导出子图五、子图、生成子图、导出子图 1 1、定义、定义 设设G

11、GVE，G GV 为两个图为两个图(同为无向图或同为同为无向图或同为有向图有向图)若若V V V V 且且 E E E E ，则称则称G G是是G G的的子图子图，G G为为G G的母图的母图，记作记作G G G G，又又若若V V V V 或或 E E E E 则称则称G G为为G G的的真子图真子图 若若V VV (V (且且E E E)E)则称则称G G为为G G的的生成子图生成子图 2 2、设、设G GVE为图，为图，V1V1 V V 且且V1 V1 ，称以，称以V1V1为顶点集，以为顶点集，以G G中两个端中两个端点都在点都在V1V1中的边组成边集中的边组成边集E1E1的图为的图为G

12、 G的的V1V1导出的子图导出的子图，记作，记作GV1GV1 可画图表示可画图表示 G G 及及 G GV1V1 （由（由部分结点导出的子图）部分结点导出的子图）又设又设E1 E1 E E且且 E1 E1 ，称以，称以 E1E1为边集，以为边集，以E1E1中边关联的顶点为中边关联的顶点为顶点集顶点集V1V1的图为的图为G G的的E1E1导出的子图导出的子图，记作，记作GE1GE1 （由（由部分边部分边导出导出的子图的子图）3 3、补图、补图 1 1）定义）定义 设设G G VE 为为n n阶无向简单图，阶无向简单图，图图G G V 以以V V为顶点集为顶点集 以以E E=(u,v):u=(u,

13、v):u V V v vV V u uv v (u,v)(u,v)E E 为边的图为边的图 称为称为G G的补图的补图，记作，记作G G 2）自补图：若图）自补图：若图 G G(G G(同构同构)则称则称G G为自补图为自补图第5页/共21页14.2 14.2 通路、回路通路、回路一、通路与回路一、通路与回路1 1、通路、通路 1 1）定义：给定有向图）定义：给定有向图D D中的任何一个边序列中的任何一个边序列L L，如果其中的任何，如果其中的任何一条边的一条边的终点终点，都是继之出现的，都是继之出现的边边(如果存在的话如果存在的话)的始点，的始点，则称这样的边的则称这样的边的序列是图序列是图

14、G G的的通路。通路。若序列中若序列中首尾结点相同首尾结点相同，则称，则称L L为回路为回路 2 2）定义：有向图）定义：有向图D D中中边序列中的各条边全都是互不相同边序列中的各条边全都是互不相同的通路，称为的通路，称为简单简单通路通路 3 3）定义：有向图）定义：有向图D D中，序列中的中，序列中的每一个结点仅出现一次每一个结点仅出现一次的通路，称为的通路，称为初级初级通路通路 若序列中若序列中首尾结点相同首尾结点相同，则称通路为，则称通路为初级回路或圈初级回路或圈 4 4）定义：序列中）定义：序列中边的条数边的条数称为它的称为它的长度长度2 2、简单通路和初级通路的关系、简单通路和初级通

15、路的关系 有向图中的每一条有向图中的每一条初级通路初级通路，也都，也都必定是简单通路必定是简单通路。反之不成立反之不成立 回路也可分为简单回路和初级回路。回路也可分为简单回路和初级回路。3 3、通路的表示：可仅用通路中的、通路的表示：可仅用通路中的边序列表示边序列表示：e e1 1e e2 2e ek k 也可仅用通路中所经过的也可仅用通路中所经过的结点的序列表示结点的序列表示：v v1 1v v2 2v v3 3v vk k 第6页/共21页4 4、性质：、性质：1 1）定理）定理 在在n n阶图阶图D D中，若从顶点中，若从顶点vivi到到vj(vivj)vj(vivj)存在通路存在通路，

16、则从，则从vivi到到vjvj存在长度小于或等于存在长度小于或等于(n(n1)1)的通路的通路 若大于若大于n-1n-1，则存在相同节点（有回路），将，则存在相同节点（有回路），将回路删去可回路删去可得得 2 2）在）在n n阶图阶图D D中，若从顶点中，若从顶点vivi到到vjvj存在通路存在通路，则，则vivi到到vjvj一定一定存在长度小存在长度小于或等于于或等于n n1 1的初级通路的初级通路(路径路径)3 3）定理）定理 在一个在一个n n阶图阶图D D中，若存在中，若存在vivi到自身的到自身的回路回路，则一定存在，则一定存在vivi到到自身长度自身长度小于或等于小于或等于n n的

17、回路的回路 4 4）在一个）在一个n n阶图阶图D D中，若存在中，若存在vivi到自身的到自身的简单回路简单回路，则一定，则一定存在长度小于存在长度小于或等于或等于n n的初级回路的初级回路 以上概念均可用在无向图以上概念均可用在无向图G G中中14.3 14.3 图的连通性图的连通性 一、无向图的连通性一、无向图的连通性 1 1、结点的连通：、结点的连通：设无向图设无向图G GVE，u,v Vu,v V，若，若u u，v v之间之间存在通路，则称存在通路，则称u,vu,v是连通的是连通的，记作，记作u u v v，u Vu V，规定，规定u uu u 2 2、结点的连通关系是等价关系结点的

18、连通关系是等价关系 若定义：若定义：u uv u，vVvV且且 u u与与v v之间有通路之间有通路 此关系是此关系是自反，对称的，传递的，自反，对称的，传递的，因而是因而是V V上的上的等价关系等价关系 第7页/共21页3 3、无向图的连通图、无向图的连通图 定义定义141413 13 若无向图若无向图G G是平凡图或是平凡图或G G中中任何两个顶点都是连通的任何两个顶点都是连通的，则称，则称G G 为连通图，为连通图，否则称否则称G G为非连通图或分离图（各子图为连通分支）为非连通图或分离图（各子图为连通分支）4 4、结点之间的距离、结点之间的距离 1 1）定义：设）定义：设u u，v v

19、为无向图为无向图G G中任意两个顶点中任意两个顶点 若若u u v v，称，称u u，v v之间长度最短的通路为之间长度最短的通路为u u，v v之间的短程线之间的短程线 短程线的长度称为短程线的长度称为u u，v v之间的之间的距离距离，记作，记作 d(ud(u，v)v)当当u u，v v不连通时，规定不连通时，规定d(ud(u，v)v)2 2）无向图结点的距离有以下性质：）无向图结点的距离有以下性质：1 1d(ud(u，v)0v)0，u=uu=u时，等号成立时，等号成立 2 2具有对称性：具有对称性：d(ud(u，v)v)d(vd(v，u)u)3 3满足三角不等式：满足三角不等式：u,v

20、u,v，w V(G)w V(G)，则，则 d(ud(u，v)+d(vv)+d(v，w)d(uw)d(u，w)w)二、有向图的连通性二、有向图的连通性 1 1、结点的可达性、结点的可达性 定义：定义：设设D DVE为一个有向图为一个有向图 vi,vj Vvi,vj V，若，若从从vivi到到vjvj存在存在通路通路 则称则称vivi可达可达vj,vj,记作记作vi vj vi vj。规定规定vivi总是可总是可达自身的达自身的，即，即vi vivi vi 第8页/共21页2 2、结点的相互可达、结点的相互可达 若若vi vj vi vj 且且vj vi vj vi 则称则称vivi与与vjvj是

21、相互可达的，记作是相互可达的，记作:vi:vi vjvj 规定规定vi vi vi vi 3 3、结点的可达关系为结点的可达关系为V V上的二元关系，但上的二元关系，但不是等价关系不是等价关系（不满足对称性）。（不满足对称性）。相互可达关系为相互可达关系为V V上的二元关系，且是上的二元关系，且是V V上的等价关系上的等价关系 有向图中顶点之间的可达关系既无对称性，也无反对称性有向图中顶点之间的可达关系既无对称性，也无反对称性4 4、有向图中结点的距离、有向图中结点的距离 定义：设定义：设D DVE为有向图为有向图 vi,vj Vvi,vj V，若，若 vi vjvi vj，称，称vivi到到

22、vivi长度最短的通路为长度最短的通路为vivi到到vjvj的短的短程线程线 短程线的长度为短程线的长度为vivi到到vjvj的的距离距离，记作，记作dvidvj 注：该定义与无向图中顶点注：该定义与无向图中顶点vivi与与vjvj之间的距离之间的距离d(vid(vi，vj)vj)的区别：无对的区别：无对称性称性 一般地：一般地：dvid vj dvjd vi（可能（可能dvid vj 不存在）不存在）5 5、弱连通图、单向连通图和强连通图、弱连通图、单向连通图和强连通图 定义定义1 1 设设D DVV，E)E)为一个有向图为一个有向图 若若D D的的作为无向图是连通图作为无向图是连通图，则称

23、，则称D D是弱连通图是弱连通图，简称为，简称为连通图连通图 定义定义2 2 设设D DVV，E)E)为一个有向图，为一个有向图，若若 vi,vj V vi,vj V,vi vj,vi vj与与vj vivj vi至少成立其一至少成立其一，则称，则称D D是是单向连单向连通图通图 若若 vi,vj Vvi,vj V，均有，均有vi vi vj vj，则称，则称D D是是强连通图强连通图 注：三种图的关系：注：三种图的关系：强连通图一定是强连通图一定是单向连通图单向连通图，反之不成立，反之不成立 单向连通图一定是单向连通图一定是弱连通图弱连通图反之不成立反之不成立 第9页/共21页6 6、有关强

24、连通图与单向连通图的判定、有关强连通图与单向连通图的判定 （1 1）定理：）定理：设有向图设有向图D DVE，V Vvv1 1，v v2 2，v vn n D D是是强连通图强连通图当且仅当当且仅当D D中存在经过每个顶点中存在经过每个顶点至少一次的回路至少一次的回路 (2)(2)定理定理 设设D D是是n n阶有向图阶有向图 D D是是单向连通图单向连通图当且仅当当且仅当D D中存在经过每个顶点中存在经过每个顶点至少一次的通路至少一次的通路例例2 2设有向图设有向图D D是单向连通图，但不是强连通图，问在是单向连通图，但不是强连通图，问在D D中至少加几条边所得中至少加几条边所得图图D D就

25、能成为强连通图就能成为强连通图?14.4 14.4 图的矩阵表示图的矩阵表示一、图的矩阵表示一、图的矩阵表示 用矩阵表示图之前，必须将图的顶点或边标定成顺序，使其成为标定图用矩阵表示图之前，必须将图的顶点或边标定成顺序，使其成为标定图1 1、无向图的、无向图的关联矩阵关联矩阵1 1）定义）定义141424 24 设无向图设无向图G GVE，V Vvv1 1,v,v2 2,，v vn n。E=eE=e1 1,e,e2 2,e,e3 3，e em m 令令m mijij为顶点为顶点v vi i与边与边e ej j的关联次数的关联次数，则称，则称(m(mijij)nxmnxm为为G G的关联矩阵，记

26、作的关联矩阵，记作 M(G)M(G)2 2）关联矩阵的性质）关联矩阵的性质:关联矩阵是关联矩阵是n n行（结点数）行（结点数）m m列（边数）列（边数）的矩阵的矩阵第10页/共21页(1(1）M(G)M(G)每列元素之和均为每列元素之和均为2 2，这正说明每条边关联两个顶点，这正说明每条边关联两个顶点(环所关联的环所关联的两个端点重合两个端点重合)m mijij=2 (j=1=2 (j=1，2 2，m)m)(2(2）M(G)M(G)第第i i行元素之和为结点行元素之和为结点vivi的度数，的度数，i i1 1，2 2，n n(3)(3)所有行的和（即矩阵所有元素之和）等于边数的所有行的和（即矩

27、阵所有元素之和）等于边数的2 2倍（该例倍（该例1010边数边数5 5的的2 2倍）。倍）。d(vd(vi i)m mijij=2=2 2m2m，这个结果正是握手定理的内容（即各，这个结果正是握手定理的内容（即各顶点的度数之和等于边数的顶点的度数之和等于边数的2 2倍）倍）（4 4）第）第j j列与第列与第k k列相同，当且仅当边列相同，当且仅当边ejej与与ekek是平行边是平行边(5)(5)某行某行i i的和为的和为0 0（即（即 m mijij=0=0）,当且仅当当且仅当v vi i是孤立点是孤立点2 2、有向图的、有向图的关联矩阵关联矩阵定义：设有向图定义：设有向图D DVE中无环，中

28、无环，V Vvv1 1，v v2 2，v vn n。E Eeel l，e e2 2,，e em m，令令 1 v1 vi i为边为边e ej j的起点的起点 m mijij=0 v0 vi i为边为边e ej j不关联不关联 1 v1 vi i为边为边e ej j的终点的终点 则称则称(m(mijij)nxmnxm，为，为D D的关联矩阵，记作的关联矩阵，记作M(DM(D）第11页/共21页 2)2)有向图关联矩阵的性质有向图关联矩阵的性质 （1 1）mij=0mij=0，j j1 1，2 2，m m，从而，从而mij=0mij=0，这说明，这说明M(D)M(D)中中所有元素之和为所有元素之和

29、为0 0 (2)M(D)(2)M(D)中，负中，负1 1的个数等于正的个数等于正1 1的个数，都等于边数的个数，都等于边数m m，这正是有向图，这正是有向图握手定理的内容（入度之和等于出度之和）握手定理的内容（入度之和等于出度之和）（3 3）第）第i i行中，正行中，正1 1的个数等于的个数等于d+(vi)d+(vi)（结点的入度），负（结点的入度），负1 1的个数等于的个数等于d-(vi)d-(vi)（结点的出度）（结点的出度）（4 4）平行边所对应的列相同）平行边所对应的列相同3 3、有向图的、有向图的邻接矩阵邻接矩阵 1 1）定义：设有向图）定义：设有向图D DVE，V Vv1v1，v2

30、v2，vnvn，E Ee1e1，e2e2，emem 令：令：aijaij为顶点为顶点vivi邻接到顶点邻接到顶点vjvj边的条数边的条数 称称(aij)nxn(aij)nxn为为D D的邻接矩阵，记作的邻接矩阵，记作A(D)A(D)，或简记为或简记为A A 2 2）邻接矩阵的性质）邻接矩阵的性质 （1 1）每列元素之和为结点的入度，即）每列元素之和为结点的入度，即 aij aij d+(vi)d+(vi)，i i1 1，2 2，n n 所有所有列的和列的和 aij aij d d+(vi)(vi)m m，等于边数，等于边数 每行元素之和为结点的出度每行元素之和为结点的出度，所有行的和也等于边数

31、，所有行的和也等于边数 （2 2）邻接矩阵中元素）邻接矩阵中元素 aij aij 反映了反映了有向图中结点有向图中结点vivi到到vjvj通路长度为通路长度为1 1的条数的条数作业：作业：P292 17P292 17、1818、4343、47 47 邻接邻接4444、4545、4646第12页/共21页（3 3）A(D)A(D)中所有元素之和为中所有元素之和为D D中长度为中长度为1 1的（边）通路总条数的（边）通路总条数。主对角线的元素值为图中结点主对角线的元素值为图中结点vivi长度为长度为1 1 的的环的条数环的条数 利用利用A(D)A(D)确定出确定出D D中中长度为长度为L L的通路

32、数和回路数的通路数和回路数,就需要用到邻接矩阵的就需要用到邻接矩阵的幂幂次运算次运算（4 4）A A2 2中的元素值中的元素值bijbij是结点是结点vivi到到vjvj长度为长度为2 2 的通路条数的通路条数：说明：由矩阵的乘积定义说明：由矩阵的乘积定义 bij=bij=k k aik*akj aik*akj 由此可推断，由此可推断，A A3 3矩阵中的矩阵中的C Cijij元素值，表示了从到长度恰为元素值，表示了从到长度恰为3 3的通路条数目的通路条数目（5 5）定理）定理141411 11 设设A A为有向图为有向图D D的邻接矩阵，的邻接矩阵，V Vv1v1，v2v2，vn vn 为为

33、D D的顶点集，的顶点集，则则A A的的L L次幂次幂A AL L(L1)(L1)中元素中元素c cijij为为D D中中vivi到到vjvj长度为长度为L L的通路数，的通路数，其中其中ciicii为为vivi到自身长度为到自身长度为L L的回路数的回路数 cij(cij(所有元素之和所有元素之和)为为D D中长度为中长度为L L的通路总数，的通路总数，其中其中 ciicii为为D D中长度为中长度为L L的回路总数的回路总数推论推论 设设B BL LA+AA+A2 2十十+A+AL L(L1)(L1)，则则BLBL中元素中元素 bijbij为为D D中长度小于或等于中长度小于或等于L L的

34、的通路数通路数，其中主对角线上元素值为其中主对角线上元素值为D D中长度小于或等于中长度小于或等于L L的回路数的回路数第13页/共21页4 4、有向图的可达矩阵、有向图的可达矩阵 1 1）定义：设）定义：设D DVE为有向图为有向图,V,Vv1v1，v2v2，vnvn 令令 1 vi1 vi可达可达vivi pij pij 0 0 否则否则 称称(pij)nxn(pij)nxn为为D D的可达矩阵，记作的可达矩阵，记作P(D)P(D)，简记为，简记为P P 2 2）可达矩阵的性质）可达矩阵的性质 （1 1）主对角线元素均为）主对角线元素均为1 1（每个结点自身可达）（每个结点自身可达）（2

35、2）可通过图的邻接矩阵）可通过图的邻接矩阵A A的的n-1n-1次幂次幂B Bn-1n-1得到（将其非零元素换得到（将其非零元素换为为1 1，主对角线元素均设为，主对角线元素均设为1 1即可）即可）第14页/共21页无向完全图无向完全图（每个结点与其（每个结点与其余结点余结点均相邻均相邻）2-2-正则图正则图有向完全图有向完全图（每个结点（每个结点都邻都邻接到接到其余结点其余结点）3-3-正则图正则图右图是左图的右图是左图的子图子图 且是左图的且是左图的真子图真子图 且是左图的且是左图的生成子图生成子图返回返回第15页/共21页（b),(c)b),(c)互为补图互为补图 自补图自补图返回第16

36、页/共21页返回起始于结点起始于结点v1v1并终止于结点并终止于结点v3v3的一些通路是：的一些通路是：P1=(1P1=(2，2)3)P2=(1P2=(4，4)3)P3=(1P3=(2，24，4)3)P4=(1P4=(2，24，41，12，2)3)P5=(1P5=(2，24，41，14，4)3)P6=(1P6=(1，11，11，2)2)，2)3)其中其中P1P1、P2P2、P3P3、P5P5为简单通路为简单通路P1P1、P2P2、P3P3为初级通路（路径）为初级通路（路径）对上图有如下的一些回路：对上图有如下的一些回路：e1=(1e1=()e2=()e2=(2，2)1)e3=(1e3=(2，2

37、3，3)1)e4=(1e4=(4，43，3)1)e5=(1e5=(4，43，32，2)1)不是初级通路任何通路都会不是初级通路任何通路都会包含有回路包含有回路 删除这样的一些回路，就能够得到一条删除这样的一些回路，就能够得到一条初级通路初级通路在通路路在通路路P5P5中，删除回路中，删除回路(1(2，24，4)1)，就能，就能够得到一条够得到一条初级通路初级通路P2P2 返回第17页/共21页返回(a a)图是个强连通的；图是个强连通的；(b b)图是个弱连通的，而不是单向连通的；图是个弱连通的，而不是单向连通的；(c c)图是个单向连通的，而不是强连通的；图是个单向连通的，而不是强连通的；结

38、点的可达性结点的可达性返回第18页/共21页例：给定有向图D，4个顶点7条边 邻接矩阵为 0 1 0 0A=0 0 1 1 1 1 0 1 1 0 0 0 4*4矩阵中有7个1（边）0 0 1 1A2=2 1 0 1 1 1 1 1 0 1 0 0 反映图中任意两个顶点间有多少长度为2的通路 2 1 0 1A3=1 2 1 1 2 2 1 2 0 0 1 1 反映图中任意两个顶点间有多少长度为3的通路 1 2 1 1A4=2 2 2 3 3 3 2 3 2 1 0 1 反映图中任意两个顶点间有多少长度为4的通路返回 3 4 2 3B4=5 5 4 6 7 7 4 7 3 2 1 2 反映图中任意两个顶点间有多少长度为小于等于4的通路返回返回返回返回第19页/共21页第20页/共21页感谢您的观看。第21页/共21页