切换科目
重点科目
主要科目
次要科目
科数网
首页
刷题
学习
VIP会员
赞助
组卷
集合
教材
VIP
写作
游客,
登录
注册
在线学习
离散数学
第五章 图论
哈密顿图
最后
更新:
2025-01-22 09:25
查看:
221
次
反馈
能力测评
会员8.2元/月
赞助
哈密顿图
哈密顿图与半哈密顿图 1859 年,哈密顿(Halmilton)爵士发明了一个关于十二面体的一个数学游戏,如图 8.11所示,一位旅行者沿着顶点标有城市名称的正十二面体的棱线行走,他要找一条通过每个顶点(城市)恰好一次的回路。这样就引出了一个问题:能不能在图中找到一条回路,使它含有这个图的所有顶点?哈密顿爵士把这个问题称为周游世界问题。 这一游戏抽象出图论中一个概念——哈密顿(Halmilton)图,并派生出货郎担(Traveling Salesman)问题。 定义8.26(哈密顿图)若图 $G$ 具有一条包含 $G$ 中所有顶点的回路,则称该回路为哈密顿回路,称 $G$ 为哈密顿图。若图 $G$ 具有一条包含 $G$ 中所有顶点的路,则称该路为哈密顿路,称 $G$ 为半哈密顿图。 显然哈密顿路通过图中每个顶点一次且仅一次,哈密顿  图8.11回路则是从图中的一个顶点出发,通过每个顶点一次且仅一次,最后回到出发点的回路。 对于哈密顿图的性质,首先要说明的是有关哈密顿图性质的研究成果与欧拉图性质的研究成果不同,哈密顿图的充要条件至今仍然是图论中尚未解决的主要问题之一。我们只能分别给出哈密顿图的充分条件和必要条件。首先我们给出哈密顿图的必要条件。 定理 8.19 (必要条件)若图 $G$ 是哈密顿图,则对于顶点集 $V$ 的每一个非空真子集 $S$ , $\omega(G-S) \leqslant|S|$ 均成立,其中 $|S|$ 表示 $S$ 中的顶点数,$G-S$ 表示 $G$ 中删去顶点子集 $S$ 后得到的图。 证明:设 $C$ 是图 $G$ 的一个哈密顿回路,则对 $V$ 的每一个非空真子集 $S, \omega(C-S) \leqslant|S|$ ;则 $\omega(G-S) \leqslant \omega(C-S) \leqslant|S|$ 。 利用定理 8.19 可以判定某些图不是哈密顿图。如图8.12(a)中,令 $S=\left\{v_1, v_4\right\}$ ,则 $\omega(G-S)=3>|S|$ ,所以该图不是哈密顿图。 方程
高斯
黎曼
傅里叶变换(复数)
拉普拉斯变换(复数)
高等数学测评
函数与极限
一元函数微分学
一元函数积分学
微分方程
空间向量与代数
多元微分学
多元积分学
无穷级数
《线性代数》难点解析
线代教程
近世代数对数学的整体思考
线性的意义
矩阵乘法(列视角)
矩阵乘法(行视角)
矩阵左乘
矩阵右乘
逆矩阵求解方程组
阶梯形矩阵的求法
方程组解的判定
四阶行列式的计算
线性变换的意义
线性空间
向量组的等价
线性空间的几何意义
基础解系的求法
施密特正交化
特征值与特征向量的意义
矩阵相似的几何意义
矩阵可对角化的理解
秩的意义(向量版)
秩的意义(方程版)
二次型的意义
线性代数测评
行列式
矩阵
向量空间
《概率论与数理统计》难点解析
概率教程
置信区间与上a分位数
概率中的“取”与“放”
贝叶斯公式
全概率公式
泊松分布
指数分布
伽玛分布
二维密度图的意义
卷积的意义
相关系数的意义
k阶矩是与矩母函数
卡方分布的作用
单正态区间估计理解
假设检验理解
切比雪夫不等式
中心极限定理
概率统计测评
事件与概率
一维随机变量与事件
多维随机变量与事件
随机变量的数字特征
大数定律与中心极限定理
统计量与抽样分布
参数估计
假设检验
上一篇:
欧拉图和半欧拉图
下一篇:
哈密顿有向图
本文对您是否有用?
有用
(
0
)
无用
(
0
)
更多
学习首页
数学试卷
同步训练
投稿
会议预约系统
数学公式
关于
Mathhub
赞助我们
科数网是专业专业的数学网站 版权所有
本站部分教程采用AI制作,请读者自行判别内容是否一定准确
如果页面无法显示请联系 18155261033 或 983506039@qq.com