最后更新: 2025-01-22 09:27 查看: 112 次反馈能力测评会员8.2元/月赞助

哈密顿有向图

定义 8.28 （哈密顿有向图）若有向图 $G$ 具有一条包含 $G$ 中所有顶点的有向回路，则称

该有向回路为哈密顿回路，称 $G$ 为哈密顿有向图。若有向图 $G$ 具有一条包含 $G$ 中所有顶点的有向路，则称该路为哈密顿有向路，称 $G$ 为半哈密顿有向图。

显然哈密顿有向图是包含 $G$ 中每个顶点一次且仅一次的有向回路，所以哈密顿有向图必定是强连通图。在这里我们仅考虑一种比较简单的情况，给出哈密顿有向图的充分条件。

定理8．22 任何一个竞赛图是半哈密顿有向图。
证明：若竞赛图的顶点数小于 4 ，显然有一条哈密顿有向路。
归纳步骤：假设 $n$ 个顶点的任一竞赛图是半哈密顿有向图。设 $G$ 是 $n+1$ 个顶点的竞赛图，从 $G$ 中删去顶点 $v$ 及其关联边，得到有向图 $G^{\prime \prime}$ ，由归纳假设，$G^{\prime}$ 有哈密顿有向路 $\left(v_1, v_2, \cdots, v_n\right), G$有 3 种情况。
（1）在 $G$ 中有一条弧 $\left(v, v_1\right)$ ，则有哈密顿有向路 $\left(v, v_1, v_2, \cdots, v_n\right)$ ；
（2）在 $G$ 中没有弧 $\left(v, v_1\right)$ ，则必有弧 $\left(v_1, v\right)$ 。若存在 $v_i, v_i$ 是 $v_1$ 之后第一个碰到并且有弧 $\left(v, v_i\right)$的顶点，则显然得到一条哈密顿有向路（ $v_1, v_2, \cdots, v_{i-1}, v, v_i, \cdots, v_n$ ）；；
（3）在 $G$ 中没有弧 $\left(v, v_i\right)$ ，而对所有 $v_i$ ，均有弧 $\left(v_i, v\right), i=1,2, \cdots, n$ ，则得一条哈密顿有向路（ $v_1, v_2, \cdots, v_n, v$ ）。

所以，由定理 8．22，$n$ 位网球选手进行单循环比赛，这 $n$ 位选手一定能依次排出一个优胜次序，然而这种次序可能有几种。进一步，我们可以得到一个更强的结果。

定理 8.23 任何一个强连通的竞赛图 $G$ 必是哈密顿有向图。
证明：下面证明一个 $n$ 个顶点的强连通竞赛图 $G$ 包含长度为 $3,4, \cdots, n$ 的有向回路。

免费注册看余下 70%

非VIP会员每天5篇文章，开通VIP 无限制查看

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

高等数学测评 函数与极限一元函数微分学一元函数积分学微分方程空间向量与代数多元微分学多元积分学无穷级数

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

线性代数测评 行列式矩阵向量空间

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

概率统计测评 事件与概率一维随机变量与事件多维随机变量与事件随机变量的数字特征大数定律与中心极限定理统计量与抽样分布参数估计假设检验

上一篇：哈密顿图

下一篇：最短路

本文对您是否有用？有用 (0) 无用 (0)