《南邮离散数学第7章图论.ppt》由会员分享，可在线阅读，更多相关《南邮离散数学第7章图论.ppt（83页珍藏版）》请在三一办公上搜索。
1、第七章 图论,图论中有许多现代应用的古老题目。瑞士数学家欧拉在18世纪引进了图论的基本思想。利用图解决了哥尼斯堡七桥问题。图可以用来解决许多领域的问题。例如：用图来确定能否在平面电路板上实现电路。用图来区分分子式相同但结构不同的两种化学物。用边上带权值的图来解决诸如寻找交通网络里两个城市间最短通路的问题。用图来安排考试等等。随着科技的发展，图论在解决运筹学、网络理论、信息论、控制论、博弈论等问题时，发挥了巨大的作用。,第七章图论,图的基本概念路与回路图的矩阵表示欧拉图与哈密尔顿图,1、图的定义及表示 图由结点和连接两个结点之间的连线组成。连线的长度和结点的位置是无关紧要的。几乎每一门可以想象的
2、学科里都有问题可以用图模型来解决。例如：可以用图来表示生态环境里不同物种的竞争；可以用图来表示在组织里谁影响谁，以及用图来表示比赛结果；旅行商问题；地球着色问题等。一个简单的例子：大城市之间的高速公路系统建模：可以把各个城市看成结点，城市之间存在高速公路，则认为这两个城市之间有连线，这样可以构成一个简单的图,7-1图的基本概念,2、图的表示法 三元组表示G=：V(G)-非空的结点集合；E(G)-边集合；G-边集合E到结点无序偶（有序偶）集合上的函数。,7-1图的基本概念,图可简记为G=,V(G)=a,b,c,dE(G)=e1,e2,e3,e4,e5,e6G(e1)=(a,b),G(e2)=(a
3、,c),G(e3)=(b,d),G(e4)=(b,c),G(e5)=(d,c),G(e6)=(a,d).,左右为同一图形,3、图的一些基本概念（1）无向边：与结点无序偶关联的边，用(a,b)表示 有向边：与结点有序偶关联的边，用表示；表明是从a到b的有向边 孤立结点：无邻接点的结点,7-1图的基本概念,无向边：(a,b),(b,c),(b,d),(c,d),(i,l),(k,l)有向边：,（2）无向图：图中每一边都为无向边 有向图：图中每一边都为有向边 混合图：图中既有有向边，也有无向边 平凡图：仅由一个孤立结点构成的图,7-1图的基本概念,（3）邻接点：由一条有向边或一条无向边相关联的两结点
4、 邻接边：关联于同一结点的两条边 平行边：连接于同一对结点的多条边 自回路（环）：关联于同一结点的一条边（既可看作是有向边，也可作无向边）,7-1图的基本概念,（4）结点的度数 图G=V，E中，与结点v关联的边数为度数，记为deg(v)。一个环的度数为2。,7-1图的基本概念,deg(a)=2deg(b)=3deg(c)=2deg(d)=2deg(e)=5,（4）结点的度数 在有向图中，定义入度、出度的概念 入度：射入一个结点的边的条数，记为deg-(v)；出度：由一个结点射出的边的条数，记为deg+(v)；入度与出度之和为该结点的度数：deg(v)=deg+(v)+deg-(v),7-1图的
5、基本概念,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)=5(G)=2,7-1图的基本概念,定理:结点度数总和等于边数的两倍，即:,证明：每条边关联两个结点 一条边给相关的每个结点的度数为1 因此，在图中，结点度数总和等于边数的两倍。,7-1图的基本概念,定理:度数为奇数的结点必定是偶数个,证明：设V1、V2分别为G中奇数度数点集和偶数度数点集，则：,7-1图的基
6、本概念,定理：有向图中所有结点的入度之和等于所有结点的出度之和,证明：一条边对应一个入度和一个出度 一个结点若具有一个出度或入度，则必关联边 所以入度之和等于边数，出度之和也等于边数,（5）多重图：含有平行边的图 简单图：不含有平行边和环的图 完全图：每一对结点之间都有边关联的简单图 有向完全图：完全图中每条边任意确定一个方向所得的图,7-1图的基本概念,定理：n个结点的无向（有向）完全图Kn的边数为n(n-1)/2,证明：在完全图中，每个结点的度数应为n1，则n个结点的度数之和为n(n-1)，因此|E|n(n-1)/2,（6）子图：,7-1图的基本概念,生成子图：包含G中所有结点的子图,（7
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互为补图？,不是，补图中不包含孤立结点,(c),(b),(a),（7）补图：图G中由G中所有结点和所有能使G成为完全图的添加边组成的图是G相对于完全图的补图，简称为G的补图，记为,7-1图的基本概念,(b),(a),和G一定互为补图,图的结点位置和连线长度可任意选择，表示不唯一,（8）图的同构：G，G=，存在一一对应的映射G：vivi，且e(vi,
8、vj)（或）是G的一条边当且仅当e=(g(vi),g(vj)（或）也是G的一条边，称G与G同构，记为GG,(a)(b),(a)和(b)同构,7-1图的基本概念,(c)和(d)同构,(c)(d),由同构的定义，易见两图同构必定满足以下条件：（必要条件）,a、结点数目相等,b、边数相等,c、度数相同的结点数目相同,G与G同构的充要条件是：a、结点一一对应b、边一一对应c、保持关联关系,以上三个条件并不是两图同构的充分条件，如：,(a),(b),7-1图的基本概念,第七章图论,图的基本概念路与回路图的矩阵表示欧拉图与哈密尔顿图,7-2路与回路,1、路的基本概念：路：图G=，设，其中ei是关联于结点v
9、i-1,vi的边，交替序列 称为联结v0到vn的路；v0，vn分别称为路的起点和终点,回路：起点和终点相等的路,迹：所有的边都不相同的路,通路：所有的结点都不相同的路,圈：除v0=vn外其余结点都不相同的路,上图中有：路 v1e2v3e3v2e3v3e4v2e6v5e7v3；迹 v5e8v4e5v2e6v5e7v3e4v2；通路 v4e8v5e6v2e1v1e2v3；圈 v2e1v1e2v3e7v5e6v2,7-2路与回路,定理：G=具有n个结点，如果从结点vj到结点vk存在一 条路，则此两结点间必存在一条边不多于n-1的路,推论：G=具有n个结点，如果从结点vj到结点vk存在一 条路，则此两
10、结点间必存在一条边不多于n-1的通路,证明：设结点vj到vk的路上的结点序列为 vj vivk，结点序列中结点的个数为L+1，则这条路中有L条边。若Ln-1，则结点序列中必出现重复结点，因而可去除重复结点之间的边，得到的仍是联结vi到vk的路。依此类推，必可得到边不多于n-1的路,7-2路与回路,2、无向图的连通性：在无向图G中，若结点u和v之间存在一条路，则称u和v是连通的。结点之间的连通性是结点集上的等价关系。证明：自反性：v和v是连通的 对称性：若u和v连通，则v和u必定也是连通的 传递性：u和v连通，v和w连通，则u和w中也存在路，是连通的,7-2路与回路,2、无向图的连通性：连通性对
11、应的等价关系给出若干等价类，把结点集V划分为V1,V2,Vm，使得两个结点vi和vj是连通的，当且仅当他们同属于同一个Vi。称子图G(V1),G(V2),G(Vm)为图G的连通分支。无向图G的一个连通分支为G的一个极大连通子图。连通分支数：W(G)连通图：只有一个连通分支的图。其中的任两个结点都连通,连通图,三个连通分支的非连通图,7-2路与回路,在图中删除结点v，即把结点v和所有与其相关联的边都删掉；在图中删除边，仅需把该边删去。对一个图删结点或边，会影响其连通性,考虑：至少要删除多少条边或结点，连通图会变为非连通图呢？,引入点割集和边割集的概念,7-2路与回路,3、割集：（1）点割集：G=
12、为无向连通图，V1V，图G删除了V1所有的结点后，所得的子图是非连通图，但删除V1的任何真子集后，得到的子图仍是连通图，称V1是G的一个点割集,割点：若点割集中只有一个结点，此结点称为割点,点割集或者割点是否唯一？,e和d都为图的割点（不唯一）,7-2路与回路,不同点割集中的结点数目未必相同如右图中，有点割集e和f和c,d,点连通度：产生一个非连通图需要删去的点的最少数目，记为,非连通图的点连通度为0存在割点的连通图的点连通度为1完全图Kp的点连通度为p-1,7-2路与回路,（2）边割集：G=为无向连通图，E1E，图G删除了E1所有的边后，所得的子图是非连通图，但删除E的任何真子集，得到的子图
13、仍是连通图，称E是G的一个边割集,割边（桥）：若边割集中只有一条边，此边称为割边,边连通度：产生一个不连通图需要删去的最少边数，记为,不连通图的边连通度为0存在割边的连通图的边连通度为1完全图Kp的边连通度为p-1,定理：对于任何一个图G，有,7-2路与回路,7-2路与回路,7-2路与回路,定理（割点存在定理）：连通无向图G中的结点v是割点的充要条件是存在两个结点u和w，使得结点u和w的每一条路都通过v。,7-2路与回路,4、有向图的连通性：和无向图连通性区别很大可达性：在有向图中，从结点u到v有一条路，称为u可达v。可达性是否为等价关系？,自反性，满足传递性，满足对称性，不满足（图中e可达g
14、，g不可达e),不是等价关系,7-2路与回路,距离：u可达v，u和v间的最短路的长度，记为d 若u到v不可达，通常记d=图的直径：D=max d,d0d=0d+ddu，v彼此可达，d不一定等于d（如右图中d=1,d=2）,距离的概念对无向图同样适用在无向图中，d=d，记为d(u,v),7-2路与回路,（1）强连通：任意两个结点互相可达 单侧连通：任意两个结点之间，至少有一个结点到另一个结点是可达的 弱连通：略去边的方向，得到的无向图是连通的,弱连通,单侧连通,强连通,7-2路与回路,定理：一个有向图是强连通的，当且仅当G中一个回路，它至少包含每个结点一次。,证明：“”：如果G中有一个回路，至少
15、包含每个结点一次，则G中任意两个结点都是可达的，所以G是强连通图。“”：若不存在回路经过G中的所有结点，则必有一回路不包含某个结点v，且v与回路上的各个结点不是相互可达，矛盾！得证,7-2路与回路,（2）强分图：具有强连通性质的极大子图 单侧分图：具有单侧连通性质的极大子图 弱分图：具有弱连通性质的极大子图,定理：有向图中的每个结点位于且只位于一个强分图中,证明：1）对于任意结点v，G中所有与v相互可达的结点的集合S即为G的一个强分图，即有每个结点都位于一个强分图中；2）假设v位于两个不同的强分图S1，S2中，则v与S1，S2中的每个结点都相互可达，可知S1，S2中的所有结点通过v都相互可达。
16、与强分图的定义矛盾，所以假设不成立。得证,第七章图论,图的基本概念路与回路图的矩阵表示欧拉图与哈密尔顿图,7-3图的矩阵表示,设G=是一个简单图，V=v1,v2,vn 是G的n个结点，则n阶方阵A(G)=(aij)称为G的邻接矩阵。其中：,对于给定结合A上的关系R，可以用有向图（关系图）和矩阵表示对于一般形式的图，也能给出其矩阵表示,1、邻接矩阵,简单无向图的邻接矩阵对称；简单有向图的邻接矩阵不一定对称,7-3图的矩阵表示,G1,G2,G3,7-3图的矩阵表示,2、置换等价：把n阶方阵A的列和行分别作置换，得到新的方阵A，称A与A置换等价。置换等价是n阶布尔矩阵集合上的等价关系 对于有向图，按
17、照结点的不同次序写出的邻接矩阵是置换等价的。因此，可选取任意一个邻接矩阵作为该图的矩阵表示，通过此邻接矩阵来考虑图的一些特性,在邻接矩阵A中，第i行中值为1的元素个数等于vi的出度 第j列中值为1的元素个数等于vj的入度,零矩阵对应零图,7-3图的矩阵表示,考虑：如何计算图中长度为k的路的数目？,7-3图的矩阵表示,定理：A(G)是图G的邻接矩阵，则(A(G)l中的i行，j列元素aij(l)等于G中联结vi与vj的长度为l的路的数目,在实际问题中，常需要考虑到节点之间是否存在路的问题。可以通过计算A,A2,An,当发现某个Al的第i行，第j列不为0，就表明vi到vj可达。,7-3图的矩阵表示,
18、由前面的定理的推论可知，如果在vi到vj之间存在路，必定存在通路，所以l只需计算到n就可以了，因此有以下推论：,推论：G有n个结点，A是邻接矩阵，bij为Bn的i行，j列元素，若bij0，则表明vi，vj中存在路,对于简单有向图的任意两个结点之间的可达性，也可以用矩阵表示出来，即可达性矩阵,要确定两结点可达是否需要无穷计算Al呢？,7-3图的矩阵表示,将Bn中不为零的元素值改为1，就可得到可达性矩阵P,3、可达性矩阵：G=是简单有向图，|V|=n，定义n*n矩阵P=(pij)为可达性矩阵,7-3图的矩阵表示,例1：设图G的邻接矩阵为，求G的可达性矩阵,解：,在计算可达性矩阵时，由于不需要考虑两
19、个结点间路的数目，我们可只计算布尔矩阵其中A(i)表示布尔运算下A的i次方,7-3图的矩阵表示,例2、图G如图所示，求可达性矩阵P,解：,7-3图的矩阵表示,对于无向图，其邻接矩阵是一个对称矩阵，其可达性矩阵也对称,7-3图的矩阵表示,图的邻接矩阵和可达性矩阵表示结点与结点之间的关联结点和边之间也有一定关联，通过完全关联矩阵表示在给出点和边的关联关系时，我们假定图中无自回路,（1）G为无向图 设 为G的结点集，为G的边集，称矩阵M(G)=(mij)为 完全关联矩阵，其中：,4、完全关联矩阵：,7-3图的矩阵表示,例：,从关联矩阵研究图形的性质：1）M(G)中每列中有且仅有两个1，对应每边关联的
20、两个结点2）每行中元素的和为对应结点的度数3）元素全为0的行对应结点为孤立结点4）平行边对应的列相同5）结点/边编序不同，对应完全关联矩阵只有行序/列序的差别,7-3图的矩阵表示,（2）G为有向图 G=，p*q阶矩阵M(G)=(mij)为G的完全关联矩阵，其中：,例：,7-3图的矩阵表示,有向图完全关联矩阵的一些性质：1）每一列中一个值为1，一个为-1，对应图中的一条有向边2）把一行中的值为1的元素相加，得到顶点的出度，把值为-1的元素相加，得到顶点的入度3）一行中元素全为0，对应孤立结点4）平行边对应的列相同5）结点/边编序不同，对应完全关联矩阵只有行序/列序的差别,7-3图的矩阵表示,5、
21、完全关联矩阵中的行相加运算：有向图：对应分量普通加法运算 无向图：对应分量模2加法运算 行相加运算相当于G中对应结点的合并,说明vi和vj中只有一个结点是边er的端点，合并后仍是er的端点,有两种情况：,1）vivj都不是er的端点；2）vivj都是er的端点，合并后删去自回路，对应边消失,7-3图的矩阵表示,例1：左图合并v4，v5后得到右图，对应关联矩阵为：,e1 e2 e3 e4 e5 e6 e7,0 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 1,v1v2v3v4v5,e1 e2 e3 e4 e5 e6 e
22、7,0 0 0 0 0 1 10 0 0 1 1 1 00 1 1 1 0 0 00 1 1 0 1 0 1,v1v2v3v4,5,M(G),M(G),7-3图的矩阵表示,例2：左图合并v2，v3且删去自回路后得到右图，关联矩阵为：,e1 e2 e3 e4 e5 e6 e7 e8 e9,1 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 0,v1v2v3v4v5v6,e1 e2 e3 e4 e5 e6 e7 e8 e9,v1v2,3v4v5v6
23、,M(G),M(G),e1 e2 e3 e4 e5 e6 e7 e8 e9,1 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 0,v1v2v3v4v5v6,1 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 0,7-3图的矩阵表示,例：计算右图对应的完全关联矩阵的秩。,e1 e2 e3 e4 e5 e6 e7,0 0 0 0
24、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 1,v1v2v3v4v5,7-3图的矩阵表示,7-3图的矩阵表示,7-3图的矩阵表示,定理：G为连通图，有r个结点，则其完全关联矩阵M(G)的秩为r-1，即rank M(G)=r-1,7-3图的矩阵表示,推论：G有r个结点，w个极大连通子图，则图G的完全关联矩阵的秩为r-w,（可以应用行相加运算求秩）,第七章图论,图的基本概念路与回路图的矩阵表示欧拉图与哈密尔顿图,欧拉提出著名的哥尼斯堡七桥问题：环城“遍游”，即从某地出发，每座桥都仅走一遍，最后回到起点。欧拉给出一个简单的准则说明哥
25、尼斯堡七桥问题是不能解的。下面给出欧拉路，欧拉回路，欧拉图，半欧拉图的概念。,7-4欧拉图与汉密尔顿图,1、欧拉图（1）定义：给定无孤立结点图G，欧拉路：通过图中每边一次且仅一次的路欧拉回路：通过图中每边一次且仅一次的回路半欧拉图：存在欧拉路的图欧拉图：具有欧拉回路的图 对于半欧拉图或者欧拉图，由于其经过每条边，必定会经过所有的点，因此必定是一个连通图，此外，关于图中的结点的度数，也有相关定理及推论,7-4欧拉图与汉密尔顿图,定理：无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度结点,（2）（半）欧拉图的判定方法,7-4欧拉图与汉密尔顿图,7-4欧拉图与汉密尔顿图,7-4欧拉图
26、与汉密尔顿图,推论：无向图G具有一条欧拉回路，当且仅当G是连通的，且所有结点的度数全为偶数,半欧拉图 欧拉图,7-4欧拉图与汉密尔顿图,可见deg(A)=5，deg(B)=deg(C)=deg(D)=3，故在图中不存在欧拉回路，哥尼斯堡七桥问题有了确切的否定答案,奇数,7-4欧拉图与汉密尔顿图,思考：无向完全图Kp当p取何值时为欧拉图？,（3）一笔画问题：1）从图G中某个结点出发，经过G中的每一边一次且仅一次到达另一个结点（半欧拉图）2）从图G中某个结点出发，经过G中的每一边一次且仅一次回到该结点（欧拉图）,7-4欧拉图与汉密尔顿图,半欧拉图 欧拉图,单向欧拉路：通过有向图G中每边一次且仅一次
27、的单向路单向欧拉回路：通过有向图G中每边一次且仅一次的单向回路,（4）G为有向图：,定理：有向图G具有一条单向欧拉回路，当且仅当G是连通的，且每个结点的入度等于出度 有向图G具有单向欧拉路，当且仅当G是连通的，且除两个结点外（一个结点的入度比出度大1，另一个结点的入度比出度小1），每个结点的入度等于出度,7-4欧拉图与汉密尔顿图,欧拉回路是边的遍历问题，而汉密尔顿回路则是点的遍历问题，即能否找到一条经过每个点一次且仅一次最终回到起点的回路。经典问题：十二面体问题,2、汉密尔顿图（1）定义：给定图G，汉密尔顿路：经过图中每个结点恰好一次的路汉密尔顿回路：经过图中每个结点恰好一次的回路半汉密尔顿图
28、：具有汉密尔顿路的图汉密尔顿图：具有汉密尔顿回路的图,7-4欧拉图与汉密尔顿图,7-4欧拉图与汉密尔顿图,（2）必要条件的判定：定理：图G=具有汉密尔顿回路，则对于V的任何非空子集S，W(G-S)|S|成立，其中W(G-S)是G-S的连通分支数。,证明：设C是G的一条汉密尔顿回路，则对于V的任意非空子集S，在C中删去S的任意一个结点a1，则C-a1是连通的非回路。若再删去S中的另一结点a2，则W(C-a1-a2)2，归纳可得：W(C-S)|S|而C-S是G-S的一个生成子图，有 W(G-S)W(C-S)|S|,7-4欧拉图与汉密尔顿图,由此定理的结论，我们可以证明某些图是非汉密尔顿图下图中，选
29、取S=v1,v4，则G-S中有三个分图，因此G不是汉密尔顿图,考虑：用上面定理能证明某个特定的图不是汉密尔顿图，那是否对于任意的非汉密尔顿图，都能用上面方法证明呢？如果不行，该如何处理？,7-4欧拉图与汉密尔顿图,考虑彼得森图（不是汉密尔顿图）：删去一个或两个结点，不能使图变为不连通图；删去三个结点，最多得到两个连通分支的子图；删去四个结点，最多得到三个连通分支的子图；删去五个或者五个以上的结点，剩余的结点个数不会超过五个，故子图的连通分支数也不会超过五,因而无法根据上述定理判定彼得森图不是汉密尔顿图,7-4欧拉图与汉密尔顿图,另一个能判定非半汉密尔顿图的方法：如果一个图中存在汉密尔顿路，我们
30、用A标记图中的任意一个结点，所有与其相邻的结点标记为B，再标记所有邻接于B的结点为A，邻接于A的结点为B，直到所有的结点都有标记结束。如果出现相邻结点的标记相同时，在对应边上增加一个结点，加上相异标记。如果图中存在汉密尔顿路，则必定交替通过结点A和B，所以A和B的个数必定相同。如果A和B的个数不同，表明此图中肯定不会存在汉密尔顿路，不是半汉密尔顿图，更不是汉密尔顿图。,7-4欧拉图与汉密尔顿图,A,B,B,B,A,A,A,A,A,A,B,B,B,B,B,B,以此法标记彼得森图，得7个A9个B，可知不是汉密尔顿图。,7-4欧拉图与汉密尔顿图,不是汉密尔顿图,7-4欧拉图与汉密尔顿图,考虑：是否标
31、上标记后，如果A和B的个数相等，图中就一定有汉密尔顿回路？,不是,例如下图3A3B，但仍不存在汉密尔顿路。,7-4欧拉图与汉密尔顿图,（3）充分条件的判定：1）定理：简单图G具有n个结点，G中每一对结点度数之和大于等于n-1，则G中存在汉密尔顿路。,证明：I.G是连通图：若G有两个或多个不连通的分图，设一个分图中有n1个结点，另一个分图中有n2个结点，分别在两个分图中选取两个结点v1和v2，可知d(v1)n1-1，d(v2)n2-1，d(v1)+d(v2)n1+n2-2 n-1，与已知条件矛盾，所以G是连通图。,7-4欧拉图与汉密尔顿图,II.构造汉密尔顿路：设在G中有p-1条边的通路，pn，
32、其结点序列为v1,v2,vp。i)v1或vp邻接于不在这条路上的一个结点：加入这个结点，扩展路，得到p条边的通路；ii)v1和vp只邻接于这条路上的结点，则需证明存在回路包含这p个结点：a)v1邻接于vp，显然成立,7-4欧拉图与汉密尔顿图,b)假设v1的邻接点集是vl,vm,vt，2 l,m,t p-1。若vp邻接于vl-1,vm-1,vt-1中的任意一个vj-1，则v1v2vj-1 vp vp-1 vj v1即为所求回路。若vp不邻接于vl-1,vm-1,vt-1中的任意一个，则vp至多邻接于p-k-1个结点，deg(vp)p-k-1，deg(v1)=k，有deg(v1)deg(vp)p-
33、1n-1，与已知条件矛盾。由于G是连通图，所以必定存在不属于该回路的结点与回路中某个结点邻接，加入这个顶点，可以得到一个边为p的通路 iii)重复上面方法，可得到有n-1条边的通路,7-4欧拉图与汉密尔顿图,只是充分条件而非必要例如右图，n=6，任何两个结点之和为4616，但G中存在汉密尔顿（回）路。,2）定理：简单图G具有n个结点，如果G中每一对结点度数之和大于等于n，则G中存在一条汉密尔顿回路。,同样的，这只是汉密尔顿回路存在的充分而非必要条件，从上例中类似可以推出。,7-4欧拉图与汉密尔顿图,定理：G为汉密尔顿图，当且仅当其闭包是汉密尔顿图。,（4）G的闭包G=有n个结点，将G中度数之和大于等于n的非邻接点连接起来得到图G，对G重复以上步骤，直到不再存在这样的结点对而得到的图，即为G的闭包，记为C(G),例：,第七章 图论小结,图、有/无向边、有/无向图、邻接点/边、孤立结点、零图、平凡图、自回路、结点度数、出/入度、多重图、完全图、补图、子图、生成子图、子图的补图、图的同构 路、迹、通路、圈、结点连通、连通分支、连通图、点/边割集、割点/边、连通度、边连通度、可达性、图的直径、单侧/强/弱连通、单侧/强/弱分图邻接矩阵、可达性矩阵、完全关联矩阵 欧拉（回）路、（半）欧拉图、汉密尔顿（回)路、（半）汉密尔顿图、图的闭包,
