离散数学第七章图论

1、4/26/20221第七章图 论离离散散数数学学第第七七章章 图图论论 4/26/20222图论的起源图论的起源问题：能否从河岸或小岛出发，不重复地经过所问题：能否从河岸或小岛出发，不重复地经过所有的桥回到原地。有的桥回到原地。ACBDKonigsberg(哥尼斯堡哥尼斯堡)七桥问题七桥问题离离散散数数学学第第七七章章 图图论论 4/26/20223 Euler将河岸和小岛作为图的结点，七座桥为将河岸和小岛作为图的结点，七座桥为边，构成一个无向重图，问题化为图论中简单道路边，构成一个无向重图，问题化为图论中简单道路的问题。的问题。ACBD Euler (欧拉欧拉) 1736年对这个问题给出了否

2、定的回答。年对这个问题给出了否定的回答。离离散散数数学学第第七七章章 图图论论 4/26/20224一、图的基本概念一、图的基本概念洛杉矶洛杉矶旧金山旧金山芝加哥芝加哥丹佛丹佛华盛顿华盛顿底特律底特律纽约纽约离离散散数数学学第第七七章章 图图论论 4/26/20225设设A A、B B是两个集合，称是两个集合，称 A&B=a,b|aA&B=a,b|a A, bA, b BB为为A A与与B B的的无序积无序积。为方便起见，常将无序对为方便起见，常将无序对a,ba,b记为记为(a,b)(a,b)定义定义1.1 1.1 一个一个无向图无向图是一个有序的二元组是一个有序的二元组，记为

3、记为G G，其中，其中（1 1）称为称为结点结点集集，元素称为，元素称为结点结点或或顶点顶点；（2 2）称为）称为边集边集，它是无序积，它是无序积V&VV&V的多重子集，的多重子集，其元素称为其元素称为无向边无向边，简称为，简称为边边。 常把无向图记为常把无向图记为G=G=离离散散数数学学第第七七章章 图图论论 4/26/20226例例1 1、G G1 1= V Vvv0 0, v, v1 1, v, v2 2,v,v3 3 E E(v(v0 0,v,v2 2),(v),(v0 0,v,v3 3),(v),(v1 1,v,v2 2),(v),(v1 1,v,v3 3),(v),

4、(v2 2，v v3 3)v0v3v2v1G1离离散散数数学学第第七七章章 图图论论 4/26/20227G2v0v1v2v3例例2 2、G G2 2= V Vvv0 0, v, v1 1, v, v2 2,v,v3 3 E E(v(v0 0,v,v3 3),(v),(v1 1,v,v3 3),(v),(v1 1,v,v3 3),(v),(v2 2，v v3 3),(v),(v0 0,v,v0 0)平行边平行边环环G 简单图简单图（不含平行边也不含环）不含平行边也不含环）多重图多重图离离散散数数学学第第七七章章 图图论论 4/26/20228洛杉矶洛杉矶旧金山旧金山芝加哥芝加哥丹佛丹佛华盛顿华

5、盛顿底特律底特律纽约纽约离离散散数数学学第第七七章章 图图论论 4/26/20229定义定义1.2 1.2 一个一个有向图有向图是一个有序的二元组是一个有序的二元组，记为记为D D，其中，其中（1 1）同无向图；）同无向图；（2 2）称为）称为边集边集，它是笛卡尔积，它是笛卡尔积V VV V的多重子集，的多重子集，其元素称为其元素称为有向边有向边，简称为，简称为边边。 v0v1v2DD= Vv0, v1, v2， E, , 离离散散数数学学第第七七章章 图图论论 4/26/202210例例3、 D=, 其中其中V=v1，v2 ，v3 ，v4 E=, ,v1v2v3v4平行边平行边离离散散数数学

6、学第第七七章章 图图论论 4/26/202211有时用有时用G泛指图（有向的或无向的）泛指图（有向的或无向的）|V(G)|表示表示G的结点数的结点数|E(G)|表示表示G的边数的边数有限图有限图 |V(G)|和和 |E(G)|均有限均有限n阶图阶图|V(G)|=n零图零图 E(G)= 洛杉矶洛杉矶旧金山旧金山芝加哥芝加哥丹佛丹佛华盛顿华盛顿底特律底特律纽约纽约平凡图平凡图1阶零图阶零图空图空图 V(G)= 离离散散数数学学第第七七章章 图图论论 4/26/202212标定图标定图非标定图非标定图在无向图在无向图G=中，若中，若ek=（vi，vj） ，则，则称称vi，vj 为为边边ek的的端点端

7、点, ek与与vi或或ek与与vj是是彼此关联的彼此关联的；关联次数关联次数邻接点、邻接边邻接点、邻接边v1v2v3v4v5 孤立点孤立点 e1e0e4e3e2e5(v3，v4)离离散散数数学学第第七七章章 图图论论 4/26/202213在有向图在有向图D=中，若中，若ek= ，则，则称称vi为为ek 的的起点起点， vj 为为ek的的终点终点 ；并称；并称vi邻接到邻接到vj ， vj邻接于邻接于vi 。v1v2v3v4离离散散数数学学第第七七章章 图图论论 4/26/202214定义定义1.3 1.3 在图在图G=G= 中，中，与结点与结点v v（v v V V）关联的）关联的边数称为结

8、点边数称为结点v v的的度数，度数，简称简称度，度，记为记为deg(v)deg(v)。( (结点上的环关联次数为结点上的环关联次数为2)2)e2v1v2v3v4e4e3e5e1v2e3v4v1v3e1e2e4e5设设D=为有向图，为有向图，以结点以结点v（v V）作为始）作为始点的边数称为点的边数称为v的的出度，出度，记作记作deg+(v)；以以v作为终作为终点的边数称为点的边数称为v的的入度，入度，记作记作deg-(v)称称deg+(v)+deg-(v)为为v的度数，记作的度数，记作deg(v) deg(v1)=deg(v4)=2 deg(v2)=deg(v3)=3 deg+(v1)=3 d

9、eg+(v2)= deg+(v4)=1 deg+(v3)=0 deg-(v1)= deg-(v2)=deg-(v4)=1 deg-(v3)=2 离离散散数数学学第第七七章章 图图论论 4/26/202215在无向图在无向图G G中，中， 令令(G)=maxdeg(v)|v(G)=maxdeg(v)|v V(G)V(G) (G)=mindeg(v)|v(G)=mindeg(v)|v V(G)V(G)最大度最大度最小度最小度类似可定义有向图的类似可定义有向图的最大出度最大出度和和最小出度最小出度、最大入最大入度度和和最小入度最小入度。有向图中，所有结点的入度之和等于所有结点的出有向图中，所有结点的

10、入度之和等于所有结点的出度之和。度之和。离离散散数数学学第第七七章章 图图论论 4/26/202216定理定理1.1 设设G=为无向图，为无向图， |V(G)|= n，|E(G)|=m，则，则niimv12)deg(e2v1v2v3v4e4e3e5e1对图的所有顶点的度求和时，得出了什么？对图的所有顶点的度求和时，得出了什么？即使出现多重边和环，这即使出现多重边和环，这个式子仍然成立个式子仍然成立握手定理握手定理n=4m=4顶点度之和为顶点度之和为8n=4m=5结点度之和为结点度之和为10一个具有一个具有10个顶点，每个顶点，每个结点的度都为个结点的度都为6的图，的图，有多少条边？有多少条边？

11、离离散散数数学学第第七七章章 图图论论 4/26/202217定理定理1.2 设设D=为为有有向图，向图， |V(D)|= n，|E(D)|=m，则，则v2e3v4v1v3e1e2e4e5niimv1)(degniimv1)(degniimv12)deg(n=4m=5结点入度之和为结点入度之和为5结点出度之和为结点出度之和为5离离散散数数学学第第七七章章 图图论论 4/26/202218推论推论 无向图中度数为奇数的结点个数是偶数。无向图中度数为奇数的结点个数是偶数。证明：证明：设设V1和和V2分别是偶度结点和奇度结点的集合分别是偶度结点和奇度结点的集合,则则12iiVviVVv)deg()d

12、eg()deg(2viiivvvm偶数偶数偶数偶数偶数偶数因此因此|V2 |为偶数为偶数任何图任何图e2v1v2v3v4e4e3e1离离散散数数学学第第七七章章 图图论论 4/26/202219例例4、已知无向图已知无向图G中结点数中结点数n与边数与边数m相等，相等，2度度结点与结点与3度结点各度结点各2个，其余结点的度数均为个，其余结点的度数均为1，试，试求求G的边数的边数m。niivm1)deg(2=2 2+ 3 2+ 1 (n-4)=n+62m=n+6m=n m=6解：由握手定理解：由握手定理离离散散数数学学第第七七章章 图图论论 4/26/202220定义定义1.4 设设G为为n阶无向

13、简单图，若阶无向简单图，若G中每一对中每一对结点之间都有边，则称结点之间都有边，则称G为为n阶无向完全图阶无向完全图，简称简称n阶完全图阶完全图，记作，记作Kn (n1)k1k2k3k4aedcbk5离离散散数数学学第第七七章章 图图论论 4/26/202221定义定义1.4 设设D为为n阶有向简单图，若阶有向简单图，若D中每个结中每个结点都邻接到其余的点都邻接到其余的n-1个结点，又邻接于其余个结点，又邻接于其余的的n-1个结点，则称个结点，则称D为为n阶有向完全图阶有向完全图。k1k3k2离离散散数数学学第第七七章章 图图论论 4/26/202222定义定义1.5 1.5 设设 为为n n

14、阶无向简单图，阶无向简单图，以以V V为结点集，以所有使为结点集，以所有使G G成为完全图成为完全图K Kn n的添加的添加边组成的集合为边集的图，称为边组成的集合为边集的图，称为的相对于完的相对于完全图的全图的补图补图，记作，记作k4GGG定理定理1.3 n阶无向完全图阶无向完全图Kn的边数为的边数为n(n-1)/2；n阶有向完全图的边数为阶有向完全图的边数为？ 。n(n-1)离离散散数数学学第第七七章章 图图论论 4/26/202223aedcb图 K5图 Gedcbadbaec图 G1aedcb图 G3离离散散数数学学第第七七章章 图图论论 4/26/202224k4GG离离散散数数学学

15、第第七七章章 图图论论 4/26/202225定义定义1.6 设设G=，G= 为两个图，为两个图，若若V V且且E E，则称，则称为的为的子图子图，G G为为GG的的母图母图，记作，记作 ；又若又若V V或或E E，则称，则称为的为的真子图。真子图。若若V=V，则称，则称为的为的生成子图生成子图k4G2G1离离散散数数学学第第七七章章 图图论论 4/26/202226在下图中，在下图中，G1，G2，G3均是均是G的真子图，其中的真子图，其中G2、G是是G的生成子图。的生成子图。e3e2e1e4e5e7e6abdeGe3e2e1e4abdG1cce3e4e6abdeG2ce4e5adeG3离离散

16、散数数学学第第七七章章 图图论论 4/26/202227定义定义1.7 1.7 设设G G = V= 是是 的子的子图，若给定另外一个图图，若给定另外一个图 ，使得使得=E-E=E-E ，且，且中仅包含中仅包含的边所的边所关联的结点，则称为关联的结点，则称为是子图相对于图是子图相对于图G G的的补图补图。 GdbaecdbecGdbaeGdbaeG离离散散数数学学第第七七章章 图图论论 4/26/202228定义定义1.8 1.8 设设G G1 1=V=,G,G2 2= V= 为两个无向为两个无向图，若存在一一映射图，若存在一一映射 g g： V V1 1 V V2 2 对于对于 v vi i

17、,v,vj j V V1 1，(v(vi i,v,vj j) ) E E1 1 当且仅当当且仅当 (g(v(g(vi i),g(v),g(vj j) E E2 2, ,并且并且(v(vi i,v,vj j) )与与(g(v(g(vi i),g(v),g(vj j)的重数相同，的重数相同，则称则称G G1 1与与G G2 2是是同构同构的，记作的，记作G G1 1 G G2 2怎样定义有向图的同构？怎样定义有向图的同构？离离散散数数学学第第七七章章 图图论论 4/26/202229 a d c b b (c)a (b)c (a)d例例7、(d)离离散散数数学学第第七七章章 图图论论 4/26/2

18、02230彼得松图彼得松图(petersen)1234567891012345689710离离散散数数学学第第七七章章 图图论论 4/26/202231离离散散数数学学第第七七章章 图图论论 4/26/202232两个图同构必有：两个图同构必有：（1）结点数相同；）结点数相同；（2）边数相同；）边数相同；（3）度数列相同）度数列相同但不是充分条件但不是充分条件（满足这三个条件的两图（满足这三个条件的两图不一定同构）不一定同构）离离散散数数学学第第七七章章 图图论论 4/26/202233例例8、 画出画出K4的所有非同构的生成子图。的所有非同构的生成子图。 解：解： K4的所有非同构的生成子图

19、如下图所示。的所有非同构的生成子图如下图所示。 离离散散数数学学第第七七章章 图图论论 4/26/202234二、路与回路二、路与回路定义定义2.1 设设为无向标定图，为无向标定图，G G中结点与边中结点与边的交替序列的交替序列 = =v vi0i0e ej1j1v vi1i1e ej2j2eejljlv vilil称为称为v vi0i0到到v vilil的的路路。v vi0i0，v vilil分别称为分别称为 的始点和终点，的始点和终点， 中边的条数称为它的中边的条数称为它的长度。长度。 当当v vi0i0= v= vilil时，该路称为时，该路称为回路回路。e2v1v2v3v4e4e3e5

20、e1离离散散数数学学第第七七章章 图图论论 4/26/202235 若路中没有重复的边，则称为若路中没有重复的边，则称为迹迹。若若路路中没有重复的点，则称为中没有重复的点，则称为通路通路。闭的通路称为闭的通路称为圈圈。e2v1v2v3v4e4e3e5e1离离散散数数学学第第七七章章 图图论论 4/26/202236e3e5e2e1dcbae4（5，1 ，2 ，3，4）是迹，不是通路，因）是迹，不是通路，因为（，）中，均出现了为（，）中，均出现了两次。（两次。（c，d，b，c）是圈。）是圈。有向图中，路、回路等概念与无向图类似有向图中，路、回路等概念与无向图类似离离散散数数学学第第七七章章 图图

21、论论 4/26/202237 定理定理2.1 2.1 在在n n阶图中，若从结点阶图中，若从结点v vi i到到v vj j（v vi i v vj j）存在一条路，则从存在一条路，则从v vi i到到v vj j存在长度不大于存在长度不大于n-1n-1的路。的路。推论推论 在在n n阶图中，若从阶图中，若从结点结点vi到到vj（vivj）存在一存在一条路，则从条路，则从vi到到vj存在长度小于存在长度小于n的通路。的通路。离离散散数数学学第第七七章章 图图论论 4/26/202238定义定义2.2 2.2 设无向图设无向图， u,v ，若，若u,v之间存在路，则称之间存在路，则称u,v是是连

22、通连通的，记作的，记作u v 。定义定义2.3 设无向图是平凡图或设无向图是平凡图或G中任何两个结中任何两个结点都是连通的，则称点都是连通的，则称G为为连通图连通图，否则称，否则称G为为非连非连通图通图或或分离图分离图。 任意一个连通无向图的任意一个连通无向图的任两个不同结任两个不同结点都存在一条通路。点都存在一条通路。离离散散数数学学第第七七章章 图图论论 4/26/202239k4 A B W（G）=1W（G）=2 非连通图可分为几个不相连通的子图，非连通图可分为几个不相连通的子图，每一子图本身都是连通的。称这几个子图为每一子图本身都是连通的。称这几个子图为的连通分支的连通分支,G,G的连

23、通分支数记为的连通分支数记为W W（G G）。）。离离散散数数学学第第七七章章 图图论论 4/26/202240设设G=为无向图为无向图(1)设设e E，用，用G-e表示从表示从G中去掉边中去掉边e，称为，称为删删除边除边e；又设；又设E E，用，用G-E 表示从表示从G中删除中删除E 中的所有边，称为删除中的所有边，称为删除E 。(2)设设v V，用，用G-v表示从表示从G中去掉中去掉v及所关联的及所关联的一切边，称为一切边，称为删除结点删除结点v；又设；又设V V，用，用G-V 表示从表示从G中删除中删除V 中所有结点，称为删除中所有结点，称为删除V 。e离离散散数数学学第第七七章章 图图

24、论论 4/26/202241定义定义2.4 2.4 设无向图设无向图为连通图，为连通图， 若存若存在在V1 V ，且，且V1 ，使得，使得W(G-V1) 1， 而对于而对于任意的任意的V2 V1，均有，均有W(G-V2)= 1， 则称则称V1是是G的的点割集点割集，若是，若是V1=v，则称，则称v为为割点割点。W(G)W(G)离离散散数数学学第第七七章章 图图论论 4/26/202242定义定义2.5 2.5 设无向图设无向图， 若存在若存在E E ，且且E ，使得，使得W(G-E )W(G)，而对于任意的，而对于任意的E E ，均有，均有W(G-E)=W(G)，则称，则称E 是是G的的边割边

25、割集集，若是，若是E =e，则称，则称e为为割边割边或或桥桥。离离散散数数学学第第七七章章 图图论论 4/26/202243定义定义2.6 2.6 设为非完全的无向连通图，设为非完全的无向连通图， 称称 (G)=min|V | | V 为为G的点割集的点割集为为G的的点连通度点连通度（或连通度）（或连通度） 设为无向连通图，设为无向连通图， 称称 (G)=min|E | | E 为为G的边割集的边割集为为G的的边连通度边连通度。 为了产生一个不连通图为了产生一个不连通图需要删去的最少的点数需要删去的最少的点数易见：非连通图的点连通度为易见：非连通图的点连通度为0，边连通度也为，边连通度也为0。

26、完全图完全图Kn的点连通度为的点连通度为n-1。离离散散数数学学第第七七章章 图图论论 4/26/202244定理定理2.2 对于任何无向图对于任何无向图G，有，有 (G) (G) (G)证明：证明：若若G不连通，则不连通，则 (G)= (G)=0 (G)若若G连通连通 1）证）证 (G)(G) 若若G是平凡图，则是平凡图，则 (G)=0 (G) 若若G不是平凡图，则因每个结点的所有关不是平凡图，则因每个结点的所有关联的边必含一个边割集，所以联的边必含一个边割集，所以 (G)(G) 离离散散数数学学第第七七章章 图图论论 4/26/2022452）证）证 (G) (G) 设设 (G)=1，即有

27、一割边，则，即有一割边，则 (G)=1 设设 (G) 2，离离散散数数学学第第七七章章 图图论论 4/26/202246定理定理2.3 一个连通无向图一个连通无向图G中的结点中的结点v是割点是割点的充分必要条件是存在两个结点的充分必要条件是存在两个结点u和和w，使得，使得结点结点u和和w的每一条路都通过的每一条路都通过v。离离散散数数学学第第七七章章 图图论论 4/26/202247定义定义2.7 2.7 设设D=D=为有向图，为有向图， vi，vj V V，若从，若从vi到到vj存在路，则称存在路，则称vi可达可达vj ，记作记作vivj，规定，规定vivi ，如果，如果vivj，且，且vj

28、vi，则称则称vj与与vi是互相可达的，是互相可达的，记作记作vi vj 定义定义2.8 2.8 设设D为有向图为有向图， vi，vj ，若若vivj，称称vi到到vj长度最短的路称为长度最短的路称为vi 到到vj的的短程短程线线，短程线的长度称为短程线的长度称为vi 到到vj的距离，的距离，记作记作d。易见易见 d 0 d+ d d 如果从如果从vi到到vi不可达，则记为不可达，则记为d = 离离散散数数学学第第七七章章 图图论论 4/26/202248定义定义2.9 2.9 设设D=D=为简单有向图，为简单有向图，若若 vi，vj V V，vivj与与vjvi至少有一个成立，则称至少有一个

29、成立，则称D D是是单侧连通单侧连通图图。若对。若对 vi，vj V V，均有，均有vi vj，则称，则称D为为强连强连通图通图。若在若在D D中略去边的方向，将它看成无向图后是中略去边的方向，将它看成无向图后是连通图，连通图，则称为则称为弱连通图弱连通图。弱弱连连通通 强强连连通通: 离离散散数数学学第第七七章章 图图论论 4/26/202249定理定理2.4 2.4 设设D D为有向图，为有向图，D D是强连通图当且仅当是强连通图当且仅当D D中中存在经过每个结点至少一次的回路存在经过每个结点至少一次的回路。D D是单向连通图当且仅当是单向连通图当且仅当D D中存在经过每个结点至少中存在经

30、过每个结点至少一次的路一次的路。离离散散数数学学第第七七章章 图图论论 4/26/202250定义定义2.10 2.10 在简单有向图中，具有强连通性质的最在简单有向图中，具有强连通性质的最大子图，称为强分图；具有单侧连通性质的最大子大子图，称为强分图；具有单侧连通性质的最大子图，称为单侧分图；具有弱连通性质的最大子图，图，称为单侧分图；具有弱连通性质的最大子图，称为弱分图称为弱分图。定理定理2.5 2.5 在有向图在有向图D D中，它的每个结点位于且只位中，它的每个结点位于且只位于一个强分图中于一个强分图中。离离散散数数学学第第七七章章 图图论论 4/26/202251三、图的矩阵表示三、图

31、的矩阵表示图图G的三种表示方法：的三种表示方法：（1）集合表示）集合表示（2）图形表示）图形表示（3）矩阵表示）矩阵表示 1、邻接矩阵表示、邻接矩阵表示 2、关联矩阵表示、关联矩阵表示离离散散数数学学第第七七章章 图图论论 4/26/202252定义定义3.1 设无向图设无向图G=是简单图，是简单图，V=v1,v2,vn, 称称(aij)nn为为G的的邻接矩阵邻接矩阵，记作，记作A(G)，其中，其中v1v2v3v40 1 1 01 0 1 11 1 0 10 1 1 0A(G)=此矩阵有何特征？此矩阵有何特征？对称对称aij=1 （vi，vj） E0 （vi，vj） E 或或i=j第第i行上行

32、上1的个数等于结点的个数等于结点vi的度数的度数离离散散数数学学第第七七章章 图图论论 4/26/202253定义定义3.1 设有向图设有向图D=，V=v1,v2,vn, E=e1,e2,em, 令令aij为顶点为顶点vi邻接到顶点邻接到顶点vj的边的条数，则称的边的条数，则称(aij)nn为为D的的邻接矩阵邻接矩阵，记作，记作A(D)。v1v2v3v4V1V2V3v4 v1 v2 v3 v4 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0此矩阵有何特征？此矩阵有何特征？A(D)=第第i行上行上1的个数等于结点的个数等于结点vi的出度，的出度，第第j行上行上1的个数等于结点的个

33、数等于结点vj的入度的入度离离散散数数学学第第七七章章 图图论论 4/26/202254v1v2v3v4 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0A(D)=计算计算(A(D)2， (A(D)3v1v2v3v4对无向图G，计算(A(G)2， (A(G)3离离散散数数学学第第七七章章 图图论论 4/26/202255定理定理3.1 设设A为图为图G的邻接矩阵，的邻接矩阵，V=v1,v2,vn为为G的结点集，的结点集，则则A的的k次幂次幂Ak(k1)中元素中元素aij(k)为为G中中vi到到vj长度为长度为k的路数，的路数，其中其中aii(k)为到自身长度为为到自身长度为k的回

34、路数，而的回路数，而 aij(k)i=1 j=1n n为为G中长度为中长度为k的路的总数，的路的总数， aii(k)i=1n其中其中为为G中长度为中长度为k的回路总数。的回路总数。离离散散数数学学第第七七章章 图图论论 4/26/202256定义定义3.2 设简单有向图设简单有向图D=，V=v1,v2,vn, 令令pij=1 vi可达可达 vj0 否则否则则称则称(pij)nn为为D的的可达矩阵可达矩阵，记作，记作P(D)。v1v2v3v4e1e2e3e4e5V1V2V3v4 v1 v2 v3 v4 1 1 1 1 1 1 1 1 0 0 1 0 0 0 1 1P(D)=离离散散数数学学第第七

35、七章章 图图论论 4/26/202257无向简单图无向简单图G定义定义3.3 设无向图设无向图G=，V=v1,v2,vn, E=e1,e2,em, 令令mij为结点为结点vi与边与边ej的关联次数，则称的关联次数，则称(mij)nm为为G的的关联矩阵关联矩阵，记作，记作M(G)。v1v2v3v4e1e4e3e2e50 0 0 11 1 1 0 00 0 1 1 10 1 0 1 0M(G)=此矩阵有何特征？此矩阵有何特征？离离散散数数学学第第七七章章 图图论论 4/26/202258有向简单图有向简单图D定义定义3.3 设有向图设有向图D=，V=v1,v2,vn, E=e1,e2,em, 令令

36、则称则称(mij)nm为为D的的关联矩阵关联矩阵，记作，记作M(D)。1 vi为为ej的始点的始点 0 vi与与ej不关联不关联 -1 vi为为ej的终点的终点 mij=离离散散数数学学第第七七章章 图图论论 4/26/202259v1v2v3v4e1e2e3e4e5V1V2V3v4e1 e2 e3 e4 e5 1 0 1 -1 1 0 0 0 1 -1 0 -1 -1 0 0-1 1 0 0 0M(D)=离离散散数数学学第第七七章章 图图论论 4/26/202260 【例【例8.1.4】 证明在证明在n（n2）个人的团）个人的团体中，总有两个人在此团体中恰好有相同个数体中，总有两个人在此团体

37、中恰好有相同个数的朋友。的朋友。 解解 以结点代表人，二人如果是朋友，则以结点代表人，二人如果是朋友，则在代表他们的结点间连上一条边，这样可得无在代表他们的结点间连上一条边，这样可得无向简单图向简单图G，每个人的朋友数即图中代表它的，每个人的朋友数即图中代表它的结点的度数，于是问题转化为：结点的度数，于是问题转化为：n阶无向简单阶无向简单图图G中必有两个结点的度数相同。中必有两个结点的度数相同。 用反证法，设用反证法，设G中各顶点的结数均不相中各顶点的结数均不相同，则度数列为同，则度数列为0，1，2，n-1，说明图，说明图中有孤立结点，这与有中有孤立结点，这与有n-1度结点相矛盾（因度结点相矛

38、盾（因为是简单图），所以必有两个结点的度数相同。为是简单图），所以必有两个结点的度数相同。离离散散数数学学第第七七章章 图图论论 4/26/202261 【例8.2.1】 一个人带着一只狼、一只羊和一捆草要渡河，由于船太小，人做摆渡者一次只能运送一个“乘客”，很显然，如果人不在，狼要吃羊，羊要吃草，问人怎样才能把它们平安地渡过河去？离离散散数数学学第第七七章章 图图论论 4/26/202262 解解 这是通路问题的一个典型实例。用这是通路问题的一个典型实例。用f表表示人，示人，w表示狼，表示狼，s表示羊，表示羊，h表示草。表示草。 集合集合f，w，s，h中能平安在一起的子中能平安在一起的子集有

39、：集有：f，w，s，h，f，w，s，f，s，h，f，w，h，f，w，f，s，f，h，w，h，f，w，s，h。用。用顶点表示渡河过程中的状态，状态是二元组：顶点表示渡河过程中的状态，状态是二元组：第一元素是集合第一元素是集合f，w，s，h在渡河过程中在渡河过程中留在原岸的子集，第二元素是在彼岸的子集，留在原岸的子集，第二元素是在彼岸的子集，将一次渡河后代表状态变化的顶点间连边，得将一次渡河后代表状态变化的顶点间连边，得图图8.2.1。容易看出，一条路径就是一种渡河。容易看出，一条路径就是一种渡河方案。方案。离离散散数数学学第第七七章章 图图论论 4/26/202263 图 8.2.1 离离散散数

40、数学学第第七七章章 图图论论 4/26/202264 【例【例8.2.4】 在一次国际会议中，由七人在一次国际会议中，由七人组成的小组组成的小组a,b,c,d,e,f,g中，中，a会英语、阿拉会英语、阿拉伯语；伯语；b会英语、西班牙语；会英语、西班牙语；c会汉语、俄语；会汉语、俄语；d会日语、西班牙语；会日语、西班牙语；e会德语、汉语和法语；会德语、汉语和法语；f会会日语、俄语；日语、俄语；g会英语、法语和德语。问：他们会英语、法语和德语。问：他们中间任何二人是否均可对话（必要时可通过别人中间任何二人是否均可对话（必要时可通过别人翻译）？翻译）？dabfgce离离散散数数学学第第七七章章 图图

41、论论 4/26/202265 解解 用顶点代表人，如果二人会同一种语用顶点代表人，如果二人会同一种语言，则在代表二人的顶点间连边，于是得到图言，则在代表二人的顶点间连边，于是得到图8.2.3。问题归结为：在这个图中，任何两个。问题归结为：在这个图中，任何两个顶点间是否都存在着通路？由于图顶点间是否都存在着通路？由于图8.2.3是一是一个连通图，因此，必要时通过别人翻译，他们个连通图，因此，必要时通过别人翻译，他们中间任何二人均可对话。中间任何二人均可对话。 在连通图中，如果删去一些顶点或边，在连通图中，如果删去一些顶点或边，则可能会影响图的连通性。所谓从图中删去某则可能会影响图的连通性。所谓从

42、图中删去某个顶点个顶点v，就是将顶点，就是将顶点v和与和与v关联的所有的边关联的所有的边均删去，我们用均删去，我们用G-v记之，并用记之，并用G-V表示从表示从G中删去中删去V的子集的子集V。用。用G-e表示删去边表示删去边e，用，用G-E表示从表示从G中删去中删去E的子集的子集E。离离散散数数学学第第七七章章 图图论论 4/26/202266【例【例8.4.1】 判断下列各命题是否是真命题。判断下列各命题是否是真命题。（1）任何有相同顶点数和边数的无向图都同构。）任何有相同顶点数和边数的无向图都同构。（2）图中的初级回路均是简单回路。）图中的初级回路均是简单回路。（3）任一图）任一图G的最大

43、度数的最大度数（G）必小于）必小于G的顶点数。的顶点数。（4）在）在n（n2）个人中，不认识另外奇数个人的有）个人中，不认识另外奇数个人的有偶数个人。偶数个人。离离散散数数学学第第七七章章 图图论论 4/26/202267 解答与分析解答与分析（1）假命题。两个图有相同顶点数和边数是二图同）假命题。两个图有相同顶点数和边数是二图同构的必要条件，而非充分条件。构的必要条件，而非充分条件。（2）真命题。由初级回路和简单回路的定义可知。）真命题。由初级回路和简单回路的定义可知。（3）假命题。当）假命题。当G非简单图时，非简单图时，（G）可大于顶点）可大于顶点数。数。（4）真命题。将）真命题。将n个人

44、抽象成个人抽象成n个顶点，若两个人不个顶点，若两个人不认识，则在他们的对应顶点之间画一条边，得到无认识，则在他们的对应顶点之间画一条边，得到无向图向图G。G中每个顶点的度数就是该顶点所对应的中每个顶点的度数就是该顶点所对应的人不认识的其他人的个数，由握手定理的推论可知，人不认识的其他人的个数，由握手定理的推论可知，G中奇度数的顶点必有偶数个。故在中奇度数的顶点必有偶数个。故在n个人中，不个人中，不认识另外奇数个人的有偶数个人。认识另外奇数个人的有偶数个人。离离散散数数学学第第七七章章 图图论论 4/26/202268 【例【例8.4.2】 在六个人的团体中，至少有在六个人的团体中，至少有三个人

45、彼此认识或彼此不认识。三个人彼此认识或彼此不认识。 分析分析 将六个人抽象成六个顶点，若两个将六个人抽象成六个顶点，若两个人认识，则在他们的对应顶点之间画一条边，人认识，则在他们的对应顶点之间画一条边，得到无向图得到无向图G，则，则G是是6阶无向简单图，阶无向简单图， 中中的边则表示他们关联的两个顶点代表的人彼此的边则表示他们关联的两个顶点代表的人彼此不认识，本题即：证明不认识，本题即：证明G或它的补图或它的补图 中存中存在在3个顶点彼此邻接。个顶点彼此邻接。GG离离散散数数学学第第七七章章 图图论论 4/26/202269图 8.4.1 bca离离散散数数学学第第七七章章 图图论论 4/26

46、/202270 解解 因为因为K6是是5-正则图，所以正则图，所以vV（G）（）（v（ ），），d（v）在）在G中或在中或在 中大于等于中大于等于3。不妨设在。不妨设在G中中d（v）3，则，则v在在G中至少关联三个顶点设为中至少关联三个顶点设为a、b、c（见图（见图8.4.1），若此三顶点在），若此三顶点在G中彼此不邻接，则必中彼此不邻接，则必有三边（有三边（a，b）、（）、（a，c）、（）、（b，c）均在）均在 中（图中虚线），亦即中（图中虚线），亦即a、b、c三点在三点在 中中彼此邻接，否则三顶点至少有两个在彼此邻接，否则三顶点至少有两个在G中邻接，中邻接，不妨设（不妨设（a，b）E（G）

47、，则），则v、a、b为在为在G中彼此邻接的三顶点，故在中彼此邻接的三顶点，故在G或或 中存在中存在3个个顶点彼此邻接。顶点彼此邻接。GGGGG离离散散数数学学第第七七章章 图图论论 4/26/202271 【例【例8.4.3】 证明无向图证明无向图G与其补图与其补图 至少有一个是连通图。至少有一个是连通图。 分析分析 是是G的补图，即的补图，即G是一个无向完是一个无向完全图。对全图。对G中任一边中任一边e，若，若eE（G），则），则eE（ ）；反之若）；反之若eE（ ），则），则eE（G）。又）。又G与与 有相同的顶点集，故只需考有相同的顶点集，故只需考虑虑G中的任意二顶点。若中的任意二顶点。

48、若G是连通图，则命题是连通图，则命题已成立，所以不妨设已成立，所以不妨设G不是连通图。不是连通图。GGGG离离散散数数学学第第七七章章 图图论论 4/26/202272 解解 假设假设G不是连通图，则不是连通图，则G至少有两个至少有两个连通分支，不妨设为连通分支，不妨设为G1、G2。对于。对于G中的任意中的任意二顶点二顶点u、v，设，设uG1，此时若，此时若vG2，则必，则必有边（有边（u，v） ，所以，所以u、v在在 中连通。中连通。此时若此时若vG2，即，即vG1,则必存在顶点则必存在顶点wG2，使得（使得（u，w） 且（且（v，w） ，所，所以以u、v仍在仍在 中连通。故中连通。故 是连

49、通图。所是连通图。所以，以，G与其补图与其补图 至少有一个是连通图。至少有一个是连通图。GGGGGGG离离散散数数学学第第七七章章 图图论论 4/26/202273习 题 八 3设图设图G有有n个顶点，个顶点，n+1条边，证明条边，证明G中至少有一个顶点的度数大于等于中至少有一个顶点的度数大于等于3。 4在简单图中若顶点数大于等于在简单图中若顶点数大于等于2，则至，则至少有两个顶点的度数相同。少有两个顶点的度数相同。 离离散散数数学学第第七七章章 图图论论 4/26/202274 6G是是n阶无向简单图，阶无向简单图，n2为奇数，为奇数，则则G与与G所含的奇度数顶点数相等。所含的奇度数顶点数相

50、等。 7证明图证明图8.1中，图（中，图（a）与（）与（b）同构，）同构，图（图（c）与（）与（d）不同构。）不同构。 8画出画出4阶无向完全图阶无向完全图K4的所有非同构的所有非同构的子图，并指出哪些是生成子图和生成子图的的子图，并指出哪些是生成子图和生成子图的互补情况。互补情况。 9画出画出3阶有向完全图的所有非同构的阶有向完全图的所有非同构的生成子图，指出每个图的补图和生成子图的互生成子图，指出每个图的补图和生成子图的互补情况。补情况。离离散散数数学学第第七七章章 图图论论 4/26/202275 图 8.1 (c)(d)(b)(a)离离散散数数学学第第七七章章 图图论论 4/26/20

51、2276 10如果一个图如果一个图G同构于自己的补图同构于自己的补图G，则称该图为自补图。则称该图为自补图。 （1）有几个非同构的）有几个非同构的4阶和阶和5阶的自补图？阶的自补图？ （2）是否有）是否有3阶和阶和6阶的自补图？阶的自补图？ 11G是是n（n3）阶连通图，）阶连通图，G没有桥，没有桥，当且仅当对当且仅当对G的每一对顶点和每一条边，有一的每一对顶点和每一条边，有一条连接这两个顶点而不含这条边的通路。条连接这两个顶点而不含这条边的通路。 12一个连通无向图一个连通无向图G中的顶点中的顶点(是割点是割点的充分必要条件是存在两个顶点的充分必要条件是存在两个顶点u和和w，使得，使得顶点顶

52、点u和和w之间的每一条路都通过之间的每一条路都通过v。 离离散散数数学学第第七七章章 图图论论 4/26/202277n 13试求图8.2中有向图的所有强分图、单分图和弱分图。n 离离散散数数学学第第七七章章 图图论论 4/26/202278图 8.2 1245673离离散散数数学学第第七七章章 图图论论 4/26/202279 15证明：图的每一个顶点和每一条边证明：图的每一个顶点和每一条边都只包含在一个弱分图中。都只包含在一个弱分图中。 16有向图有向图G如图如图8.3所示，计算所示，计算G的邻的邻接矩阵的前接矩阵的前4次幂，回答下列问题。次幂，回答下列问题。 （1）G中中v1到到v4的长

53、度为的长度为4的通路有几条？的通路有几条？ （2）G中中v1到到v1的长度为的长度为4的回路有几条？的回路有几条？离离散散数数学学第第七七章章 图图论论 4/26/202280 （3）G中长度为中长度为4的通路总数是多少？其的通路总数是多少？其中有多少条是回路？中有多少条是回路？ （4）G中长度小于等于中长度小于等于4的通路有几条？的通路有几条？其中有多少条是回路？其中有多少条是回路？ （5）写出）写出G的可达矩阵。的可达矩阵。 离离散散数数学学第第七七章章 图图论论 4/26/202281图 8.3 1243离离散散数数学学第第七七章章 图图论论 4/26/202282Konigsberg(

54、Konigsberg(哥尼斯堡哥尼斯堡) )七桥问题七桥问题ACBD问题：能否从河岸或小岛出发，通过每一座桥，问题：能否从河岸或小岛出发，通过每一座桥，而且仅仅通过一次回到原地。而且仅仅通过一次回到原地。离离散散数数学学第第十十五五章章 欧欧拉拉图图与与哈哈密密顿顿图图 四、欧拉图与哈密顿图四、欧拉图与哈密顿图欧拉图 离离散散数数学学第第七七章章 图图论论 4/26/202283 Euler(欧拉欧拉)1736年对这个问题，给出了否年对这个问题，给出了否定的回答。将河岸和小岛作为图的结点，七座定的回答。将河岸和小岛作为图的结点，七座桥为边，构成一个无向重图，问题化为图论中桥为边，构成一个无向重

55、图，问题化为图论中迹的问题。迹的问题。定义定义4.14.1 通过图中通过图中所有边所有边一次且仅一次的路称为一次且仅一次的路称为欧拉路欧拉路。 通过图中通过图中所有边所有边一次且仅一次的回路称为一次且仅一次的回路称为欧拉回欧拉回路路。 具有欧拉回路的图称为具有欧拉回路的图称为欧拉图欧拉图，具有，具有欧拉路欧拉路而无而无欧拉回路的图称为欧拉回路的图称为半欧拉图半欧拉图。离离散散数数学学第第十十五五章章 欧欧拉拉图图与与哈哈密密顿顿图图 离离散散数数学学第第七七章章 图图论论 4/26/202284离离散散数数学学第第十十五五章章 欧欧拉拉图图与与哈哈密密顿顿图图 e2v1v2v3v4e4e3e5

56、e1aedcb离离散散数数学学第第七七章章 图图论论 4/26/202285定理定理4.14.1 无向图无向图G G是欧拉图当且仅当是欧拉图当且仅当G G是连通的，且是连通的，且G G中没有奇度结点。中没有奇度结点。定理定理4.24.2 无向图无向图G G是半欧拉图当且仅当是半欧拉图当且仅当G G是连通的，是连通的，且且G G中恰有两个奇度结点。中恰有两个奇度结点。离离散散数数学学第第十十五五章章 欧欧拉拉图图与与哈哈密密顿顿图图 哥尼斯堡七桥问题，由于四个结点哥尼斯堡七桥问题，由于四个结点都是奇度结点，不可能有欧拉回路。都是奇度结点，不可能有欧拉回路。e2v1v2v3v4e4e3e5e1ae

57、dcb离离散散数数学学第第七七章章 图图论论 4/26/202286如下图中（a）是欧拉图，图（b）是半欧拉图，图（c）既非欧拉图也非半欧拉图。e10e1e9e3e4e2e5e6e7e8(a)(b)(c)105432离离散散数数学学第第七七章章 图图论论 4/26/202287离离散散数数学学第第十十五五章章 欧欧拉拉图图与与哈哈密密顿顿图图 e3e5e2e1dcbae4 定义定义4.14.1 通过图中通过图中所有边所有边一次且仅一次的单向一次且仅一次的单向路称为路称为单向单向欧拉路欧拉路。 通过图中通过图中所有边所有边一次且仅一次的回路称为一次且仅一次的回路称为欧拉回欧拉回路路。 具有欧拉回

58、路的图称为具有欧拉回路的图称为欧拉图欧拉图，具有，具有单向欧拉路单向欧拉路而无欧拉回路的图称为而无欧拉回路的图称为半欧拉图半欧拉图。离离散散数数学学第第七七章章 图图论论 4/26/202288离离散散数数学学第第十十五五章章 欧欧拉拉图图与与哈哈密密顿顿图图 定理定理4.34.3 有向图有向图D D是欧拉图当且仅当是欧拉图当且仅当D D是强连是强连通的且每个结点的入度都等于出度。通的且每个结点的入度都等于出度。定理定理4.44.4 有向图有向图D D是半欧拉图当且仅当是半欧拉图当且仅当D D是单是单向连通的，且向连通的，且D D中恰有两个奇度结点，其中一中恰有两个奇度结点，其中一个的入度比出

59、度大个的入度比出度大1 1，另一个的出度比入度大，另一个的出度比入度大1 1，其余结点的入度都等于出度。，其余结点的入度都等于出度。e3e5e2e1dcbae4 离离散散数数学学第第七七章章 图图论论 4/26/202289 当给定了一个欧拉图后，如何找出它的一条欧当给定了一个欧拉图后，如何找出它的一条欧拉回路？下面的拉回路？下面的Fleury（于（于1921年提出）算法解年提出）算法解决了这个问题，这个算法的实质是决了这个问题，这个算法的实质是“避桥避桥”。 设设G是欧拉图。是欧拉图。 （1）任选）任选G的一个结点的一个结点v0为起点，并设零条为起点，并设零条边的路为边的路为l0=v0。 （

60、2）设已选好的迹为）设已选好的迹为li=v0e1v1e2v2eivi，则按下述方法从则按下述方法从E-e1，e2，ei中选取边中选取边ei+1： ei+1与与vi关联；关联； 除非没有别的边可选择，否则除非没有别的边可选择，否则ei+1不不是是Gi=G-e1，e2，ei的割边（桥）。的割边（桥）。 （3）当第）当第(2)步不能继续进行时（所有的边已步不能继续进行时（所有的边已走遍），算法终止。走遍），算法终止。离离散散数数学学第第七七章章 图图论论 4/26/202290 例例 找出下图的一条欧拉回路。找出下图的一条欧拉回路。 解解 从从v0出发，先找到出发，先找到l3=v0e1v1e2v4e3v5，因为此时在因为此时在G