图论图基本概念.pptx-得力文库

资源描述

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

1、3 3、有关图的术语、有关图的术语1 1）用）用G G表示无向图，表示无向图，D D表示有向图。表示有向图。有时用有时用V(G)V(G)，E(G)E(G)分别表示分别表示G G的顶点集和边集，的顶点集和边集，2 2）用）用 V(G)V(G)，E(G)E(G)分别表示分别表示G G的顶点数和边数的顶点数和边数(有向图类似）有向图类似）若若V(G)V(G)n n，则称，则称G G为为n n阶图。对有向图可做类似规定。阶图。对有向图可做类似规定。3 3）在图）在图G G中，若中，若边集边集E(G)E(G)，则称，则称G G为为零图零图若若G G为为n n阶图，则称阶图，则称G G为为n n阶零图阶

2、零图，记作，记作N Nn n，特别是称，特别是称N N1 1为为平凡图平凡图 4)4)常用常用e ek k表示无向边表示无向边(vi(vi，vj)(vj)(或有向边或有向边vi)vj)设设G GV E 为无向图，为无向图，e ek k=(vi=(vi，vj)Evj)E，则称则称vjvj，vjvj为为e ek k的端点的端点，e ek k与与vivi、vjvj是彼此是彼此相关联的相关联的起终点相同的边称为环起终点相同的边称为环不与任何边关联的结点称为孤立点（包括有向向图不与任何边关联的结点称为孤立点（包括有向向图)5 5）邻接：）邻接：边的相邻边的相邻：e ek k，e el lEE若若e

3、ek k与与e el l至少有一个公共端点，则称至少有一个公共端点，则称e ek k与与e el l是是相邻的相邻的顶点的相邻顶点的相邻：若若 e et tEE，使得，使得e et t=vi=vj，则称则称vivi为为etet的始点，的始点，vjvj为为e et t的终点，的终点，并称并称vivi邻接到邻接到vjvj，vjvj邻接于邻接于vi vi 两个结点为一条边的端点，则称两个结点两个结点为一条边的端点，则称两个结点互为邻接点互为邻接点，也称也称边关联于这两个结点边关联于这两个结点，或称两个结点邻接于此边，或称两个结点邻接于此边。第1页/共21页 6 6）平行边：）平行边：在无向图中，关

4、联一对顶点的无向边如果多于在无向图中，关联一对顶点的无向边如果多于1 1条，则称这些边为平条，则称这些边为平行边，平行边的条数称为重数行边，平行边的条数称为重数在有向图中，关联一对顶点的有向边如果多于在有向图中，关联一对顶点的有向边如果多于1 1条，并且这些边的条，并且这些边的始点与终点相同始点与终点相同(也就是它们的方向相同也就是它们的方向相同)，则称这些边为平行边，则称这些边为平行边 7 7）多重图和简单图：）多重图和简单图：含平行边的图称为多重图含平行边的图称为多重图既不含平行边也不含环的图称为既不含平行边也不含环的图称为简单图简单图（主要讨论简单图）（主要讨论简单图）4 4、结点的

5、度、结点的度 1 1）定义）定义4 4 设设G GVE为无向图，为无向图，v Vv V，称，称v v作为边的端点次数之作为边的端点次数之和和为为v v的度数，简记为度记作的度数，简记为度记作d d G G(v)(v)，简记为简记为d dG G(v)(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)，

6、称称d d+(v)+d(v)+d-(v)(v)为为 v v的度数，记作的度数，记作d dD D(v)(v)2)2)称度数为称度数为1 1的顶点为悬挂顶点，与它关联的边称为悬挂边的顶点为悬挂顶点，与它关联的边称为悬挂边根据结点的度数可将结点分为：根据结点的度数可将结点分为：度为偶数度为偶数(奇数奇数)的顶点称为的顶点称为偶度偶度(奇度奇度)顶点顶点.有环的结点提供的度为有环的结点提供的度为2 2（有向图的环提供入度（有向图的环提供入度1 1和出度和出度1 1）第2页/共21页3 3）定义：）定义：(G)=maxd(v)|vV(G)(G)=maxd(v)|vV(G)为图为图G G中结点最大的度中

8、中结点最小的出度5 5、握手定理（欧拉）、握手定理（欧拉）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倍倍)证证:G:G中每条边中每条边(包括环包括环)均有两个端点，所以在计算均有两个端点，所以在计算G G中各顶中各顶点度数之和时，每条边均提供点度数之和时，每条边均提供2 2度，当然，度，当然，m m条边共提供条边共提供2m2m度度 2)2)定理定理2 2 设设D D为任意有向图为任意有向图,V,Vvv1 1，v

9、 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)推论推论任何图任何图(无向的或有向的无向的或有向的)中，中，奇度顶点的个数是偶数奇度顶点的个数是偶数第3页/共21页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的度数列的度数列注：由于推论可知，不是任何一个非负整数序列均可作为一个图的度数注：由于推论可知

10、，不是任何一个非负整数序列均可作为一个图的度数列。列。条件：条件：奇度数奇度数的结点个数应该是的结点个数应该是偶数个偶数个（2 2）序列的可图化：）序列的可图化：d=(dd=(d1 1,d,d2 2,d dn n)对一个整数序列对一个整数序列d,d,若存在以若存在以n n个顶点的个顶点的n n阶无向图阶无向图G G，有，有d(vd(vi i)=d)=di i 称该序列是可图化的称该序列是可图化的（3 3）定理）定理设非负整数列设非负整数列d d(d1(d1，d2d2，dn)dn)，则，则d d是可图化的当且是可图化的当且仅当仅当 d di i=0(mod 2)=0(mod 2)(序列之和

11、必须是偶数序列之和必须是偶数)（4 4）由于简单图中没有平行边及环）由于简单图中没有平行边及环结论：结论：n n个结点的个结点的简单图简单图中结点的最大中结点的最大度数（度数（G)G)）应小于等于）应小于等于n-n-1 1 每个结点至多与其他每个结点至多与其他n-1n-1个结点相邻个结点相邻例：给定例：给定5 5个序列哪些是可图化的？哪些是可简单图化的？个序列哪些是可图化的？哪些是可简单图化的？d1=5,5,4,4,2,1 d1=5,5,4,4,2,1 d2=5,4,3,2,2d2=5,4,3,2,2 d3=3,3,3,1d3=3,3,3,1 d4=4,4,3,3,2,2d4=4,4,3,

12、3,2,2 第4页/共21页二、图的同构二、图的同构定义定义设设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)()()的重数的重数相同相同，则称则称

13、G1G1与与G2G2是同构的，记作是同构的，记作Gl Gl G2 G2 定义说明了定义说明了:两个图的各结点之间，如果存在着一一对应关系两个图的各结点之间，如果存在着一一对应关系f f 这种对应关系又保持了这种对应关系又保持了结点间的邻接关系结点间的邻接关系，那么这两个图就是同构，那么这两个图就是同构的的在有向图的情况下，在有向图的情况下，f f不但应该保持结点间的邻接关系，还应该不但应该保持结点间的邻接关系，还应该保持边的方向保持边的方向注：注：1)1)互为互为同构的两个图（必要条件）同构的两个图（必要条件）有有相同样的阶数相同样的阶数（结点）和（结点）和同样数量的边数同样数量的边数及顶点

14、的及顶点的度数序列度数序列但这对于形成图的同构来说，三个条件并不是充分条件（仅是必要条但这对于形成图的同构来说，三个条件并不是充分条件（仅是必要条件）件）2)2)图之间的图之间的同构关系同构关系可看成全体图集合上的二元关系可看成全体图集合上的二元关系具有自反性，对称性和传递性，具有自反性，对称性和传递性，是等价关系是等价关系同构的图为一个等价类，在同构的图为一个等价类，在同构的意义之下都可以看成是一个图。同构的意义之下都可以看成是一个图。例例 (1)(1)画出画出4 4阶阶3 3条边的所有非同构的条边的所有非同构的无向简单图无向简单图结点个数结点个数与与边数相同边数相同，只需找出，只需

15、找出顶点度数序列不同顶点度数序列不同的图（的图（2 23 36 6）：）：第5页/共21页例例 (1)(1)画出画出4 4阶阶3 3条边的所有非同构的无向简单图条边的所有非同构的无向简单图非同构的图但结点个数与边数相同非同构的图但结点个数与边数相同只需找出只需找出顶点度数序列不同的图顶点度数序列不同的图结点总度数：结点总度数：2 23 36 6 如何将度数如何将度数6 6分配给分配给4 4个结点个结点 1 1 1 3 1 1 1 3 相应的图相应的图 2 2 1 1 2 2 1 1 2 2 2 0 2 2 2 0(2)(2)画出画出3 3阶阶2 2条边的所有非同构的条边的所有非同构的有向

16、简单图有向简单图结点个数与边数相同，只需找出结点个数与边数相同，只需找出顶点度（出度及入度）数序列不同顶点度（出度及入度）数序列不同的图的图结点总度数：结点总度数：2 22 24 4 度数分配度数分配 1 2 1 1 2 1 按出度与入度分配：按出度与入度分配：入度列入度列 1 1 01 1 0出度列出度列 0 1 10 1 1入度列入度列 0 2 00 2 0出度列出度列 1 0 11 0 1入度列入度列 1 0 11 0 1出度列出度列 0 2 00 2 0度数分配度数分配 2 2 0 2 2 0 按出度与入度分配：按出度与入度分配：入度列入度列 1 1 01 1 0出度列出度列 1

17、1 01 1 0这只是对较为简单的情这只是对较为简单的情况给出的非同构图，对况给出的非同构图，对于一般的情况（于一般的情况（n,m)n,m)图图到目前为止还没有解决到目前为止还没有解决第6页/共21页三、特殊图完全图与正则图三、特殊图完全图与正则图 1 1）完全图）完全图定义定义设设G G为为n n阶无向简单图，若阶无向简单图，若G G中每个顶点均与其余的中每个顶点均与其余的n n1 1个顶点个顶点相邻，则称相邻，则称G G为为n n阶无向完全图，简称阶无向完全图，简称n n阶完全图阶完全图，记作，记作KnKn(n1)(n1)设设D D为为n n阶有向简单图，若阶有向简单图，若D D中每个

18、顶点都中每个顶点都邻接到邻接到其余的其余的n n1 1个个顶点，又顶点，又邻接于邻接于其余的其余的n n1 1个顶点，则称个顶点，则称D D是是n n阶阶有向完全图有向完全图可画图表示（无向图可画图表示（无向图5 5阶、有向图阶、有向图3 3阶和阶和4 4阶）阶）2)2)完全图的性质：完全图的性质：n n阶无向完全图阶无向完全图G G的边数与结点的关系的边数与结点的关系 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阶无向简单图，若阶无向简

19、单图，若 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正则图正则图第7页/共21页四、子图、生成子图、导出子图四、子图、生成子图、导出子图 1 1、定义、定义设设G GVE，G GV 为两个图为两个图(同为无向图或同为同为无向图或同为有向图有向图)，若若V V V V 且且E E E E ，则称，则称G G是是G G的子图，的子图，G G为为G G的母图，的母图，记作记作G G G G，又又若若V

20、 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 G的的V1V1导出的子图导出的子图，记作，记作GV1GV1 可画图表示可画图表示 G G 及及 G GV1V1 （按书上的例）（按书上的例）结点导出的子图结点导出的子图又设又设E1 E1 E E且且 E1 E1 ，称以，称以

21、E1E1为边集，以为边集，以E1E1中边关联的顶点为中边关联的顶点为顶点集顶点集V1V1的图为的图为G G的的E1E1导出的子图导出的子图，记作，记作GE1GE1 边导出的子边导出的子图图3 3、补图、补图 1 1）定义）定义设设G G VE 为为n n阶无向简单图，以阶无向简单图，以V V为顶点集，以为顶点集，以所有使所有使G G成为完全图成为完全图KnKn的添加边组成的集合为边集的添加边组成的集合为边集的图，的图，称为称为G G的补图的补图，记作，记作G G 2 2）性质性质：设设G G是是n n阶阶k-k-正则图，证明正则图，证明G G的补图的补图G G也是正则图也是正则图对图中任何

22、结点对图中任何结点v v的度有的度有 d G(v)+d d G(v)+d G G(v)(v)=d =d KnKn(v)=n-1(v)=n-1 d d G G(v)(v)=n-1 =n-1 d G(v)d G(v)n-1-k=n-1-k=n-(k+1n-(k+1）3 3）自补图：若图）自补图：若图 G G(G G(同构同构)则称则称G G为自补图为自补图作业：作业：p291 1、3、5、7、8、9、14、15、16、25第8页/共21页14.2 14.2 通路、回路通路、回路一、通路与回路一、通路与回路1 1、通路、通路 1 1）定义：给定有向图）定义：给定有向图D D中的任何一个边序列中的任

23、何一个边序列L L，如果其中的任何，如果其中的任何一条边的一条边的终点终点，都是继之出现的，都是继之出现的边边(如果存在的话如果存在的话)的始点，的始点，则称这样的边的序则称这样的边的序列是图列是图G G的通路。的通路。若序列中若序列中首尾结点相同首尾结点相同，则称，则称L L为回路。为回路。2 2）定义：有向图）定义：有向图D D中，中，边序列中的各条边全都是互不相同边序列中的各条边全都是互不相同的通路，称为的通路，称为简简单通路。单通路。3 3）定义：有向图）定义：有向图D D中，序列中的中，序列中的每一个结点仅出现一次每一个结点仅出现一次的通路，称为的通路，称为初级初级通路通路若序列中

24、若序列中首尾结点相同首尾结点相同，则称通路为，则称通路为初级回路或圈初级回路或圈。4 4）定义：序列中）定义：序列中边的条数边的条数称为它的称为它的长度长度2 2、简单通路和初级通路的关系、简单通路和初级通路的关系有向图中的每一条有向图中的每一条初级通路初级通路，也都，也都必定是简单通路必定是简单通路。反之不成立反之不成立回路也可分为简单回路和初级回路。回路也可分为简单回路和初级回路。3 3、通路的表示：可仅用通路中的、通路的表示：可仅用通路中的边序列表示边序列表示：e e1 1e e2 2e ek k 也可仅用通路中所经过的也可仅用通路中所经过的结点的序列表示结点的序列表示：v v1 1

25、v v2 2v v3 3v vk k 第9页/共21页4 4、性质：、性质：1 1）定理）定理在在n n阶图阶图D D中，若从顶点中，若从顶点vivi到到vj(vivj)vj(vivj)存在通路存在通路，则从，则从vivi到到vjvj存在长度小于或等于存在长度小于或等于(n(n1)1)的通路的通路若大于若大于n-1n-1，则存在相同节点（有回路），将回路删去可得，则存在相同节点（有回路），将回路删去可得 2 2）在）在n n阶图阶图D D中，若从顶点中，若从顶点vivi到到vjvj存在通路存在通路，则，则vivi到到vjvj一定一定存在长度小存在长度小于或等于于或等于n n1 1的初级通路

26、的初级通路(路径路径)3 3）定理）定理在一个在一个n n阶图阶图D D中，若存在中，若存在vivi到自身的到自身的回路回路，则一定存在，则一定存在vivi到到自身长度自身长度小于或等于小于或等于n n的回路的回路 4 4）在一个）在一个n n阶图阶图D D中，若存在中，若存在vivi到自身的到自身的简单回路简单回路，则一定，则一定存在长度小于存在长度小于或等于或等于n n的初级回路的初级回路以上概念均可用在无向图以上概念均可用在无向图G G中中14.3 14.3 图的连通性图的连通性一、无向图的连通性一、无向图的连通性 1 1、结点的连通：、结点的连通：设无向图设无向图G GVE，u,

27、v Vu,v V，若，若u u，v v之间之间存在通路，则称存在通路，则称u,vu,v是连通的是连通的，记作，记作u u v v，u Vu V，规定，规定u uu u 2 2、结点的连通关系是等价关系结点的连通关系是等价关系若定义：若定义：u uv u，vVvV且且 u u与与v v之间有通路之间有通路此关系是自反，对称的，传递的，因而是此关系是自反，对称的，传递的，因而是V V上的等价关系上的等价关系第10页/共21页3 3、无向图的连通图、无向图的连通图定义定义141413 13 若无向图若无向图G G是平凡图或是平凡图或G G中中任何两个顶点都是连通的任何两个顶点都是连通的，则称

28、，则称G G 为连通图，否则称为连通图，否则称G G为非连通图或分离图为非连通图或分离图4 4、结点之间的距离、结点之间的距离 1 1）定义：设）定义：设u u，v v为无向图为无向图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)

29、0v)0，u=uu=u时，等号成立时，等号成立 2 2具有对称性：具有对称性：d(ud(u，v)v)d(vd(v，u)u)3 3满足三角不等式：满足三角不等式：u,v 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总是可达自身的，即总是可达自身的

30、，即vi vivi vi 第11页/共21页2 2、结点的相互可达、结点的相互可达若若vi vj vi vj 且且vj vi vj vi 则称则称vivi与与vjvj是相互可达的，记作是相互可达的，记作:vi:vi vjvj 规定规定vi vi vi vi 3 3、结点的可达关系为结点的可达关系为V V上的二元关系，但上的二元关系，但不是等价关系不是等价关系（不满足对称性）。（不满足对称性）。相互可达关系为相互可达关系为V V上的二元关系，且是上的二元关系，且是V V上的等价关系上的等价关系有向图中顶点之间的可达关系既无对称性，也无反对称性有向图中顶点之间的可达关系既无对称性，也无反对称性

31、4 4、有向图中结点的距离、有向图中结点的距离定义：设定义：设D DVE为有向图为有向图 vi,vj Vvi,vj V，若，若 vi vjvi vj，称，称vivi到到vivi长度最短的通路为长度最短的通路为vivi到到vjvj的短的短程线程线短程线的长度为短程线的长度为vivi到到vjvj的的距离距离，记作，记作dvidvj 注：该定义与无向图中顶点注：该定义与无向图中顶点vivi与与vjvj之间的距离之间的距离d(vid(vi，vj)vj)的区别：无对的区别：无对称性称性一般地：一般地：dvid vj dvjd vi（可能（可能dvid vj 不存在）不存在）5 5、弱连通图、单向连

32、通图和强连通图、弱连通图、单向连通图和强连通图定义定义1 1 设设D DVV，E)E)为一个有向图为一个有向图若若D D的的作为无向图是连通图作为无向图是连通图，则称，则称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是是强连通图强连通图注：三种图的关系：注：三种图的关系：强连

33、通图一定是强连通图一定是单向连通图单向连通图，反之不成立，反之不成立单向连通图一定是单向连通图一定是弱连通图弱连通图反之不成立反之不成立第12页/共21页6 6、有关强连通图与单向连通图的判定、有关强连通图与单向连通图的判定（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中存在经过每个顶点至少一次的中存在经过每个顶点

34、至少一次的通路通路例例2 2设有向图设有向图D D是单向连通图，但不是强连通图，问在是单向连通图，但不是强连通图，问在D D中至少加几条边所得中至少加几条边所得图图D D就能成为强连通图就能成为强连通图?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,

35、e3 3，e em m，令，令m mijij为顶点为顶点v vi i与边与边e ej j的关联次数的关联次数，则称，则称(m(mijij)nxmnxm为为G G的关联矩阵，记的关联矩阵，记作作 M(G)M(G)2 2）关联矩阵的性质）关联矩阵的性质:关联矩阵是关联矩阵是n n行（结点数）行（结点数）m m列（边数）列（边数）的矩阵的矩阵第13页/共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

36、)M(G)第第i i行元素之和为结点行元素之和为结点vivi的度数，的度数，i i1 1，2 2，n n(3)(3)所有行的和（即矩阵所有元素之和）等于边数的所有行的和（即矩阵所有元素之和）等于边数的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的和为的和为

37、0 0（即（即 m mijij=0=0）,当且仅当当且仅当v vi i是孤立点是孤立点2 2、有向图的、有向图的关联矩阵关联矩阵定义：设有向图定义：设有向图D DVE中无环，中无环，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）第14页/共21页 2)2)有向图关联矩阵的性质

38、有向图关联矩阵的性质（1 1）mij=0mij=0，j j1 1，2 2，m m，从而，从而mij=0mij=0，这说明，这说明M(D)M(D)中中所有元素之和为所有元素之和为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)（结点的出度）（结

39、点的出度）（4 4）平行边所对应的列相同）平行边所对应的列相同3 3、有向图的、有向图的邻接矩阵邻接矩阵 1 1）定义：设有向图）定义：设有向图D DVE，V Vv1v1，v2v2，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

40、，2 2，n n 所有所有列的和列的和 aij aij d d+(vi)(vi)m m，等于边数，等于边数每行元素之和为结点的出度每行元素之和为结点的出度，所有行的和也等于边数，所有行的和也等于边数（2 2）邻接矩阵中元素）邻接矩阵中元素 aij aij 反映了反映了有向图中结点有向图中结点vivi到到vjvj通路长度为通路长度为1 1的条数的条数第15页/共21页（3 3）A(D)A(D)中所有元素之和为中所有元素之和为D D中长度为中长度为1 1的（边）通路总条数的（边）通路总条数。主对角线的元素值为图中结点主对角线的元素值为图中结点vivi长度为长度为1 1 的的环的条数环的条数利

41、用利用A(D)A(D)确定出确定出D D中中长度为长度为L L的通路数和回路数的通路数和回路数,就需要用到邻接矩阵的幂就需要用到邻接矩阵的幂次运算次运算（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

42、D的邻接矩阵，的邻接矩阵，V Vv1v1，v2v2，vn vn 为为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中元素中

43、元素 bijbij为为D D中长度小于或等于中长度小于或等于L L的通路数，的通路数，其中主对角线上元素值为其中主对角线上元素值为D D中长度小于或等于中长度小于或等于L L的回路数的回路数第16页/共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）主对角线元素均为

44、）主对角线元素均为1 1（每个结点自身可达）（每个结点自身可达）（2 2）可通过图的邻接矩阵）可通过图的邻接矩阵A A的的n-1n-1次幂次幂B Bn-1n-1得到（将其非零元素换得到（将其非零元素换为为1 1，主对角线元素均设为，主对角线元素均设为1 1即可）即可）第17页/共21页无向图G：V=v1，v2，v3 E=(v1,v2),(v1,v2),(v2,v2),(v2,v2),(v3,v2),(v3,v2),(v1,v3),有向图D：V=v1，v2，v3 E=,返回第18页/共21页返回结点数相同边数相同结点数相同边数相同结点的度相同结点的度相同但是两个图但是两个图不同构不同构第19页/共21页（b),(c)b),(c)互为补图互为补图自补图自补图返回第20页/共21页感谢您的观看。第21页/共21页

展开阅读全文

图论 图基本概念.pptx

图论图基本概念.pptx