下载文档原格式
习题三1． 因为n 个结点的树的边有n-1条，故其总度数为 2 (n-1)，故度为1的结点个数为2 (n-1)－2n 2－3n 3－……－kn k .2. 设L 是树T 的一条最长路，L 中的结点依次为 v 1, v 2 , …, v k 。
因为L 中各结点都有边相连，所以它们的度数均大于或等于1。
若deg (v 1)>1, 则除了边(v 1, v 2)外，还存在边(v 1, v’) 。
因为树中不存在回路，故v’∉{ v 1, v 2 , …, v k }，于是，(v’,v 1, v 2 , …, v k )是T 的一条新的路，其长度比L 更长。
这与L 是T 的最长路矛盾。
所以deg (v 1)＝1，类似可证deg (v k )＝1。
4．(a) 直接根据图确定B 5B 5T 可得树的棵数：.1014201241001411013)det(55=--------=TB B (b) 去掉边(v 1, v 5)，则直接根据图确定B 5B 5T 可得不含边(v 1, v 5)的树的棵数：,754201241001411012)det(55=--------=TB B 于是，含边(v 1, v 5)的树的棵数为：101－75＝26。
(c) 去掉边(v 4, v 5)，则直接根据图确定B 5B 5T 可得不含边(v 1, v 5)的树的棵数：.60321241001411013)det(55=--------=TB B5. (a) 因为, ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡----------=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡----------=00011100100010001100010000000100001,1100110010101100010001110010000000111001*11B B(b) 去掉边(v 1, v 5)后，有, ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡---------=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡---------=000001000100100010011000100000010001,110011000101100010011100100000011101*11B B(c) 去掉到v 3的其它全部边(v 4, v 3)、(v 5, v 3)后，有,00010010110001000000100000100001,10110010110001000100100000111001*11⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡--------=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡--------=B B..24211310113110021=-------=)B de t(B T1*1为根的根树的个数为因此以v ..81001131011311002),(1=-------=)B de t(B T1*151的根树的个数为为根且不含边因此以v v v ..921131000111002),(321=-----=)B de t(B T1*1的根树的个数为为根且含边因此以v v v10. (1) 余树为｛e 1, e 2, e 5, e 8｝, 重排B 5的各列得. 1001000010001C I C e e e e e e e e ,C 3.4.4,,01-00 0001 1-010 11-00B , 1-000 1-010 01-01 0011-B ,) B B ( 01-00 0001 1-010 11-00 1-000 1-010 01-010011- e e e e e e e e f12f 7643851 f12121112117643851⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡------==⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡------=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡---⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡-----=-=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=-101001011001111)(1010010110011111001100010110100100010100101001121121152基本回路矩阵为由定理则 ＝TT B B B(2) 由定理3.4.8, 基本割集矩阵为. 10010000100001111-0011-01011-001I C - I S S e e e e e e e e Tf12f11f 7643851⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡===)()(214．(a) 这是一个求最优二叉树的问题。
图论课后习题答案图论是数学中的一个分支，主要研究图的结构和性质。
图论的课后习题通常包括证明题、计算题和应用题。
下面给出一些典型的图论课后习题答案：1. 证明题：证明一个图是连通的当且仅当它的任意两个顶点都存在一条路径相连。
答案：首先定义连通图的概念：一个图是连通的，如果对于任意两个顶点，都存在一条路径将它们连接起来。
接下来，我们证明两个方向：- 如果一个图是连通的，那么对于任意两个顶点\( u \)和\( v \)，根据定义，必然存在一条路径\( P \)将它们连接起来。
- 反之，如果对于任意两个顶点\( u \)和\( v \)，都存在一条路径将它们连接起来，那么我们可以构造一个从任意顶点\( u \)出发，访问图中所有顶点的路径，这表明图是连通的。
2. 计算题：给定一个有\( n \)个顶点的完全图，计算它的边数。
答案：在完全图中，每个顶点都与其他所有顶点相连。
因此，对于一个顶点，它将与\( n-1 \)个其他顶点相连。
但是，每条边被计算了两次（因为它连接了两个顶点），所以边数应该是\( \frac{n(n-1)}{2} \)。
3. 应用题：在一个社交网络中，每个用户可以与其他人建立联系。
如果一个用户与至少一半的用户建立了联系，那么这个社交网络是连通的吗？答案：是的，这个社交网络是连通的。
假设社交网络中有\( n \)个用户，如果一个用户与至少\( \lceil \frac{n}{2} \rceil \)个用户建立了联系，那么我们可以构造一条从任意用户\( u \)到这个中心用户的路径。
由于中心用户与至少一半的用户建立了联系，我们可以继续通过这些联系到达其他用户，从而证明社交网络是连通的。
4. 证明题：证明在任何图中，边数至少是顶点数减一。
答案：考虑一个图的生成树，它是一个最小的连通子图，包含图中的所有顶点，并且没有环。
在生成树中，边数等于顶点数减一。
由于任何图都至少包含一个生成树，因此原图的边数至少与生成树的边数相同，即至少是顶点数减一。
东北大学考试试卷（A卷）2010—2011 学年第 2 学期课程名称：图论与代数结构┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄总分一二三四五六七八九学院班级学号姓名……………○……………密……………○……………封……………○…………线………………得分一．(15分) 填空1.设A={2, 4, 6, 8}，A上的二元运算*定义为：a*b=max{a, b}，则在独异点<A,*>中，单位元是 2 ，零元是8 。
2.设a是12阶群的生成元，则a2是 6 阶元素，a5是12 阶元素。
3.设〈G, *〉是一个群，G中的幂等元是 e 。
若G={a,b,c}，a*x=b，则x=a-1*b ；设a是幺元，则b*c= a 。
4.小于5个元素的格都是有补分配（布尔）格。
5.有n个结点的树，其结点度数之和是2(n-1)。
6.一个无向图有生成树的充分必要条件是该图是连通图__。
7.n阶无向完全图Kn 的边数是n(n-1)/2 ，每个结点的度数是n-1 。
若Kn为欧拉图，则n的取值为奇数。
8.具有6 个顶点，12条边的连通简单平面图中，每个面都是由 3 条边围成。
9.无向树T有8片树叶，2个3度分支结点，其余的分支结点都是4度顶点，则 2 个4度分支结点。
得分二． (26分)判断题4.（6分）判断下列集合和运算能否构成半群、独异点和群。
如果不能，简单说明理由。
（1）a是正整数，G={a n|n∈Z，Z为整数集}, 运算是普通乘法。
是半群、独异点和群。
（2分）（2）Q+是正有理数集，运算为普通加法。
（2分）是半群，不是独异点和群。
满足封闭、结合，但没有幺元。
（3）设Z为整数集，∀ x,y∈Z, 运算x*y=x+y-2。
是半群、群和独异点。
（2分）1.（6分）设V1=<Z,+>, V2=<Z, •>，其中Z为整数集合，+和•分别代表普通加法和乘法。
判断下述集合S能否构成V1和V2的子半群和子独异点。
图论（张先迪-李正良）课后习题答案（第⼀章）习题⼀作者---寒江独钓1.证明：在n 阶连通图中(1) ⾄少有n-1条边；(2) 如果边数⼤于n-1，则⾄少有⼀条闭迹；(3) 如果恰有n-1条边，则⾄少有⼀个奇度点。
证明: (1) 若G 中没有1度顶点，由握⼿定理：()2()21v V G m d v n m n m n ∈=≥?≥?>-∑若G 中有1度顶点u ，对G 的顶点数作数学归纳。
当n=2时，结论显然；设结论对n=k 时成⽴。
当n=k+1时，考虑G-u,它仍然为连通图，所以，边数≥k-1.于是G 的边数≥k.(2) 考虑G 中途径：121:n n W v v v v -→→→→L若W 是路，则长为n-1;但由于G 的边数⼤于n-1,因此，存在v i 与v j ,它们相异，但邻接。
于是：1i i j i v v v v +→→→→L 为G 中⼀闭途径，于是也就存在闭迹。
(3) 若不然，G 中顶点度数⾄少为2，于是由握⼿定理：()2()21v V G m d v n m n m n ∈=≥?≥?>-∑这与G 中恰有n-1条边⽭盾！ 2.(1)2n ?12n 2?12n ?1 (2)2n?2?1(3) 2n?2。
证明:u 1的两个邻接点与v 1的两个邻接点状况不同。
所以，两图不同构。
4.证明下⾯两图同构。
u 1 v 1证明:作映射f : v i ? u i (i=1,2….10)容易证明，对?v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 )由图的同构定义知，图(a)与(b)是同构的。
5.指出4个顶点的⾮同构的所有简单图。
分析：四个顶点的简单图最少边数为0，最多边数为6，所以可按边数进⾏枚举。
(a)v 2 v 3u 4u(b)6.证明:1)充分性:当G 是完全图时，每个顶点的度数都是n ?1,共有n 个顶点，总的度数为n(n ?1)，因此总的边数是n(n?1)2=(n 2). 2)必要性:因为G 是简单图,所以当G 是完全图的时候每个顶点的度数才达到最⼤:n ?1.若G 不是完全图，则⾄少有⼀个顶点的度数⼩于n ?1,这样的话，总的度数就要⼩于n (n ?1)，因此总的边数⼩于(n 2)，⽭盾。
图论习题二答案图论习题二答案图论是数学中的一个分支，研究的是图的性质和图之间的关系。
在图论中，有很多经典的习题可以帮助我们更好地理解和应用图的概念。
本文将探讨一些图论习题二的答案，帮助读者更好地理解和掌握图论的知识。
1. 习题：给定一个无向图G=(V,E)，其中V={1,2,3,4,5,6}，E={(1,2),(1,3),(2,3),(2,4),(3,4),(4,5),(4,6)}，求图G的邻接矩阵和关联矩阵。
答案：邻接矩阵是一个n×n的矩阵，其中n是图的顶点数。
对于无向图G，邻接矩阵的元素a[i][j]表示顶点i和顶点j之间是否存在边。
如果存在边，则a[i][j]=1，否则a[i][j]=0。
对于给定的图G，邻接矩阵为：0 1 1 0 0 01 0 1 1 0 01 1 0 1 0 00 1 1 0 1 10 0 0 1 0 00 0 0 1 0 0关联矩阵是一个n×m的矩阵，其中n是图的顶点数，m是图的边数。
对于无向图G，关联矩阵的元素b[i][j]表示顶点i和边j之间的关系。
如果顶点i是边j 的起点，则b[i][j]=-1；如果顶点i是边j的终点，则b[i][j]=1；否则b[i][j]=0。
对于给定的图G，关联矩阵为：-1 -1 0 0 0 01 0 -1 -1 0 00 1 1 0 0 00 0 0 1 -1 -10 0 0 0 1 00 0 0 0 0 12. 习题：给定一个有向图G=(V,E)，其中V={1,2,3,4,5}，E={(1,2),(1,3),(2,3),(2,4),(3,4),(4,1),(5,4)}，求图G的邻接表和深度优先搜索遍历结果。
答案：邻接表是一种图的表示方法，用于存储图中每个顶点的邻接顶点。
对于有向图G，邻接表中的每个元素表示该顶点的出边。
对于给定的图G，邻接表为：1: 2, 32: 3, 43: 44: 15: 4深度优先搜索（DFS）是一种图的遍历算法，用于遍历图中的所有顶点。
)3( 题属中国邮路问题除第欧拉图与哈密尔顿图<1.>给定一个由16条线段构成的图形（见下图）.证明：不能引一条折线与每一线段恰好相交一次（折线可以是不封闭的和自由相交的，但他的顶点不在给定的线段上）证明：建立一个图G ：顶点i v 代表图形的区域(1,2,3,4,5,6)i X i ，顶点i v 与j v 之间连接的边数等于区域i X 与j X 公共线段的数目.于是，将上图的区域和边可转化成下图：由顶点度数知不存在欧拉路，从1X 到6X 只能相交于外面的两条线段.<2.>下列图形中哪些能一笔画成.解：只需考虑该图是否有欧拉路（即有两个奇点或者无奇点），故第一个和第三个可以一笔画成，第二个不能一笔画成.<4.>下图是某个展览馆的平面图，其中每个相邻的展览室有门相通.证明：不存在一条从A 进入，经过每个展览室恰好一次再从A 处出来的参观路线.证：用顶点代表展览室，两顶点相邻当且仅当这两点所对应的展览室有门相通，则可得一个连通简单图G （见下图）.因此，只要证明G 中不存在H —回路即可.具体理由如下：令}{1216,,,S y y y = ，则显然S 是G 的真子集，而()1816G S S ω-=>=（x 共18个，y 共16个），故由讲义中定理2.3知不存在H —回路.<5.>某次会议有20人参加，其中每个人都至少有10个朋友.这20人围一桌入座，要想使与每个人相邻的两位都是朋友是否可能？解:用顶点代表人，两人是朋友时相应顶点间连一边，得到一个无向图(,)G V E =.只要证明G 中存在H —回路即可. G 是10阶连通图，对于20n =，且()10,()10G G d u d v ≥≥，可得：()()20G G d u d v n +≥=，故由讲义中定理2.4知G 中存在H —回路.<6.>已知,,,,,,a b c d e f g 七个人中，a 会讲英语，b 会讲英语和汉语，c 会讲英语、意大利语和俄语，d 会讲汉语和日语，e 会讲意大利语和德语，f 会讲俄语、日语和法语，g 会讲德语和法语.能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈.解：用七个顶点表示这七个人.若两人能交谈（会讲同一种语言），就在这两顶点之间连一条边，得到图G .只要证明图G 中存在H -回路即可. 具体结果如下：c e g f d b a c 意大利语德语法语日语汉语英语英语 .<7.>设G 是分划为,X Y 的二部图，且X Y ≠，则G 一定不是H —图。
图论试题及答案解析图片一、选择题1. 图论中，图的基本元素是什么？A. 点和线B. 点和面C. 线和面D. 点和边答案：A2. 在无向图中，如果两个顶点之间存在一条边，则称这两个顶点是：A. 相邻的B. 相连的C. 相等的D. 相异的答案：A3. 在有向图中，如果从顶点A到顶点B有一条有向边，则称顶点A是顶点B的：A. 父顶点B. 子顶点C. 邻接顶点D. 非邻接顶点答案：B4. 一个图的度是指：A. 图中顶点的总数B. 图中边的总数C. 一个顶点的边数D. 图的连通性答案：C5. 一个图是连通的，当且仅当：A. 图中任意两个顶点都是相邻的B. 图中任意两个顶点都可以通过边相连C. 图中任意两个顶点都可以通过路径相连D. 图中任意两个顶点都可以通过子顶点相连答案：C二、填空题1. 在图论中，一个顶点的度数是该顶点的________。
答案：边数2. 如果一个图的任意两个顶点都可以通过边相连，则称该图为________。
答案：完全图3. 一个图中，如果存在一个顶点到其他所有顶点都有边相连，则称该顶点为________。
答案：中心顶点4. 图论中，最短路径问题是指在图中找到两个顶点之间的________。
答案：最短路径5. 如果一个图的任意两个顶点都可以通过有向路径相连，则称该图为________。
答案：强连通图三、简答题1. 请简述图论中的欧拉路径和哈密顿路径的定义。
答案：欧拉路径是指在图中经过每条边恰好一次的路径，而哈密顿路径是指在图中经过每个顶点恰好一次的路径。
2. 什么是图的着色问题？答案：图的着色问题是指将图中的顶点用不同的颜色进行标记，使得相邻的两个顶点颜色不同。
四、计算题1. 给定一个无向图G，顶点集为{A, B, C, D, E}，边集为{AB, BC, CD, DE, EA}，请画出该图，并计算其最小生成树的权重。
答案：首先画出图G的示意图，然后使用克鲁斯卡尔算法或普里姆算法计算最小生成树的权重。
习题一1. 一个工厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；这样就得到一个无向图。
若每点的度数为3，则总度数为27，与图的总度数总是偶数的性质矛盾。
若仅有四个点的度数为偶数，则其余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是偶数的性质矛盾。
（或者利用度数为奇数的点的个数必须为偶数个）2.若存在孤立点，则m 不超过K n-1的边数, 故m <= (n-1)(n-2)/2, 与题设矛盾。
3.4. 用向量(a 1,a 2,a 3)表示三个量杯中水的量, 其中a i 为第i 杯中水的量, i = 1,2,3.以满足a 1+a 2+a 3 = 8 (a 1,a 2,a 3为非负整数)的所有向量作为各结点, 如果(a 1,a 2,a 3)中某杯的水倒满另一杯得到 ( a ’1, a ’2, a ’3 ) , 则由结点到结点画一条有向边。
这样可得一个有向图。
本题即为在此图中找一条由( 8, 0, 0 )到( 4, 4, 0 )的一条有向路，以下即是这样的一条：5. 可以。
6 若9个人中没有4个人相互认识，构造图G ，每个点代表一个点，两个人相互认识则对应的两个点之间有边。
1） 若可以找到点v ，d(v)>5，则与v 相连的6个点中，要么有3个相互认识，要么有3个相互不认识（作K 6并给边涂色:红=认识，蓝=不认识，只要证图中必有同色三角形。
v 1有5条边，由抽屉原则必有三边同色(设为红)，这三边的另一顶点设为v 2, v 3, v 4。
若 △v 2v 3v 4有一边为红，则与v 1构成红色△，若△v 2v 3v 4的三边无红色，则构成蓝色△）。
若有3个人相互认识，则这3个人与v 相互认识，这与假设没有4个人相互认识矛盾，所以这6个人中一定有3个人相互不认识2） 若可以找到点v ，d(v)<5，不与v 相连的点至少有4个，由于没有4个人相互认识，所以这4个人中至少有2个人相互不认识，这两个人与v 共3个人相互不认识∑∑∑∑∑∑∑==+====-=++=-==---=--=ni i n i i n i n i n i ni i i n i i n i i i i a a n n a a a n n n a n a v v 12 12 12112212 12 i i 2/)1(C )1(2)1(])1[(a a 。
， 所以 因为 ，＋ 的负度数，则为结点的正度数，为结点记－－－－－( 8, 0, 0 ) ( 5, 3, 0 ) ( 5, 0, 3 ) ( 2, 3, 3 ) ( 2, 5, 1 )(7, 0, 1 ) ( 7, 1, 0 ) ( 4, 4, 0 )( 4, 1, 3 )3） 若每个点的度数都为5，则有奇数个度数为奇数的点，不可能。
7. 同构。
同构的双射如下：8. 记e 1= (v 1,v 2), e 2= ( v 1,v 4), e 3= (v 3,v 1), e 4= (v 2,v 5), e 5= (v 6,v 3), e 6= (v 6,v 4), e 7= (v 5,v 3), e 8= (v 3,v 4), e 9 = (v 6,v 1), 则邻接矩阵为： 关联矩阵为：边列表为：A= (1,1,3,2,6,6,5,3,6), B= (2,4,1,5,3,4,3,4,1). 正向表为：A= (1,3,4,6,6,7,10), B= (2,4,5,1,4,3,3,4,1).⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡---------100110000001001000010100010011010100000001001100000111, 001101000100000000001001010000001010⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡习题二1.用数学归纳法。
k=1时，由定理知结论成立。
设对于k命题成立。
对于k+1情形，设前k个连通支的结点总个数为n1, 则由归纳假设，前k个连通支的总边数m1<= ( n1－k+1)( n1－k)/2。
最后一个连通支的结点个数为n－n1, 其边数m2<= ( n－n1)( n－n1－1)/2，所以，G的总边数m= m1+ m2<= ( n1－k+1)( n1－k)/2 + ( n－n1)( n－n1－1)/2n1=n－1时，m<= ( (n-1)－k+1)( (n-1)－k)/2 +0= ( (n－k)( (n－k－1)/2, 命题成立。
n1＜= n－2时，由于n1<=k, 故m<= ( (n－2)－k+1)( n1－k)/2 + ( n－n1)( n－k－1)/2＝( n－k)( n－k－1)/2 , 命题成立。
2．若G连通，则命题已成立；否则，G至少有两个连通支。
任取结点v1, v2，若G的补图中边(v1, v2)不存在，则(v1, v2)是G中边，v1, v2在G的同一个连通支（假设为G1）中。
设G2是G的另一连通支，取v3∈G2,则v1→ v3→v2是补图中v1到v2的一条道路，即结点v1, v2在补图中有路相通。
由v1, v2的任意性，知补图连通。
3．设L1,L2是连通图G的两条最长路，且L1,L2无公共结点。
设L1,L2的长度(边数)为p.由于G是连通的，故L1上必有一结点v1与L2上一结点v2有道路L’相通。
结点v1将L1分为两部分，其中一部分的长度≥ p/2 , 记此部分道路为L3。
同样，结点v2将L2分为两部分，其中一部分L4的长度≥ p/2 。
这样，L3＋L’＋L4就是G的一条新的道路，且其长度大于p, 这与G的最长路(L1)的长度是p的假设矛盾。
4. 对结点数n作归纳法。
（1）n= 4时m≥5. 若有结点的度≤1, 则剩下的三结点的度数之和≥4，不可能。
于是每个结点的度≥2，从而存在一个回路。
若此回路为一个三角形，则还有此回路外的一结点，它与此回路中的结点至少有二条边，从而构成一个新的含全部四个结点的回路，原来三角形中的一边（不在新回路中）即是新回路的一条弦。
若此回路为含全部四个结点的初等回路，则至少还有一边不在回路上，此边就是该回路的一条弦。
（2）设n-1情形命题已成立。
对于n情形：若有结点的度≤1, 则去掉此结点及关联边后，依归纳假设命题成立。
若有结点v的度=2, 设v关联的两结点为s,t，则去掉结点v及关联边、将s,t合并为一个结点后，依归纳假设命题成立。
若每个结点的度≥3，由书上例2.1.3的结果知命题成立。
5 a)对于任意边(u,v),由于不存在三角形，所以d(u)+d(v)<=n，对所有m条边求和，不等式左边每个d(v)被计算了d(v)次b) 对n归纳，设小于n时不等式成立，当|V|=n时，删去边(u,v)及点u，v以及相关的边得到G'，由归纳假设，G'最多(n-2)2/4条边，由于(u,v)与G'不构成三角形，因此由G'变回G时最多增加(n-2)+1条边，所以G的边最多(n-2)2/4+(n-2)+1=n2/4注：此题与三角形的存在性无关设最大度数为k，且d(v)=k，令E0={与v相连的边}，E1={不与v相连的边}，则|E0|=k，|E1|<=(n-k-1)*k，其中n-k-1表示去除了v及其邻点，这些点的度数都小于等于km=|E0|+|E1|<=nk-k2<= n2/46．问题可化为求下列红线表示的图是否存在一条欧拉道路的问题：存在欧拉道路！7 设C是H道路，当S中顶点在C上不相邻时，C-S最多被分成|S|+1段，而当S中顶点有相邻时段数将更少，而C是G的生成子图，所以t<=|S|+18．由推论2.4.1, 只需验证G的任意一对结点的度数之和大于或等于n即可。
若存在结点v1, v2满足deg(v1)+deg(v2)<n, 则G－{v1, v2} 的边数<= K n-2的边数= (n-2)(n-3)/2 .另一方面，由题设知G－{ v1, v2} 的边数＝m－（deg(v1)+deg(v2)）＞[(n-1)(n-2)/2+2]－n= (n-2)(n-3)/2 ,与上式矛盾。
9 对n进行数学归纳法，设n小于等于k时命题成立，则当n=k+1时对任意顶点v，G-v得到的G'仍是有向完全图，由归纳假设存在H道路v1v2…v k若G中存在边(v,v1)或(v k,v)则命题成立否则G中存在边(v1,v)和(v,v k)，这也意味着可以找到i，1<=i<k，有边(v i,v)和(v,v i+1) 此时v1v2…v i vv i+1….v k为H道路10 对于任意的点u,v，若u与v认识，则d(u)+d(v)=(n-2)+2=n若u不认识v，则从V-{u,v}中让取一点w，w认识u和v否则若w不认识u，则v和w都不认识u，v和w合起来只能最多认识n-3个人，矛盾。
由w的任意性，d(u)+d(v)>=2(n-2)，当n>=4时，2(n-2)>=n所以对任意两个点度数和大于等于n11 对于这q条边，每条边的两个端点压缩合并为一个点，并去掉重边得到G'G'各点度数均大于等于n/2，所以存在H回路，该回路中q个新点恢复成原2q个点，则所代表的q条边仍在此H回路中注：q不能超过n/212 构造图G，每个小立方体对应一个点，两个立方体之间有公共面则对应顶点间有边设最左上角点为黑色，依据相邻点不同色的原则给所有点着色，则黑色点有14个，白色点有13个，若所要求路径存在，则意味着从黑色点开始遍历这27个点到达白色点，这不可能13．1）将边按权值由小到大排序：边：a23a35a15a13a34a45a24a12a25a14权：26 27 29 33 34 35 38 42 49 522)分支定界：S1: a23a35a15a13a34 , 非H回路,d (S1)=149;将a34置换为其后的a45, a24，a12，a25，a14，也全都是非H回路；S2: a23a35a15a34a45, 非H回路,d(S2)=151;将a45置换为其后的a24，a12，a25，a14，也全都是非H回路；S3: a23a35a15a45a24 , 非H回路,d (S8)=155;将a24置换为其后的a12，a25，a14，也全都是非H回路；S4: a23a35a15a24a12 , 非H回路,d (S4)=162;S5: a23a35a15a24a25 , 非H回路,d (S5)=169;S6: a23a35a15a24a14 , H回路,d0:=172;S7: a23a35a15a12a25 , 非H回路,d (S7)=173;S8: a23a35a13a34a45 , 非H回路,d (S8)=155;将a34 , a45置换为其后的数，也全都是非H回路；S9: a23a35a34a45a24 , 非H回路,d (S9)=160;将a45 , a24置换为其后的数，也全都是非H回路；S10: a23a35a45a24a12 , 非H回路,d (S10)=168;将a12置换为其后的a25 , a14，也全都是非H回路；S11: a23a35a45a12a25 , 非H回路,d (S11)=179;将a12 ,a25置换为其后的数，其路长差于d0，故不必考虑；S12: a23a35a24a12a25, 非H回路,d (S12)=182;将a24，a12，a25,置换为其后的数，其总长差于d0，故不必考虑；继续下去所得组长度会比S6差，故可终止计算。
