图论 图基本概念PPT课件

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为

2、为n n阶零图阶零图，记作，记作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）邻接：）邻接： 边的

3、相邻边的相邻：e ek k，e el lEE若若e 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 两个结点为一条边的端点，则称两个结点两个结点为一条边的端点，则称两个结点互为邻接点互为邻接点， 也称也称边关联于这两个结点边关联于这两个结点，或称两个结点邻接于此边，或称两个结点邻接

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

5、也不含环的图称为简单图简单图（主要讨论简单图）（主要讨论简单图）4 4、结点的度、结点的度 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作为边的

6、终点的次数之和为作为边的终点的次数之和为v v的入度，记作的入度，记作d d+ + (v)(v)， 称称d d+ +(v) + d(v) + d- -( v)( v)为为 v v的度数，记作的度数，记作d dD D (v)(v) 2) 2) 称度数为称度数为1 1的顶点为悬挂顶点，与它关联的边称为悬挂边的顶点为悬挂顶点，与它关联的边称为悬挂边 根据结点的度数可将结点分为：根据结点的度数可将结点分为： 度为偶数度为偶数( (奇数奇数) )的顶点称为的顶点称为偶度偶度( (奇度奇度) )顶点顶点. . 有环的结点提供的度为有环的结点提供的度为2 2（有向图的环提供入度（有向图的环提供入度1 1和出

7、度和出度1 1） 第2页/共21页3 3）定义：）定义：?(G)=maxd(v)|vV(G) (G)=maxd(v)|vV(G) 为图为图G G中结点最大的度中结点最大的度 (G)=mind(v)|vV(G) (G)=mind(v)|vV(G) 为图为图G G中结点最小的度中结点最小的度 简记为简记为?、 定义：定义：?(D)=maxd(v)|vV(D) (D)=maxd(v)|vV(D) 为图为图D D中结点最大的入度中结点最大的入度 ?(D)=maxd(v)|vV(D) (D)=maxd(v)|vV(D) 为图为图D D中结点最大的出度中结点最大的出度 (D)=mind(v)|vV(D)

8、(D)=mind(v)|vV(D) 为图为图D D中结点最小的入度中结点最小的入度 - -(D)=mind(v)|vV(D) (D)=mind(v)|vV(D) 为图为图D D中结点最小的出度中结点最小的出度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中每条边中每条边( (包括环包括环) )均有两个端点，所以在计算均有两个端点

9、，所以在计算G G中各顶中各顶点度数之和时，每条边均提供点度数之和时，每条边均提供2 2度，当然，度，当然，m m条边共提供条边共提供2m2m度度 2) 2) 定理定理2 2 设设D D为任意有向图为任意有向图,V,Vvv1 1，v v2 2，v vn n,|E| = ,|E| = m 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) 结点的度数序列结点的度数序

10、列 (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个

11、顶点的个顶点的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) ( (序列之和必须是偶数序列之和必须是偶数) ) （4 4）由于简单图中没有平行边及环）由于简单图中没有平行边及环 结论：结论：n n个结点的个结点的简单图简单图中结点的最大中结点的最大度数（度数（G)G)）应小于等于）应小于等于n-n-1 1 每个结点至多与其他每个结点

12、至多与其他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,3,2,2 第4页/共21页二、图的同构二、图的同构定义定义 设设G1G1Vl E1 ，G2=V2G2=E2为两个无向图为两个无向图( (两个有向图两个有向图) )， 若存在双射函数若存在双射函数f f：V1 V2 V1 V2 顶点的一一顶点的一一对

13、应对应 对于对于 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 G2 定义说明了定义说明了: :两个图的各结点之间，如果存在着一一对应关系两个图的各结点之间，如果存在着一一对应关系f f 这种对应关系又保持了

14、这种对应关系又保持了结点间的邻接关系结点间的邻接关系，那么这两个图就是同，那么这两个图就是同构的构的 在有向图的情况下，在有向图的情况下，f f不但应该保持结点间的邻接关系，还应该不但应该保持结点间的邻接关系，还应该保持边的方向保持边的方向注：注：1)1) 互为互为同构的两个图（必要条件）同构的两个图（必要条件） 有有相同样的阶数相同样的阶数（结点）和（结点）和同样数量的边数同样数量的边数及顶点的及顶点的度数序列度数序列 但这对于形成图的同构来说，三个条件并不是充分条件（仅是必要条但这对于形成图的同构来说，三个条件并不是充分条件（仅是必要条件）件） 2)2)图之间的图之间的同构关系同构关系可看

15、成全体图集合上的二元关系可看成全体图集合上的二元关系 具有自反性，对称性和传递性，具有自反性，对称性和传递性，是等价关系是等价关系 同构的图为一个等价类，在同构的图为一个等价类，在同构的意义之下都可以看成是一个图。同构的意义之下都可以看成是一个图。例例 (1)(1)画出画出4 4阶阶3 3条边的所有非同构的条边的所有非同构的无向简单图无向简单图 结点个数结点个数与与边数相同边数相同，只需找出，只需找出顶点度数序列不同顶点度数序列不同的图（的图（2 23 36 6）：）： 第5页/共21页例例 (1)(1)画出画出4 4阶阶3 3条边的所有非同构的无向简单图条边的所有非同构的无向简单图 非同构的

16、图但结点个数与边数相同非同构的图但结点个数与边数相同 只需找出只需找出顶点度数序列不同的图顶点度数序列不同的图 结点总度数：结点总度数： 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条边的所有非同构的条边的所有非同构的有向简单图有向简单图 结点个数与边数相同，只需找出结点个数与边数相同，只需找出顶点度（出度及入度）数序列不同顶点度（出度及入度）数序列不同的图的图 结点总度数：结点总度数： 2 22 24 4 度数分

17、配度数分配 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 1 01 1 0这只是对较为简单的情这只是对较为简单的情况给出的非同构图，对况给出的非同构图，对于一般的情况（于一般的情况（n,m)n,m)图图到目前为止还没有解决到目前为止还没有解决第6页/共

18、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中每个顶点都中每个顶点都邻接到邻接到其余的其余的n n1 1个个顶点，又顶点，又邻接于邻接于其余的其余的n n1 1个顶点，则称个顶点，则称D D是是n n阶阶有向完全图有向完全图 可画图表示（无向

19、图可画图表示（无向图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阶无向简单图，若阶无向简单图，若 v V(G)v V(G)，均有，均有d(v)d(v)k k， 则称则称G G为是为是 k-k-正则图正则图 k-k-正则图的边数与结点个数的关系正则图

20、的边数与结点个数的关系 ： 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 GG G， 又又若若V VV V或或E E E E，则称，则称G G为为G G的真子图的真子图 若若V VV(V(且且E E E), E),则称则称G G为为

21、G G的的生成子图生成子图 2 2、设、设G GVE为图，为图，V1V1V V 且且V1 V1 ，称以，称以V1V1为顶点集，以为顶点集，以G G中两个中两个端点都在端点都在V1V1中的边组成边集中的边组成边集E1E1的图为的图为G G的的V1V1导出的子图导出的子图，记作，记作GV1GV1 可画图表示可画图表示 G G 及及 G GV1V1 （按书上的例）（按书上的例）结点导出的子图结点导出的子图 又设又设E1 E1 E E且且 E1 E1 ，称以，称以 E1E1为边集，以为边集，以E1E1中边关联的顶点中边关联的顶点为顶点集为顶点集V1V1的图为的图为G G的的E1E1导出的子图导出的子图

22、，记作，记作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也是正则图也是正则图 对图中任何结点对图中任何结点v v的度有的度有 d G(v) + d d G(v) + d G G(v)(v) = d = d KnKn(v)=

23、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中的任何一个边序列中的任何一个边序列L L，如果其中的任何，如果其中的任何一条边的一条边的终点终点，都是继之出现的，

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

25、圈。 4 4）定义：序列中）定义：序列中边的条数边的条数称为它的称为它的长度长度2 2、简单通路和初级通路的关系、简单通路和初级通路的关系 有向图中的每一条有向图中的每一条初级通路初级通路，也都，也都必定是简单通路必定是简单通路。 反之不成立反之不成立 回路也可分为简单回路和初级回路。回路也可分为简单回路和初级回路。3 3、通路的表示：可仅用通路中的、通路的表示：可仅用通路中的边序列表示边序列表示：e e1 1e e2 2e ek k 也可仅用通路中所经过的也可仅用通路中所经过的结点的序列表示结点的序列表示：v v1 1v v2 2v v3 3v vk k 第9页/共21页4 4、性质：、性质

26、： 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的初级通路的初级通路( (路径路径) ) 3 3）定理）定理 在一个在一个n n阶

27、图阶图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,v Vu,v V，若，若u u，v v之间之间存在通路，则

28、称存在通路，则称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中中任何两个顶点都是连通的任何两个顶点都是连通的，则称，则称G G 为连通图，否则称为连通图，否则称G G为

29、非连通图或分离图为非连通图或分离图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) 0v) 0，u = uu = u时，等号成立时

30、，等号成立 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总是可达自身的，即总是可达自身的，即vi

31、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上的等价关系上的等价关系 有向图中顶点之间的可达关系既无对称性，也无反对称性有向图中顶点之间的可达关系既无对称性，也无反对称性

32、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、弱连通图、单向

33、连通图和强连通图、弱连通图、单向连通图和强连通图 定义定义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是是强连通图强连通图 注：三种图的关系：注：三种图的

34、关系：强连通图一定是强连通图一定是单向连通图单向连通图，反之不成立，反之不成立 单向连通图一定是单向连通图一定是弱连通图弱连通图反之不成立反之不成立 第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中存在经过每个顶点至少一次的中

35、存在经过每个顶点至少一次的通路通路例例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=e

36、1 1,e,e2 2,e,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

37、 = 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) 所有行的和（即矩阵所有元素之和）等于边数的所有行的和（即矩阵所有元素之和）等于边数的2 2倍（该例倍（该例1010边数边数5 5的的2 2倍）。倍）。 d(vd(vi i) )m mijij= 2 = 2 2m2m，这个结果正是握手定理的内容，这个结果正是握手定理的内容（即各顶点的度数之和等于边数的（即各顶点的度数之和等于边数的2 2倍）倍） （4 4）第）第j j列与第列与第k k列相同，当且仅当边列相同，当且

38、仅当边ejej与与ekek是平行边是平行边 (5) (5) 某行某行i i的和为的和为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) )

39、nxmnxm，为，为D D的关联矩阵，记作的关联矩阵，记作M(DM(D） 第14页/共21页 2)2)有向图关联矩阵的性质有向图关联矩阵的性质 （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的个数

40、等于的个数等于d+(vi)d+(vi)（结点的入度），负（结点的入度），负1 1的个数等于的个数等于d-(vi)d-(vi)（结点的出度）（结点的出度） （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）邻接矩阵的

41、性质）邻接矩阵的性质 （1 1）每列元素之和为结点的入度，即）每列元素之和为结点的入度，即 aij aij d+(vi)d+(vi)，i i1 1，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的（边）通路总条数的（边）通路总条数