图论练习题

最短路径练习题一、选择题：1. 在图论中，最短路径问题是指在加权图中找到两个顶点之间的最短路径，以下哪个算法不是用于解决最短路径问题的？A. Dijkstra算法B. Bellman-Ford算法C. Prim算法D. A*搜索算法2. 以下哪个选项不是Dijkstra算法的前提条件？A. 图必须是有向图B. 所有边的权重必须非负C. 图中不能有负权重边D. 图可以是无向图3. 以下哪个算法可以处理包含负权重边的图？A. Dijkstra算法B. Bellman-Ford算法C. Floyd-Warshall算法D. A*搜索算法4. Floyd-Warshall算法的时间复杂度是：A. O(n^2)B. O(n^3)C. O(nlogn)D. O(n)5. 以下哪个选项是Dijkstra算法的步骤之一？A. 从起点开始，不断扩展最短路径树B. 从终点开始，不断扩展最短路径树C. 从每个顶点开始，计算到其他顶点的最短路径D. 从每个顶点开始，不断扩展最短路径树二、填空题：1. 在Dijkstra算法中，初始时，除了起点的最短路径为0外，其他所有顶点的最短路径都设为________。

2. Dijkstra算法中，当所有顶点都被访问过之后，算法结束，此时得到的距离数组中存储的是从起点到每个顶点的________。

3. Bellman-Ford算法可以处理图中的负权重边，但该算法不能处理图中的________。

4. Floyd-Warshall算法是一种动态规划算法，它可以在O(n^3)的时间复杂度内计算出图中所有顶点对之间的最短路径。

5. A*搜索算法是一种启发式搜索算法，它通过________和实际代价的和来估计从当前顶点到目标顶点的代价。

三、简答题：1. 描述Dijkstra算法的基本思想，并说明其在处理有向图中的最短路径问题时的优势。

2. 说明Bellman-Ford算法如何检测图中是否存在负权重环，并解释其在处理负权重边时的适用性。

课程类型数学
“托兰定理”讲义编号：
托兰定理在求极值的图论问题中具有重要作用，本讲主要介绍该定理及其相关方法。

定理：有n个顶点且不含三角形的简单图G中最多有[n2/4]条边。

证明
1
例1 设n≥2。

平面上已给2n个点，每三点不共线。

在这些点之间连n2+1条线段。

证明至少形成n个以已知
点为顶点的三角形。

【解答】
例2 由n个点和这些点之间的l条连线段组成一个空间四边形，其中n=q2+q+1，l≥1/2q(q+1)2+1，q≥2，q∈N。

已知此图中任四点不共面，每点至少有一条连线段，存在一点至少有q+2条连线段。

证明：图中必存在一个空
间四边形（即由四点A，B，C，D和四条连线段AB，BC，CD，DA组成的图形）
2。

离散数学特殊图练习题一、基本概念与性质1. 判断下列说法是否正确：（1）完全图是连通图。

（2）树是一个无环的连通图。

（3）平面图一定可以画在一个平面上，使得任意两边都不相交。

2. 填空题：（1）一个有n个顶点的完全图的边数为______。

（2）一个有n个顶点的连通图至少有______条边。

（3）一个有n个顶点的树有______条边。

二、特殊图的判定1. 判断下列图是否为特殊图，并说明理由：（1）一个有5个顶点的图，其中每个顶点的度数分别为4, 4, 3, 3, 2。

（2）一个有6个顶点的图，其中每个顶点的度数都为3。

2. 下列图是否为平面图？请给出证明或反例：（1）K5（完全图K5）。

（2）K3,3（完全二部图K3,3）。

三、特殊图的性质与应用1. 计算下列图的色数：（1）一个有5个顶点的完全图。

（2）一个有6个顶点的环形图。

2. 下列图是否存在哈密顿回路？请给出证明或反例：（1）一个有5个顶点的环形图。

（2）一个有6个顶点的完全二部图。

四、综合题（1）若G为连通图，则G至少有n1条边。

（2）若G为平面图，则G的边数e ≤ 3n 6。

（1）完全图K6。

（2）完全二部图K3,3。

（3）一个有5个顶点的树。

3. 设G是一个有8个顶点的连通图，其中每个顶点的度数都为3。

证明：G至少有一个哈密顿回路。

五、图的同构与子图（1）图G1：顶点集{A, B, C, D}，边集{AB, AC, BC, BD, CD}；图G2：顶点集{P, Q, R, S}，边集{PQ, PR, QR, QS, RS}。

（1）一个有4个顶点的完全图。

（2）一个有5个顶点的星形图。

六、路径与距离（1）一个有6个顶点的环形图。

（2）一个有5个顶点的完全图。

（1）一个有6个顶点的路径图，顶点A和顶点B分别位于路径的两端。

（2）一个有7个顶点的图，顶点A和B不相邻，但通过其他顶点可以到达。

七、欧拉图与哈密顿图（1）一个有5个顶点的环形图。

6
通路定理
[定理]通路定理 在n阶图G中，如果有顶点u到v （u v） 的通路，那么u到v必有一条长度小于等
于n1的基本通路。
7
通路定理证明
定理：在有n个顶点的图G中，如果有顶点u到v的通路，必有长 度不大于n-1的基本通路。
证明：(1)先证明u和v之间存在基本通路 若uv之间的通路P中有相同的顶点，则从P中删除相同顶点之间
路径，直到P中没有相同顶点，这样得到的路径为u和v之间的基 本通路。
(2) 再证基本通路长度不大于n-1 （反证法）设u和v之间的基本通路的长度≥ｎ。 ∵ 一条边关联两个顶点， ∴长度≥ｎ的基本通路上至少有ｎ＋１个顶点。 ∴至少有两个相同顶点在u和v之间的基本通路上，这与基本通路 的性质“任意两个顶点不同”相矛盾。
图G从vi点到vj点有通路当且仅当？
bij = 1
21
图的连通性与可达矩阵
有向图的连通性（n1）： 设有向图G的可达矩阵为B
(1) Ｇ强连通 B中元素全为１ (2) Ｇ是单向连通的 B中所有关于主对角线对称
的两个元素中至少一个值为１
无向图的连通性（n1）： 设无向图G的可达矩阵为B
Ｇ连通 B中元素全为１
[定义]基本通(回)路
结点各不相同的通路称为基本通路。 中间结点各不相同的回路称为基本回路。
A
基本通路：ACEBD
B
E
基本回路：ABCDEA
C
D
5
有向通(回)路
[定义]有向通(回)路 若通路v0v1 … vn各边是有向边，且vi-1和vi 分别是有向边的始点与终点，则称该通路为 有向通(回)路。
通路uxv相连。
由u和v的任意性，可知~G是连通的。
27