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的初级回路。