8图论习题

图论课后习题答案图论是数学中的一个分支，主要研究图的结构和性质。

图论的课后习题通常包括证明题、计算题和应用题。

下面给出一些典型的图论课后习题答案：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. 证明题：证明在任何图中，边数至少是顶点数减一。

答案：考虑一个图的生成树，它是一个最小的连通子图，包含图中的所有顶点，并且没有环。

在生成树中，边数等于顶点数减一。

由于任何图都至少包含一个生成树，因此原图的边数至少与生成树的边数相同，即至少是顶点数减一。

初二最短路径问题练习题在图论中，最短路径问题是指在一个加权有向图或无向图中，找到两个顶点之间的最短路径。

最短路径可能是指权重之和最小的路径，或者是指路径上边的数量最少。

最短路径问题有许多种解决方法，其中最著名且广泛应用的算法是狄克斯特拉算法（Dijkstra's algorithm）。

该算法在计算机科学领域被广泛应用于路由算法、网络传输以及学术研究中。

我们来通过一个初二级别的练习题来巩固对最短路径问题的理解。

假设有一个城市地图，有五个地点：A、B、C、D和E。

每两个地点之间都有一条路径，路径上标有权重，代表两个地点之间的距离。

如下图所示：```1 3 4(A)------(B)------(D)------(E)| | /| | /| | /2 5 1\ /\ /(C)```现在，我们想要从地点A到达地点E，但希望选择一条最短路径。

我们可以使用狄克斯特拉算法来解决这个问题。

首先，我们需要创建一个包含所有地点的列表，并初始化每个地点的距离为无穷大。

然后，我们将起点A的距离设置为0，并将其添加到一个称为“未访问集合”中。

接下来，我们开始循环，直到我们找到到达终点E的最短路径或者我们访问了所有的地点。

在每一轮循环中，我们从未访问集合中选择距离起点A最近的地点，并将其标记为已访问。

然后，我们更新与该地点相邻的所有未访问地点的距离，如果新的路径较短的话。

最后，当我们找到到达终点E的最短路径时，我们可以通过回溯来获取完整的路径。

根据以上算法，我们可以求解出从地点A到达地点E的最短路径。

假设初始设置如下：地点A的最短路径长度为0，其他地点的最短路径长度为无穷大。

未访问集合：A、B、C、D、E首先，我们选择地点A作为起点，因为它的距离最小。

我们更新地点A相邻的地点的距离。

更新后的距离如下：A: 0B: 1C: 2D: ∞E: ∞接下来，我们选择距离最小的地点B，并更新它相邻地点的距离。

更新后的距离如下：A: 0B: 1C: 2D: 4E: ∞然后，我们选择距离最小的地点C，并更新它相邻地点的距离。

《图论》练习题(2014)1、利用Dijkstra 算法求下图中顶点0v 到其它各顶点的距离，并写出到顶点8v 的最短路。

2、1、列出色数3为的三个图： 。

2、p 阶完全图的色数为： 。

3、p 阶树的邻接多项式为： 。

4、p 阶完全图的邻接多项式为： 。

5、如下图所示的图的邻接矩阵为 ，关联矩阵为 。

6、度序列为(2,2,2,2,2,2)的简单图是 。

7、是否存在度序列为(2,2,3,4,5,6)，(1,2,3,4,4,5)的简单图？若存在，给出一个图；若不存在，请说明理由。

8、画出如下图的所有生成子图。

9、设图G 如下图所示，求该图的生成树个数)(G 。

v 2v 6v 4v 610、已知图G （V 、E ），画出G －V 5，G －v 3v 4，G[{v 2，v 3，v 5}]，G[{v 3v 4，v 4，v 6，v 7v 8}]G ：11、已知图G 的邻接矩阵⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=2111102112011111A ，画出G ，并求出度序列。

12、证明：偶图G 的任意子图H 仍为偶图。

13、证明：设图G （V 、E ）的度序列为（p d d d ,,,21 ），边数为q ，则q i d pi 21==∑14、证明：在任何图中，奇顶点个数为偶数。

15、证明：整数序列（6，6，5，4，3，3，1）不可能为一个简单图的图序列。

16、证明顶点度数均为2的简单连通图是圈。

17、证明非平凡树T 的边连通度为'()1T κ=。

18、n 阶完全图n K 的连通度为()1T n κ=-。

19、设G 是一个p 阶图，且()()21,-≥∈∀p v d G V v ，则G 连通图。

20、若图G 是 不连通的，则其补图G C 是连通的。

21、证明：设G 是由1G 和2G 两个连通分支组成的图，则);();();(21x G P x G P x G P =。

v 1v 2v 3v 4v 5v 6v 8v 722、证明：设G 是由1G 和2G 两个连通分支组成的图，则)}(),(max{)(21G G G χχχ=。

习题八8.1 设V={u,v,w,x,y}, 画出图G: (V ,E).(1) E={(u,v),(u,x),(v,w),(v,y),(x,y)} (2) E={(u,v),(v,w),(w,x),(w,y),(x,y)} 再求每个结点的次数。

8.2 设G 是具有4个结点的完全图：(1) 写出G 的所有子图； (2) 写出G 的所有生成子图。

8.3 画出一个多重图，使它们的邻接矩阵为1300301101220120⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭. 8.4 对于图1，试求(1) 从a 到h 的所有基本通路； (2) 从a 到h 的所有简单通路； (3) 从a 到h 的距离。

he d图18.5 图2中哪个有欧拉通路、有欧拉回路、有汉密尔顿通路、有汉密尔顿回路？b ce图28.6 图G 1，G 2的邻接矩阵分别为A 1，A 2，试求：(1) 23231122,,,A A A A ;(2) 在G 1内列出每两个结点间的距离； (3) 列出G 1，G 2中的所有基本回路。

10011000001100101010001001A ⎛⎫ ⎪⎪ ⎪= ⎪ ⎪⎪⎝⎭，20001100000001100010001010100100100001000000100000A ⎛⎫⎪⎪ ⎪ ⎪= ⎪ ⎪⎪⎪ ⎪⎝⎭8.7 设有向图D 如下，试求：(1) 每个结点的入次与出次； (2) 它的邻接矩阵M D ； (3) D 是强连通、弱连通还是单向连通？ (4) 求从a 到c 长度小于或等于3的通路数。

8.8 D 是具有结点v 1、v 2、v 3、v 4的有向图，它的邻接矩阵表示如下：0111011011011000⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭(1) 画出这个图； (2) D 是强连通还是单向连通？(3) 求从v 1到v 1长度是3的回路，从v 1到v 2、v 1到v 3、v 1到v 4长度是3的通路数。

习题九9.4 设有代数表示式如下：42(35)(2)x y a b c -+，试画出这个表示式的树. 第四篇1. 在图G=(V,E)中，结点次数与边数的关系是下面4个中的哪一个？ (1) deg()2||i v E = (2) deg()||i v E = (3)deg()2||v Vv E ∈=∑ (4) deg()||v Vv E ∈=∑2. 设G 是n 个结点的无向完全图，则图G 的边数是多少？设D 是n 个结点的有向完全图，则图D 的边数又是多少？3. 仅有一个结点是图称为什么图？4. 设G=(V ,E)为无向简单图，|V|=n ，∆(G)为G 中结点的最大次数，请指出下面4个中哪个不等式是正确的。

图论部分一、选择题：1．欧拉回路是（B ）A. 路径B. 简单回路C. 既是基本回路也是简单回路D.既非基本回路也非简单回路 2．哈密尔顿回路是（C ）A. 路径B. 简单回路C. 既是基本回路也是简单回路D.既非基本回路也非简单回路 3．设G 是简单有向图，可达矩阵P(G)刻划下列关系中的是（C ） A 、点与边 B 、边与点 C 、点与点 D 、边与边4．下列哪一种图不一定是树（C ）。

A.无简单回路的连通图B. 有n 个顶点n-1条边的连通图C. 每对顶点间都有通路的图D. 连通但删去一条边便不连通的图 5.下列哪个不是两个图同构的必要条件A. 结点数目相等B. 边数相等C. 度数相同的结点数目相同D. 两个图都是平面图 6．在有n 个结点的连通图中，其边数（B ）A. 最多有n-1条B. 至少有n-1条C. 最多有n 条D. 至少有n 条 7．下列图为树的是（C ）。

A 、>><><><=<},,,,,{},,,,{1d c b a a a d c b a G B 、>><><><=<},,,,,{},,,,{2d c d b b a d c b a G C 、>><><><=<},,,,,{},,,,{3a c d a b a d c b a GD 、>><><><=<},,,,,{},,,,{4d d c a b a d c b a G 二、填充题：1、n 阶无向完全图K n 的边数是(2)1(-n n )，每个结点的度数是(n-1)。

2、n 个结点的有向完全图边数是(n(n-1))，每个结点的度数是(2n-2)。

3、设有向图G = < V ，E >，},,,{4321v v v v V =的邻接矩阵⎪⎪⎪⎪⎪⎭⎫⎝⎛=00010*******1010A ， 则1v 的入度)(deg 1v -= 3 ，4v 的出度)(deg 4v +=1 ，从2v 到4v 的长度为2的路有 1 条。

二、应用题题0：（1996年全国数学联赛）有n（n≥6）个人聚会，已知每个人至少认识其中的[n/2]个人，而对任意的[n/2]个人，或者其中有两个人相互认识，或者余下的n-[n/2]个人中有两个人相互认识。

证明这n个人中必有3个人互相认识。

注：[n/2]表示不超过n/2的最大整数。

证明将n个人用n个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G。

由条件可知，G是具有n个顶点的简单图，并且有（1）对每个顶点x，)N G≥[n/2]；(x（2）对V的任一个子集S，只要S＝[n/2]，S中有两个顶点相邻或V-S中有两个顶点相邻。

需要证明G中有三个顶点两两相邻。

反证，若G中不存在三个两两相邻的顶点。

在G中取两个相邻的顶点x1和y1,记N G(x1)＝{y1,y2,……,y t}和N G(y1)={x1,x2,……,x k},则N G(x1)和N G(y1)不相交，并且N G(x1)（N G(y1)）中没有相邻的顶点对。

情况一；n=2r：此时[n/2]＝r，由（1）和上述假设，t=k=r且N G(y1)＝V-N G(x1)，但N G(x1)中没有相邻的顶点对，由（2），N G(y1)中有相邻的顶点对，矛盾。

情况二；n=2r+1: 此时[n/2]＝r，由于N G(x1)和N G(y1)不相交，t≥r,k≥r,所以r+1≥t,r+1≥k。

若t=r+1,则k=r，即N G(y1)=r，N G(x1)＝V-N G(y1)，由（2），N G(x1)或N G(y1)中有相邻的顶点对，矛盾。

故k≠r+1，同理t≠r+1。

所以t=r,k=r。

记w∈V- N G(x1) ∪N G(y1),由（2），w分别与N G(x1)和N G(y1)中一个顶点相邻，设wx i0∈E, wy j0∈E。

若x i0y j0∈E，则w，x i0, y j0两两相邻，矛盾。

若x i0y j0∉E，则与x i0相邻的顶点只能是(N G(x1)-{y j0})∪{w},与y j0相邻的顶点只能是(N G(y1)-{x j0})∪{w}。

图论试题及答案解析图片一、选择题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 设图G有12条边，G中有1度结点2个，2度结点2个，4度结点3个，其余结点度数不超过3．求G中至少有多少个结点？2 设有向简单图G的度数序列为(2,2,3,3）, 入度序列为(0,0,2,3),求G得出度序列 .3 设D是n阶有向简单完全图,则图D的边数为 .4设G是n阶无向简单完全图K n，则图G的边数为 .5 仅有一个孤立结点组成的图称为( )(A)零图(B)平凡图(C)补图(D)子图6设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有N k个k度顶点，N k+1个k+1度顶点，则N k = .7设图G如右图.已知路径(1) P1=(v1e5 v5e7 v2e2 v3 )(2) P2=(v5e6 v2e2 v3e3 v4e8 v2e7 v5)(3) P3=(v2e7 v5e6 v2)(4) P4=(v1e1 v2e2 v3e3 v4e8 v2e6 v5)判断路径类型，并求其长度.81）判断下图G1中的路径类型, 并求其长度. P1=(v3e5v4e7v1e4v3e3v2e1v1e4v3)P2=(v3e3v2e2v2e1v1e4v3)P3=(v3e3v2e1v1e4v3).2）判断下图G2中的路径类型, 并求其长度. P1=(v1e1v2e6v5e7v3e2v2e6v5e8v4)P2=(v1e5v5e7v3e2v2e6v5e8v4)P3=(v1e1v2e6v5e7v3e3v4).v1e1e5v2e65e7e4 e2e8v3 4e3v e v1 设图G 有12条边，G 中有1度结点2个，2度结点2个，4度结点3个，其余结点度数不超过3．求G 中至少有多少个结点？ 至少9个2 设有向简单图G 的度数序列为(2,2,3,3）, 入度序列为(0,0,2,3),求G 得出度序列 （2,2,5,6） .3 设D 是n 阶有向简单完全图,则图D 的边数为 )1(−n n .4 设G 是n 阶无向简单完全图K n ，则图G 的边数为 m =n (n -1)/2 .5 仅有一个孤立结点组成的图称为( B ) (A) 零图 (B)平凡图 (C)补图 (D)子图6设n 阶图G 中有m 条边，每个结点的度数不是k 的是k+1，若G 中有N k 个k 度顶点，N k+1个k+1度顶点，则N k = N k =(k+1)n-2m . 7设图G 如右图.已知路径 (1) P 1=(v 1e 5 v 5e 7 v 2e 2 v 3 ) (2) P 2=(v 5e 6 v 2e 2 v 3e 3 v 4e 8 v 2e 7 v 5) (3) P 3=(v 2e 7 v 5e 6 v 2)(4) P 4=(v 1e 1 v 2e 2 v 3e 3 v 4e 8 v 2e 6 v 5)判断路径类型，并求其长度. (1) 初级通路；3 (2) 简单回路；5 (3) 初级回路；2 (4) 简单通路. 5 81）判断下图G1中的路径类型, 并求其长度. P 1=(v 3e 5v 4e 7v 1e 4v 3e 3v 2e 1v 1e 4v 3) P 2=(v 3e 3v 2e 2v 2e 1v 1e 4v 3) P 3=(v 3e 3v 2e 1v 1e 4v 3).2）判断下图G2中的路径类型, 并求其长度. P 1=(v 1e 1v 2e 6v 5e 7v 3e 2v 2e 6v 5e 8v 4) P 2=(v 1e 5v 5e 7v 3e 2v 2e 6v 5e 8v 4) P 3=(v 1e 1v 2e 6v 5e 7v 3e 3v 4).解：在图G 1中，v 3e 5v 4e 7v 1e 4v 3e 3v 2e 1v 1e 4v 3是一条长度为6的回路，但既不是简单回路，也不是初级回路； v 3e 3v 2e 2v 2e 1v 1e 4v 3是一条长度为4的简单回路，但不是初级回路； v 3e 3v 2e 1v 1e 4v 3是一条长度为3的初级回路。

《图论》期末考试模拟题（答案） ⼀、选择题 1、给定⽆向图如图所⽰，下⾯给出的顶点集⼦集中，是点割集的为（A,B,C,D）。

A. {b, d} B. {d} C. {a, c} D. {g, e} bf 内容需要下载⽂档才能查看 2、设V＝{a,b,c,d},与V能构成强连通图的边集E＝（ A ）。

A. {,,,,} B. {,,,,} C. {,,,,} {,,,,} 3、⼀个连通的⽆向图G，如果它的所有结点的度数都是偶数，那么它具有⼀条（ B ）。

A. 哈密尔顿回路 B. 欧拉回路 C. 哈密尔顿通路 D. 欧拉通路 4、如图所⽰各图，其中存在哈密顿回路的图是（ A, C ）。

内容需要下载⽂档才能查看 第 1 页共 5 页 图论期末考试题⽬参考 《图论》 5. 下图中既是欧拉图，⼜是哈密尔顿图的有（D）。

5、设G是有5个顶点的完全图，则G（ B ）。

D. ⽆哈密尔顿路 E. 可以⼀笔画出 F. 不能⼀笔画出 G. 是平⾯图 6、设G是连通简单平⾯图，G中有11个顶点5个⾯，则G中的边是（ D ）。

A. 10 B. 12 C. 16 D. 14 ⼆、填空题 1、完全图K8具有（ 28 ）条边。

2、图G如图所⽰， ab fc 那么图G的割点是（ a, f ）。

e d 3、⽆向图G为欧拉图，当且仅当G是连通的，且G中⽆（奇数度）结点。

第 2 页共 5 页 图论期末考试题⽬参考 《图论》 4、连通有向图D含有欧拉回路的充分必要条件是（ D中每个结点的⼊度＝出度）。

5、 n个结点、m条边的⽆向连通图是树当且仅当m=__（3）___。

(1) n+1 (2) n (3) n-1 (4)2n-1 三、 1、设图G=(P,E) 中有12条边，6个度数为3的顶点，其余顶点的度数均⼩于3，求G⾄少有多少个顶点。

解答：设G有n个顶点，由定理1， ∑d i=1nG(vi)=2m=24 (|E|=m) 由题设 24<3×6+3(n?6) ∴ 3n>24 即 n>8 因此，G中⾄少有9个顶点。

图论期末考试题库及答案一、单项选择题1. 图论的创始人是（）。

A. 欧拉B. 莱布尼茨C. 牛顿D. 高斯答案：A2. 在图论中，一个图的顶点集合为空，但边集合不为空的图称为（）。

A. 空图B. 完全图C. 树D. 多重图答案：A3. 如果一个图的任意两个顶点之间都存在一条路径，则称该图为（）。

A. 连通图B. 强连通图C. 弱连通图D. 无环图答案：A4. 在图论中，一个图的边的集合可以划分为若干个不相交的路径，使得图中的每个顶点恰好属于其中一条路径，这样的图称为（）。

A. 欧拉图B. 哈密顿图C. 树答案：C5. 图论中，一个图的边的集合可以划分为若干个不相交的回路，使得图中的每个顶点恰好属于其中一条回路，这样的图称为（）。

A. 欧拉图B. 哈密顿图C. 树D. 环答案：A二、多项选择题1. 下列哪些是图论中的基本术语（）。

A. 顶点B. 边D. 权重答案：ABCD2. 在图论中，以下哪些图是无向图（）。

A. 完全图B. 树C. 多重图D. 有向图答案：ABC3. 图论中，以下哪些图是连通图（）。

A. 完全图B. 树C. 多重图D. 空图答案：ABC三、填空题1. 图论中，一个图的顶点集合为V，边集合为E，那么图可以表示为G=（）。

答案：(V, E)2. 如果一个图的任意两个顶点之间都存在一条路径，则称该图为（）。

答案：连通图3. 在图论中，一个图的边的集合可以划分为若干个不相交的路径，使得图中的每个顶点恰好属于其中一条路径，这样的图称为（）。

答案：树四、简答题1. 请解释什么是图论中的“完全图”？答案：完全图是指图中每一对不同的顶点之间都恰好有一条边相连的图。

在完全图Kn中，n个顶点两两相连，共有n(n-1)/2条边。

2. 请解释什么是图论中的“欧拉路径”和“欧拉回路”？答案：欧拉路径是指图中存在一条路径，该路径恰好经过每条边一次。

欧拉回路是指图中存在一条回路，该回路恰好经过每条边一次。

五、计算题1. 给定一个图G=(V, E)，其中V={A, B, C, D, E}，E={(A, B), (B, C), (C, D), (D, E), (E, A), (A, C)}，请判断该图是否为连通图，并说明理由。

图论试题及答案解析图片一、选择题1. 在图论中，一个图的顶点数为n，那么这个图最多有多少条边？A. nB. n(n-1)/2C. n^2D. 2n答案：B解析：在一个无向图中，每个顶点最多与其他n-1个顶点相连，因此最多有n(n-1)/2条边。

2. 什么是连通图？A. 至少有一个环的图B. 任意两个顶点都可以通过路径相连的图C. 没有孤立顶点的图D. 所有顶点度数都大于0的图答案：B解析：连通图是指图中任意两个顶点都可以通过路径相连的图。

3. 在图论中，什么是哈密顿路径？A. 经过图中所有顶点的路径B. 经过图中所有边的路径C. 经过图中所有顶点的回路D. 经过图中所有边的回路答案：A解析：哈密顿路径是指经过图中所有顶点的路径。

4. 什么是二分图？A. 图的顶点可以被分成两个不相交的集合，使得同一集合内的顶点不相邻B. 图的顶点可以被分成两个不相交的集合，使得同一集合内的顶点相邻C. 图的边可以被分成两个不相交的集合，使得同一集合内的边不相邻D. 图的边可以被分成两个不相交的集合，使得同一集合内的边相邻答案：A解析：二分图是指图的顶点可以被分成两个不相交的集合，使得同一集合内的顶点不相邻。

5. 在图论中，什么是最小生成树？A. 包含图中所有顶点的最小边数的生成树B. 包含图中所有顶点的最小权重的生成树C. 包含图中所有边的最小权重的生成树D. 包含图中所有边的最小边数的生成树答案：B解析：最小生成树是指包含图中所有顶点的最小权重的生成树。

二、填空题1. 在无向图中，如果一个顶点的度数为n，则该顶点至少有______条边。

答案：n解析：一个顶点的度数是指与该顶点相连的边的数量。

2. 如果一个图是连通的，那么该图至少有______个连通分量。

答案：1解析：连通图的定义是图中任意两个顶点都可以通过路径相连，因此至少有一个连通分量。

3. 在图论中，一个图的色数是指给图的顶点着色，使得相邻顶点颜色不同，所需的最小颜色数。

二、应用题题0：（1996年全国数学联赛）有n （n ≥6）个人聚会，已知每个人至少认识其中的[n /2]个人，而对任意的[n /2]个人，或者其中有两个人相互认识，或者余下的n -[n /2]个人中有两个人相互认识。

证明这n 个人中必有3个人互相认识。

注：[n /2]表示不超过n /2的最大整数。

证明 将n 个人用n 个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G 。

由条件可知，G 是具有n 个顶点的简单图，并且有（1）对每个顶点x ，)(x N G ≥[n /2]；（2）对V 的任一个子集S ，只要S ＝[n /2]，S 中有两个顶点相邻或V-S 中有两个顶点相邻。

需要证明G 中有三个顶点两两相邻。

反证，若G 中不存在三个两两相邻的顶点。

在G 中取两个相邻的顶点x 1和y 1,记N G (x 1)＝{y 1,y 2,……,y t }和N G (y 1)={x 1,x 2,……,x k },则N G (x 1)和N G (y 1)不相交，并且N G (x 1)（N G (y 1)）中没有相邻的顶点对。

情况一；n=2r ：此时[n /2]＝r ，由（1）和上述假设，t=k=r 且N G (y 1)＝V-N G (x 1)，但N G (x 1)中没有相邻的顶点对，由（2），N G (y 1)中有相邻的顶点对，矛盾。

情况二；n=2r+1: 此时[n /2]＝r ，由于N G (x 1)和N G (y 1)不相交，t ≥r,k ≥r,所以r+1≥t,r+1≥k 。

若t=r+1,则k=r ，即N G (y 1)=r ，N G (x 1)＝V-N G (y 1)，由（2），N G (x 1)或N G (y 1)中有相邻的顶点对，矛盾。

故k ≠r+1，同理t ≠r+1。

所以t=r,k=r 。

记w ∈V- N G (x 1) ∪N G (y 1),由（2），w 分别与N G (x 1)和N G (y 1)中一个顶点相邻，设wx i0∈E, wy j0∈E 。

二、应用题题0 : (1996年全国数学联赛)有n (n_6)个人聚会，已知每个人至少认识其中的［n/2］个人，而对任意的［n/2］个人，或者其中有两个人相互认识，或者余下的n-［n/2］个人中有两个人相互认识。

证明这n个人中必有3个人互相认识。

注：［n/2］表示不超过n/2的最大整数。

证明将n个人用n个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G。

由条件可知，G是具有n个顶点的简单图，并且有(1)对每个顶点x, N G(X)工［n/2］;(2)对V的任一个子集S,只要S = ［n/2］, S中有两个顶点相邻或V-S中有两个顶点相邻。

需要证明G中有三个顶点两两相邻。

反证，若G中不存在三个两两相邻的顶点。

在G中取两个相邻的顶点X i和y i,记N G(X I)={y i,y2, ,y t}和N G(y i)={x i,X2, ,X k},贝U N G(X I)和N G(y i)不相交，并且N G(X I) (N G(y i)) 中没有相邻的顶点对。

情况一；n=2r:此时［n/2］=「，由(i)和上述假设，t=k=r 且N G(y i) = V-N G(X I)，但N G(X I)中没有相邻的顶点对，由(2), N G(y i)中有相邻的顶点对，矛盾。

情况二；n=2r+i:此时［n/2］= r,由于N G(X I)和N G(y i)不相交，t亠r,k ",所以r+i 亠t,r+i 丄k。

若t=r+i,则k=r，即N G(y i)=r, N G(X I)= V-N G(y i)，由(2), N G(X I)或N G(y i)中有相邻的顶点对，矛盾。

故k z r+i，同理r+i。

所以t=r,k=r。

记w^V- N G(X I) U N G(y i),由(2), w 分别与N G(X I)和N G(y i)中一个顶点相邻，设wx io，E, wy jo，E。

若X io y jo・E,则w , X io, y jo两两相邻，矛盾。