第七章图论.ppt

《第七章图论.ppt》由会员分享，可在线阅读，更多相关《第七章图论.ppt（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章图论第七章图论第七章图论第七章图论 n 图的基本概念图的基本概念n路与回路路与回路n图的矩阵表示图的矩阵表示n欧拉图与哈密尔顿图欧拉图与哈密尔顿图1、图的定义及表示、图的定义及表示 图由结点和连接两个结点之间的连线组成图由结点和连接两个结点之间的连线组成。连线的长度和。连线的长度和结点的位置是无关紧要的。结点的位置是无关紧要的。几乎每一门可以想象的学科里都有问题可以用图模型来解几乎每一门可以想象的学科里都有问题可以用图模型来解决。例如：可以用图来表示生态环境里不同物种的竞争；可以决。例如：可以用图来表示生态环境里不同物种的竞争；可以用图来表示在组织里谁影响谁，以及用图来表示比赛结果；旅用

2、图来表示在组织里谁影响谁，以及用图来表示比赛结果；旅行商问题；地球着色问题等。行商问题；地球着色问题等。一个简单的例子：大城市之间的高速公路系统建模：一个简单的例子：大城市之间的高速公路系统建模：可以把各个城市看成结点，城市之间存在高速公路，则认可以把各个城市看成结点，城市之间存在高速公路，则认为这两个城市之间有连线，这样可以构成一个简单的图为这两个城市之间有连线，这样可以构成一个简单的图7-1图的基本概念图的基本概念2、图图的表示法的表示法 三三元元组组表表示示G=：V(G)-非非空空的的结结点点集集合合；E(G)-边边集集合合；G-边边集集合合E到到结结点点无无序序偶偶（有有序序偶偶）集集

3、合合上上的的函函数。数。7-1图的基本概念图的基本概念图可图可简记为简记为G=V(G)=a,b,c,dE(G)=e1,e2,e3,e4,e5,e6G(e1)=(a,b),G(e2)=(a,c),G(e3)=(b,d),G(e4)=(b,c),G(e5)=(d,c),G(e6)=(a,d).左右为同一图形左右为同一图形3、图图的一些基本概念的一些基本概念（1）无向无向边边：与与结结点无序偶关点无序偶关联联的的边边，用，用(a,b)表示表示 有向有向边边：与与结结点有序偶关点有序偶关联联的的边边，用，用表示；表明是从表示；表明是从a到到b的有向的有向边边 孤立孤立结结点：点：无无邻邻接点的接点的结

4、结点点7-1图的基本概念图的基本概念无向边：无向边：(a,b),(b,c),(b,d),(c,d),(i,l),(k,l)有向边：有向边：,（2）无向图：无向图：图中每一边都为无向边图中每一边都为无向边 有向图：有向图：图中每一边都为有向边图中每一边都为有向边 混合图：混合图：图中既有有向边，也有无向边图中既有有向边，也有无向边 平凡图：平凡图：仅由一个孤立结点构成的图仅由一个孤立结点构成的图7-1图的基本概念图的基本概念（3）邻接点：邻接点：由一条有向边或一条无向边相关联的两结点由一条有向边或一条无向边相关联的两结点 邻接边：邻接边：关联于同一结点的两条边关联于同一结点的两条边 平行边：平行

5、边：连接于同一对结点的多条边连接于同一对结点的多条边 自回路（环）：自回路（环）：关联于同一结点的一条边（既可看作是有关联于同一结点的一条边（既可看作是有向边，也可作无向边）向边，也可作无向边）7-1图的基本概念图的基本概念（4）结结点的度数点的度数 图图G=V，E中，与中，与结结点点v关关联联的的边边数数为为度数，度数，记为记为deg(v)。一个一个环环的度数的度数为为2。7-1图的基本概念图的基本概念deg(a)=2deg(b)=3deg(c)=2deg(d)=2deg(e)=5（4）结结点的度数点的度数 在有向在有向图图中，定中，定义义入度、出度的概念入度、出度的概念 入度：入度：射入一

6、个射入一个结结点的点的边边的条数，的条数，记为记为deg-(v)；出度：出度：由一个由一个结结点射出的点射出的边边的条数，的条数，记为记为deg+(v)；入度与出度之和入度与出度之和为该结为该结点的度数：点的度数：deg(v)=deg+(v)+deg-(v)7-1图的基本概念图的基本概念deg+(e)=2,deg-(e)=1,deg(e)=3deg+(f)=1,deg-(f)=2,deg(f)=3deg+(g)=deg-(g)=1,deg(g)=2deg+(h)=deg-(h)=1,deg(h)=2（4）结结点的度数点的度数 最大度：最大度：最小度：最小度：7-1图的基本概念图的基本概念(G)

7、=5(G)=27-1图的基本概念图的基本概念定理定理:结点度数总和等于边数的两倍结点度数总和等于边数的两倍，即，即:证明：每条边关联两个结点证明：每条边关联两个结点 一条边给相关的每个结点的度数为一条边给相关的每个结点的度数为1 因此，在图中，结点度数总和等于边数的两倍。因此，在图中，结点度数总和等于边数的两倍。7-1图的基本概念图的基本概念定理定理:度数为奇数的结点必定是偶数个度数为奇数的结点必定是偶数个证证明：明：设设V1、V2分分别为别为G中奇数度数点集和偶数度数点集，中奇数度数点集和偶数度数点集，则则：定理：定理：有向有向图图中中所有所有结结点的入度之和等于所有点的入度之和等于所有结结

8、点的出度之和点的出度之和（5）多重多重图图：含有平行含有平行边边的的图图 简单图简单图：不含有平行不含有平行边边和和环环的的图图 完全完全图图：每一每一对结对结点之点之间间都有都有边边关关联联的的简单图简单图 有向完全有向完全图图：完全完全图图中每条中每条边边任意确定一个方向所得的任意确定一个方向所得的图图7-1图的基本概念图的基本概念定理：定理：n个个结结点的无向（有向）完全点的无向（有向）完全图图Kn的的边边数数为为n(n-1)/2证证明：明：在完全在完全图图中，每个中，每个结结点的度数点的度数应为应为n1，则则n个个结结点的点的度数之和度数之和为为n(n-1)，因此，因此|E|n(n-1

9、)/2（6）子子图图：7-1图的基本概念图的基本概念生成子生成子图图：包含包含G中所有中所有结结点的子点的子图图（7）补图补图：G是是G的子图，若的子图，若G=，使得，使得EE-E，且且V 中仅包含中仅包含E 的边所关联的结点（的边所关联的结点（V中无孤立结点），则中无孤立结点），则称称G是是G相对于相对于G的补图的补图7-1图的基本概念图的基本概念图图(c)是图是图(b)相对于图相对于图(a)的补图的补图问：问：若若G是是G相对于相对于G的补图，是否一定有的补图，是否一定有G是是G相对于相对于G的的补图？即补图？即G和和G互为补图？互为补图？不是，补图中不包含孤立结点不是，补图中不包含孤立结

10、点(c)(b)(a)（7）补图补图：图图G中由中由G中所有结点和所有能使中所有结点和所有能使G成为完全图的添加边组成为完全图的添加边组成的图是成的图是G相对于完全图的补图相对于完全图的补图，简称为，简称为G的补图的补图，记为，记为7-1图的基本概念图的基本概念(b)(a)和和G一定互为补图一定互为补图图的结点位置和连线长度可任意选择，表示不唯一图的结点位置和连线长度可任意选择，表示不唯一（8）图图的同构：的同构：G，G=，存在一一，存在一一对应对应的映射的映射G：vivi，且，且e(vi,vj)（或（或）是）是G的一条的一条边边当当且且仅仅当当e=(g(vi),g(vj)（或（或）也是）也是G

11、的一条的一条边边，称，称G与与G同构，同构，记为记为GG(a)(b)(a)和和(b)同构同构7-1图的基本概念图的基本概念(c)和和(d)同构同构(c)(d)由同构的定义，易见两图同构必定满足以下条件：（由同构的定义，易见两图同构必定满足以下条件：（必要条件必要条件）a、结点数目相等、结点数目相等b、边数相等、边数相等 c、度数相同的结点数目相同、度数相同的结点数目相同G与与G同构的充要条件同构的充要条件是：是：a、结点一一对应、结点一一对应b、边一一对应、边一一对应c、保持关联关系、保持关联关系以上三个条件并以上三个条件并不是两图同构的不是两图同构的充分条件，如：充分条件，如：(a)(b)7

12、-1图的基本概念图的基本概念第七章图论第七章图论 n 图的基本概念图的基本概念n路与回路路与回路n图的矩阵表示图的矩阵表示n欧拉图与哈密尔顿图欧拉图与哈密尔顿图7-2路与回路路与回路回路：回路：起点和终点相等的路起点和终点相等的路 迹：迹：所有的边都不相同的路所有的边都不相同的路通路：通路：所有的结点都不相同的路所有的结点都不相同的路圈：圈：除除v0=vn外其余结点都不相同的路外其余结点都不相同的路上图中有：路上图中有：路 v1e2v3e3v2e3v3e4v2e6v5e7v3；迹迹 v5e8v4e5v2e6v5e7v3e4v2；通路通路 v4e8v5e6v2e1v1e2v3；圈圈 v2e1v1

13、e2v3e7v5e6v21、路的基本概念：、路的基本概念：路：路：图图G=，设设 v0,v1,vn V,V,e1,e2,en E,E,其中其中ei是关是关联联于于结结点点vi-1,vi的的边边，交替序列，交替序列设设 v0 e1 v1 e2 en vn称为称为联结联结v0到到vn的路；的路；v0，vn分别称为路的起点和终点分别称为路的起点和终点7-2路与回路路与回路定理定理：G=具有具有n个个结结点，如果从点，如果从结结点点vj到到结结点点vk存在一存在一 条路条路，则则此两此两结结点点间间必存在一条必存在一条边边不多于不多于n-1的路的路推推论论：G=具有具有n个个结结点，如果从点，如果从结

14、结点点vj到到结结点点vk存在一存在一 条路条路，则则此两此两结结点点间间必存在一条必存在一条边边不多于不多于n-1的通路的通路证证明：明：设结设结点点vj到到vk的路上的的路上的结结点序列点序列为为 vj vivk，结结点序列中点序列中结结点的个数点的个数为为L+1，则这则这条路中有条路中有L条条边边。若。若Ln-1，则结则结点序点序列中必出列中必出现现重复重复结结点，因而可去除重复点，因而可去除重复结结点之点之间间的的边边，得到的，得到的仍是仍是联结联结vi到到vk的路。依此的路。依此类类推，必可得到推，必可得到边边不多于不多于n-1的路的路7-2路与回路路与回路2、无向图的连通性：、无向

15、图的连通性：在无向图在无向图G中，若结点中，若结点u和和v之间存在一条路，则称之间存在一条路，则称u和和v是是连通的连通的。结点之间的连通性是结点集上的等价关系结点之间的连通性是结点集上的等价关系。证明：自反性：证明：自反性：v和和v是连通的是连通的 对称性：若对称性：若u和和v连通，则连通，则v和和u必定也是连通的必定也是连通的 传递性：传递性：u和和v连通，连通，v和和w连通，则连通，则u和和w中也存在路，中也存在路，是连通的是连通的7-2路与回路路与回路2、无向图的连通性：、无向图的连通性：连通性对应的等价关系给出若干等价类，把结点集连通性对应的等价关系给出若干等价类，把结点集V划分为划

16、分为V1,V2,Vm，使得两个结点，使得两个结点vi和和vj是连通的，当且仅当他们同属是连通的，当且仅当他们同属于同一个于同一个Vi。称子图。称子图G(V1),G(V2),G(Vm)为图为图G的的连通分支连通分支。无向图无向图G的一个连通分支为的一个连通分支为G的的一个极大连通子图一个极大连通子图。连通分支数：连通分支数：W(G)连通图：连通图：只有一个连通分支的图。其中的只有一个连通分支的图。其中的任两个结点都连通任两个结点都连通连通图连通图三个连通分支的非连通图三个连通分支的非连通图7-2路与回路路与回路在在图图中中删删除除结结点点v，即把，即把结结点点v和所有与其相关和所有与其相关联联的

17、的边边都都删删掉；掉；在在图图中中删删除除边边，仅仅需把需把该边删该边删去。去。对对一个一个图删结图删结点或点或边边，会影响其，会影响其连连通性通性考虑：至少要删除多少条边或结点，连通图会变为非连通图呢？考虑：至少要删除多少条边或结点，连通图会变为非连通图呢？引入点割集和边割集的概念引入点割集和边割集的概念7-2路与回路路与回路3、割集：、割集：（1）点割集点割集：G=为为无向无向连连通通图图，V1V，图图G删删除了除了V1所有的所有的结结点后，所得的子点后，所得的子图图是非是非连连通通图图，但，但删删除除V1的任何真的任何真子集后，得到的子子集后，得到的子图图仍是仍是连连通通图图，称，称V1

18、是是G的一个点割集的一个点割集割点割点：若点割集中只有一个结点，此结点称为割点若点割集中只有一个结点，此结点称为割点点割集或者割点是否唯一？点割集或者割点是否唯一？e和和d都为图的割点都为图的割点（不唯一）（不唯一）7-2路与回路路与回路不同点割集中的结点数目未必相同不同点割集中的结点数目未必相同如右图中，有点割集如右图中，有点割集e和和f和和c,d点连通度点连通度：产生一个非连通图需要删去的点的最少数目，产生一个非连通图需要删去的点的最少数目，记记为为 k(G)=min|V1|V1是是G的点割集的点割集非连通图的点连通度为非连通图的点连通度为0存在割点的连通图存在割点的连通图的点连通度为的点

19、连通度为1完全图完全图Kp的点连通度为的点连通度为p-17-2路与回路路与回路（2）边边割集割集：G=为为无向无向连连通通图图，E1E，图图G删删除除了了E1所有的所有的边边后，所得的子后，所得的子图图是非是非连连通通图图，但，但删删除除E的任何真的任何真子集，得到的子子集，得到的子图图仍是仍是连连通通图图，称，称E是是G的一个的一个边边割集割集割边（桥）割边（桥）：若边割集中只有一条边，此边称为割边若边割集中只有一条边，此边称为割边边连通度边连通度：产生一个不连通图需要删去的最少边数，记为：产生一个不连通图需要删去的最少边数，记为不连通图不连通图的边连通度为的边连通度为0存在割边的连通图存在

20、割边的连通图的边连通度为的边连通度为1完全图完全图Kp的边连通度为的边连通度为p-1定理：定理：对于任何一个图对于任何一个图G，有，有7-2路与回路路与回路7-2路与回路路与回路定理（割点存在定理）：定理（割点存在定理）：连连通无向通无向图图G中的中的结结点点v是割点的充要是割点的充要条件条件是存在两个是存在两个结结点点u和和w，使得，使得结结点点u和和w的每一条路都通的每一条路都通过过v。7-2路与回路路与回路4、有向图的连通性、有向图的连通性：和无向图连通性区别很大和无向图连通性区别很大可达性可达性：在有向图中，从结点在有向图中，从结点u到到v有一条路，称为有一条路，称为u可达可达v。可达

21、性是否为等价关系？可达性是否为等价关系？自反性，满足自反性，满足传递性，满足传递性，满足对称性，不满足（图中对称性，不满足（图中e可达可达g，g不可达不可达e)不是等价关系不是等价关系7-2路与回路路与回路距离距离：u可达可达v，u和和v间间的的最短路的最短路的长长度度，记为记为d 若若u到到v不可达，不可达，通常通常记记d=图图的直径的直径：D=max dd0d=0d+ddu，v彼此可达，彼此可达，d不一定等于不一定等于d（如右图中（如右图中d=1,d=2）距离的概念距离的概念对对无向无向图图同同样样适用适用在无向在无向图图中，中，d=d，记为记为d(u,v)7-2路与回路路与回路（1）强连

22、通强连通：任意两个结点互相可达：任意两个结点互相可达 单侧连通单侧连通：任意两个结点之间，至少有一个结点到另一：任意两个结点之间，至少有一个结点到另一个结点是可达的个结点是可达的 弱连通弱连通：略去边的方向，得到的无向图是连通的：略去边的方向，得到的无向图是连通的弱连通弱连通单侧连通单侧连通 强连通强连通 7-2路与回路路与回路定理定理：一个有向：一个有向图图是是强强连连通的，当且通的，当且仅仅当当G中一个回路，它中一个回路，它至少包含每个至少包含每个结结点一次。点一次。证证明：明：“”：如果：如果G中有一个回路，至少包含每个中有一个回路，至少包含每个结结点一次，点一次，则则G中任意两个中任意

23、两个结结点都是可达的，所以点都是可达的，所以G是是强强连连通通图图。“”：若不存在回路若不存在回路经过经过G中的所有中的所有结结点，点，则则必有一必有一回路不包含某个回路不包含某个结结点点v，且，且v与回路上的各个与回路上的各个结结点不是相互可点不是相互可达，矛盾！达，矛盾！得得证证7-2路与回路路与回路（2）强分图强分图：具有强连通性质的极大子图：具有强连通性质的极大子图 单侧分图单侧分图：具有单侧连通性质的极大子图：具有单侧连通性质的极大子图 弱分图弱分图：具有弱连通性质的极大子图：具有弱连通性质的极大子图定理：定理：有向图中的每个结点位于且只位于一个强分图中有向图中的每个结点位于且只位于

24、一个强分图中第七章图论第七章图论 n 图的基本概念图的基本概念n路与回路路与回路n图的矩阵表示图的矩阵表示n欧拉图与哈密尔顿图欧拉图与哈密尔顿图7-3图图的矩的矩阵阵表示表示设设G=是一个是一个简单图简单图，V=v1,v2,vn 是是G的的n个个结结点，点，则则n阶阶方方阵阵A(G)=(aij)称称为为G的的邻邻接矩接矩阵阵。其中：。其中：对对于于给给定集合定集合A上的关系上的关系R，可以用有向，可以用有向图图（关系（关系图图）和矩）和矩阵阵表示表示对对于一般形式的于一般形式的图图，也能，也能给给出其矩出其矩阵阵表示表示1、邻接矩阵、邻接矩阵简单无向图的邻接矩阵对称；简单有向图的邻接矩阵不一定

25、对称简单无向图的邻接矩阵对称；简单有向图的邻接矩阵不一定对称零矩零矩阵对应阵对应零零图图7-3图图的矩的矩阵阵表示表示G1G2G3在在邻邻接矩接矩阵阵A中，中，第第i行中行中值为值为1的元素个数等于的元素个数等于vi的出度的出度 第第j列中列中值为值为1的元素个数等于的元素个数等于vj的入度的入度7-3图图的矩的矩阵阵表示表示2、置、置换换等价：等价：把把n阶阶方方阵阵A的列和行分的列和行分别别作置作置换换，得到新的方，得到新的方阵阵A，称，称A与与A置置换换等价等价。置。置换换等价等价是是n阶阶布布尔尔矩矩阵阵集合集合上的等价关系上的等价关系 对对于有向于有向图图，按照，按照结结点的不同次序

26、写出的点的不同次序写出的邻邻接矩接矩阵阵是置是置换换等价的。因此，可等价的。因此，可选选取任意一个取任意一个邻邻接矩接矩阵阵作作为为该图该图的矩的矩阵阵表示，通表示，通过过此此邻邻接矩接矩阵阵来考来考虑图虑图的一些特的一些特性性7-3图图的矩的矩阵阵表示表示3、可达性矩、可达性矩阵阵：G=是是简单简单有向有向图图，|V|=n，定，定义义n*n矩矩阵阵P=(pij)为为可可达性矩达性矩阵阵考虑：考虑：如何计算图中长度为如何计算图中长度为k的路的数目的路的数目？7-3图图的矩的矩阵阵表示表示7-3图图的矩的矩阵阵表示表示定理：定理：A(G)是是图图G的的邻邻接矩接矩阵阵，则则(A(G)l中的中的i

27、行，行，j列元素列元素aij(l)等于等于G中中联结联结vi与与vj的的长长度度为为l的路的数目的路的数目在在实际问题实际问题中，常需要考中，常需要考虑虑到到节节点之点之间间是否存在路的是否存在路的问题问题。可以通可以通过计过计算算A,A2,An,当当发现发现某个某个Al的的第第i行，第行，第j列不列不为为0，就表明就表明vi到到vj可达可达。7-3图图的矩的矩阵阵表示表示 由前面的定理的推由前面的定理的推论论可知，如果在可知，如果在vi到到vj之之间间存在路，必存在路，必定存在通路，所以定存在通路，所以l只需只需计计算到算到n就可以了，因此有以下推就可以了，因此有以下推论论：推论：推论：G有

28、有n个结点，个结点，A是邻接矩阵，是邻接矩阵，bij为为Bn的的i行，行，j列元素，若列元素，若bij0，则表明，则表明vi，vj中存在路中存在路要确定两结点可达是否需要无穷计算要确定两结点可达是否需要无穷计算Al呢？呢？将将Bn中不为零的元素值改为中不为零的元素值改为1，就可得到可达性矩阵，就可得到可达性矩阵P7-3图图的矩的矩阵阵表示表示例例1：设图设图G的邻接矩阵为的邻接矩阵为 ，求，求G的可达性矩阵的可达性矩阵解：解：在在计算可达性矩阵计算可达性矩阵时，由于不需要考虑两个结点间路的数目，时，由于不需要考虑两个结点间路的数目，我们我们可只计算布尔矩阵可只计算布尔矩阵其中其中A(i)表示布

29、尔运算下表示布尔运算下A的的i次方次方7-3图图的矩的矩阵阵表示表示例例2、图图G如图所示，求可达性矩阵如图所示，求可达性矩阵P解：解：7-3图图的矩的矩阵阵表示表示对于无向图对于无向图，其邻接矩阵是一个对称矩阵，其可达性矩阵也对称，其邻接矩阵是一个对称矩阵，其可达性矩阵也对称7-3图图的矩的矩阵阵表示表示图的邻接矩阵和可达性矩阵表示图的邻接矩阵和可达性矩阵表示结点与结点结点与结点之间的关联之间的关联结点和边之间结点和边之间也有一定关联，通过完全关联矩阵表示也有一定关联，通过完全关联矩阵表示在给出点和边的关联关系时，我们在给出点和边的关联关系时，我们假定图中无自回路假定图中无自回路（1）G为无

30、向图为无向图 设设 为为G的结点集，的结点集，为为G的边集，的边集，称矩阵称矩阵M(G)=(mij)为为 完全关联矩阵完全关联矩阵，其中：，其中：4、完全关联矩阵：、完全关联矩阵：7-3图图的矩的矩阵阵表示表示例：例：从关联矩阵研究图形的性质从关联矩阵研究图形的性质：1）M(G)中每列中有且仅有两个中每列中有且仅有两个1，对应每边关联的两个结点，对应每边关联的两个结点2）每行中元素的和为对应结点的度数）每行中元素的和为对应结点的度数3）元素全为）元素全为0的行对应结点为孤立结点的行对应结点为孤立结点4）平行边对应的列相同）平行边对应的列相同5）结点）结点/边编序不同，对应完全关联矩阵只有行序边

31、编序不同，对应完全关联矩阵只有行序/列序的差别列序的差别7-3图图的矩的矩阵阵表示表示（2）G为为有向有向图图 G=，p*q阶阶矩矩阵阵M(G)=(mij)为为G的完全关的完全关联联矩矩阵阵，其中：，其中：例：例：7-3图图的矩的矩阵阵表示表示有向图完全关联矩阵的一些性质有向图完全关联矩阵的一些性质：1）每一列中一个值为）每一列中一个值为1，一个为，一个为-1，对应图中的一条有向边，对应图中的一条有向边2）把一行中的值为）把一行中的值为1的元素相加，得到顶点的出度，把值为的元素相加，得到顶点的出度，把值为-1的元素相加，得到顶点的入度的元素相加，得到顶点的入度3）一行中元素全为）一行中元素全为

32、0，对应孤立结点，对应孤立结点4）平行边对应的列相同）平行边对应的列相同5）结点）结点/边编序不同，对应完全关联矩阵只有行序边编序不同，对应完全关联矩阵只有行序/列序的列序的差别差别7-3图图的矩的矩阵阵表示表示5、完全关、完全关联联矩矩阵阵中的行相加运算：中的行相加运算：有向有向图图：对应对应分量普通加法运算分量普通加法运算 无向无向图图：对应对应分量模分量模2加法运算加法运算 行相加运算相当于行相加运算相当于G中中对应对应结结点的合并点的合并说说明明vi和和vj中只有一个中只有一个结结点是点是边边er的端点，合并的端点，合并后仍是后仍是er的端点的端点有两种情况：有两种情况：1）vivj都

33、不是都不是er的端点；的端点；2）vivj都是都是er的端点，合并后的端点，合并后删删去自回路，去自回路，对应边对应边消失消失7-3图图的矩的矩阵阵表示表示例例1：左图合并：左图合并v4，v5后得到右图，对应关联矩阵为：后得到右图，对应关联矩阵为：e1 e2 e3 e4 e5 e6 e70 0 0 0 0 1 10 0 0 1 1 1 00 1 1 1 0 0 01 1 0 0 0 0 01 0 1 0 1 0 1v1v2v3v4v5e1 e2 e3 e4 e5 e6 e70 0 0 0 0 1 10 0 0 1 1 1 00 1 1 1 0 0 00 1 1 0 1 0 1v1v2v3v4,

34、5M(G)M(G)7-3图图的矩的矩阵阵表示表示例例2：左图合并：左图合并v2，v3且删去自回路后得到右图，关联矩阵为：且删去自回路后得到右图，关联矩阵为：e1 e2 e3 e4 e5 e6 e7 e8 e91 1 0 0 0 0 0 0 0-1 0 1 0 0 0 1 0 00 0 -1 1 0 0 0 -1 10 -1 0 0 0 1 -1 1 00 0 0 0 1 -1 0 0 10 0 0 -1 -1 0 0 0 0v1v2v3v4v5v6e1 e2 e3 e4 e5 e6 e7 e8 e9v1v2,3v4v5v6M(G)M(G)e1 e2 e3 e4 e5 e6 e7 e8 e91

35、1 0 0 0 0 0 0 0-1 0 1 0 0 0 1 0 00 0 -1 1 0 0 0 -1 10 -1 0 0 0 1 -1 1 00 0 0 0 1 -1 0 0 -10 0 0 -1 -1 0 0 0 0v1v2v3v4v5v61 1 0 0 0 0 0 0 0-1 0 0 1 0 0 1 -1 10 -1 0 0 0 1 -1 1 00 0 0 0 1 -1 0 0 -10 0 0 -1 -1 0 0 0 07-3图图的矩的矩阵阵表示表示定理：定理：G为连通图为连通图，有，有r个结点，则其完全关联矩阵个结点，则其完全关联矩阵M(G)的的秩为秩为r-1，即，即rank M(G)=

36、r-1推论：推论：G有有r个结点，个结点，w个极大连通子图个极大连通子图，则图，则图G的完全关联的完全关联矩阵的矩阵的秩为秩为r-w第七章图论第七章图论 n 图的基本概念图的基本概念n路与回路路与回路n图的矩阵表示图的矩阵表示n欧拉图与哈密尔顿图欧拉图与哈密尔顿图 欧拉提出著名的欧拉提出著名的哥尼斯堡七桥问题哥尼斯堡七桥问题：环城：环城“遍游遍游”，即，即从某地出发，每座桥都仅走一遍，最后回到起点。从某地出发，每座桥都仅走一遍，最后回到起点。欧拉给出一个简单的准则说明哥尼斯堡七桥问题是不能欧拉给出一个简单的准则说明哥尼斯堡七桥问题是不能解的。解的。下面给出欧拉路，欧拉回路，欧拉图，半欧拉图的概

37、念。下面给出欧拉路，欧拉回路，欧拉图，半欧拉图的概念。7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图1、欧拉图欧拉图（1）定义：给定无孤立结点图定义：给定无孤立结点图G，欧拉路欧拉路：通过图中每边一次且仅一次的路通过图中每边一次且仅一次的路欧拉回路欧拉回路：通过图中每边一次且仅一次的回路通过图中每边一次且仅一次的回路半欧拉图半欧拉图：存在欧拉路的图：存在欧拉路的图欧拉图欧拉图：具有欧拉回路的图具有欧拉回路的图 对于半欧拉图或者欧拉图，由于其经过每条边，必定会对于半欧拉图或者欧拉图，由于其经过每条边，必定会经过所有的点，因此必定是一个连通图，此外，关于图中的经过所有的点，因此必定是一个连通图，此外，

38、关于图中的结点的度数，也有相关定理及推论结点的度数，也有相关定理及推论7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图定理：定理：无向图无向图G具有一条欧拉路具有一条欧拉路，当且仅当，当且仅当G是连通是连通的，且有的，且有零个或两个奇数度结点零个或两个奇数度结点（2）（半）欧拉图的判定方法）（半）欧拉图的判定方法7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图推论：无向图推论：无向图G具有一条欧拉回路具有一条欧拉回路，当且仅当，当且仅当G是连通是连通的，且的，且所有结点的度数全为偶数所有结点的度数全为偶数半欧拉图半欧拉图

39、欧拉图欧拉图7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图可见可见deg(A)=5，deg(B)=deg(C)=deg(D)=3，故在图中不存，故在图中不存在欧拉回路，哥尼斯堡七桥问题有了确切的否定答案在欧拉回路，哥尼斯堡七桥问题有了确切的否定答案奇数奇数7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图思考：无向完全图思考：无向完全图Kp当当p取何值时为欧拉图？取何值时为欧拉图？（3）一笔画问题：）一笔画问题：1）从图）从图G中某个结点出发，经过中某个结点出发，经过G中的每一边一次且仅一次中的每一边一次且仅一次到达另一个结点（半欧拉图）到达另一个结点（半欧拉图）2）从图）从图G中某个结点出发，经过中某个

40、结点出发，经过G中的每一边一次且仅一次中的每一边一次且仅一次回到该结点（欧拉图）回到该结点（欧拉图）7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图半欧拉图半欧拉图 欧拉图欧拉图单向欧拉路单向欧拉路：通过有向图通过有向图G中每边一次且仅一次的单向路中每边一次且仅一次的单向路单向欧拉回路单向欧拉回路：通过有向图通过有向图G中每边一次且仅一次的单向回路中每边一次且仅一次的单向回路（4）G为有向图：为有向图：定理：定理：有向图有向图G具有一条单向欧拉回路具有一条单向欧拉回路，当且仅当，当且仅当G是连通的是连通的，且且每个结点的入度等于出度每个结点的入度等于出度 有向图有向图G具有单向欧拉路具有单向欧拉路，

41、当且仅当，当且仅当G是连通是连通的，且的，且除除两个结点外两个结点外（一个结点的入度比出度大（一个结点的入度比出度大1，另一个结点的入度比，另一个结点的入度比出度小出度小1），每个结点的入度等于出度），每个结点的入度等于出度7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图欧拉回路是边的遍历问题，而汉密尔顿回路则是点的遍历问欧拉回路是边的遍历问题，而汉密尔顿回路则是点的遍历问题题，即能否找到一条经过每个点一次且仅一次最终回到起点，即能否找到一条经过每个点一次且仅一次最终回到起点的回路。经典问题：十二面体问题的回路。经典问题：十二面体问题2、汉密尔顿图、汉密尔顿图（1）定义：给定图）定义：给定图G，汉密

42、尔顿路汉密尔顿路：经过图中每个结点恰好一次的路经过图中每个结点恰好一次的路汉密尔顿回路汉密尔顿回路：经过图中每个结点恰好一次的回路经过图中每个结点恰好一次的回路半汉密尔顿图半汉密尔顿图：具有汉密尔顿路的图：具有汉密尔顿路的图汉密尔顿图汉密尔顿图：具有汉密尔顿回路的图具有汉密尔顿回路的图7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图（2）必要条件的判定必要条件的判定：定理：定理：图图G=具有汉密尔顿回路，则对于具有汉密尔顿回路，则对于V的任何非空的任何非空子集子集S，W(G-S)|S|成立，其中成立，其中W(G-S)是是G-S的的连连通分支数。通分支数。由此

43、定理的结论，我们可以证明某些图是非汉密尔顿图由此定理的结论，我们可以证明某些图是非汉密尔顿图考虑：用上面定理能证明某个特定的图不是汉密尔顿图，考虑：用上面定理能证明某个特定的图不是汉密尔顿图，那是否对于任意的非汉密尔顿图，都能用上面方法证明呢？那是否对于任意的非汉密尔顿图，都能用上面方法证明呢？7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图考虑考虑彼得森图（彼得森图（不是汉密尔顿图）不是汉密尔顿图）：删去一个或两个结点，不能使图变为不连通图；删去三个结删去一个或两个结点，不能使图变为不连通图；删去三个结点，最多得到两个连通分支的子图；删去四个结点，最多得到三点，最多得到两个连通分支的子图；删去四个

44、结点，最多得到三个连通分支的子图；删去五个或者五个以上的结点，剩余的结点个连通分支的子图；删去五个或者五个以上的结点，剩余的结点个数不会超过五个，故子图的连通分支数也不会超过五个数不会超过五个，故子图的连通分支数也不会超过五因而无法根据上述定理判定彼因而无法根据上述定理判定彼得森图不是汉密尔顿图得森图不是汉密尔顿图7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图另一个能判定非半汉密尔顿图的方法：另一个能判定非半汉密尔顿图的方法：如果一个图中存在汉密尔顿路，我们用如果一个图中存在汉密尔顿路，我们用A标记图中的任意标记图中的任意一个结点，所有与其相邻的结点标记为一个结点，所有与其相邻的结点标记为B，再标

45、记所有邻接于，再标记所有邻接于B的结点为的结点为A，邻接于，邻接于A的结点为的结点为B，直到所有的结点都有标记结，直到所有的结点都有标记结束。如果出现相邻结点的标记相同时，在对应边上增加一个结束。如果出现相邻结点的标记相同时，在对应边上增加一个结点，加上相异标记。点，加上相异标记。如果图中存在汉密尔顿路，则必定交替通过结点如果图中存在汉密尔顿路，则必定交替通过结点A和和B，所，所以以A和和B的个数必定相同。的个数必定相同。如果如果A和和B的个数不同，表明此图中肯定不会存在汉密尔顿的个数不同，表明此图中肯定不会存在汉密尔顿路，不是半汉密尔顿图，更不是汉密尔顿图。路，不是半汉密尔顿图，更不是汉密尔

46、顿图。7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图ABBBAAAAAABBBBBB 以此法标记彼得森图，得以此法标记彼得森图，得7个个A9个个B，可知不是汉密尔顿图。，可知不是汉密尔顿图。7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图不是汉密尔顿图不是汉密尔顿图7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图考虑：是否标上标记后，如果考虑：是否标上标记后，如果A和和B的个数相等，图中就一定有的个数相等，图中就一定有汉密尔顿回路？汉密尔顿回路？不是不是例如下图例如下图3A3B，但仍不存在汉密尔顿路。，但仍不存在汉密尔顿路。7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图（3）充分条件的判定充分条件的判定：1）定理

47、：）定理：简单图简单图G具有具有n个结点，个结点，G中中每一对结点度数之和大每一对结点度数之和大于等于于等于n-1，则，则G中存在汉密尔顿路中存在汉密尔顿路。2）定理：）定理：简单图简单图G具有具有n个结点，如果个结点，如果G中中每一对结点度数每一对结点度数之和大于等于之和大于等于n，则，则G中存在一条汉密尔顿回路中存在一条汉密尔顿回路。只是充分条件而非必要只是充分条件而非必要例如右图，例如右图，n=6，任何两个结点之和为，任何两个结点之和为4616，但，但G中存在汉密尔顿（回）路。中存在汉密尔顿（回）路。7-4欧拉欧拉图图与与汉汉密密尔尔顿图顿图定理：定理：G为汉密尔顿图，当且仅当其闭包是汉

48、密尔顿图为汉密尔顿图，当且仅当其闭包是汉密尔顿图。（4）G的闭包的闭包G=有有n个结点，将个结点，将G中度数之和大于等于中度数之和大于等于n的非邻接点连的非邻接点连接起来得到图接起来得到图G，对，对G重复以上步骤，直到不再存在这样的重复以上步骤，直到不再存在这样的结点对而得到的图，即为结点对而得到的图，即为G的闭包的闭包，记为，记为C(G)(a)(b)(c)(d)例：例：第七章第七章 图论小结图论小结n 图、有图、有/无向边、有无向边、有/无向图、邻接点无向图、邻接点/边、孤立结点、零边、孤立结点、零图、平凡图、自回路、结点度数、出图、平凡图、自回路、结点度数、出/入度、多重图、完全入度、多重图、完全图、补图、子图、生成子图、子图的补图、图的同构图、补图、子图、生成子图、子图的补图、图的同构n 路、迹、通路、圈、结点连通、连通分支、连通图、点路、迹、通路、圈、结点连通、连通分支、连通图、点/边割集、割点边割集、割点/边、点连通度、边连通度、可达性、图的直边、点连通度、边连通度、可达性、图的直径、单侧径、单侧/强强/弱连通、单侧弱连通、单侧/强强/弱分图弱分图n邻接矩阵、可达性矩阵、完全关联矩阵邻接矩阵、可达性矩阵、完全关联矩阵n 欧拉（回）路、（半）欧拉图、汉密尔顿（回欧拉（回）路、（半）欧拉图、汉密尔顿（回)路、（半）路、（半）汉密尔顿图、图的闭包汉密尔顿图、图的闭包结束结束