WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
图论部分简介
图论相关概念
图的存储
DFS（图论）
BFS（图论）
树基础
树的直径
最近公共祖先
树的重心
树链剖分
树上启发式合并
虚树
树分治
动态树分治
AHU算法
树哈希
矩阵树定理
有向无环图
拓扑排序
最小生成树
斯坦纳树
最小树形图
最小直径生成树
最短路
拆点
差分约束
k 短路
同余最短路
强连通分量
双连通分量
割点和桥
2-SAT
欧拉图
哈密顿图
二分图
最小环
平面图
图的着色
网络流简介
最大流
最小割
费用流
上下界网络流
Prufer 序列
LGV 引理
弦图
46 objects
本站非官方，所收集资源均来源于网络。
哈密顿图 - 图论
## 定义 通过图中所有顶点一次且仅一次的通路称为哈密顿通路。 通过图中所有顶点一次且仅一次的回路称为哈密顿回路。 具有哈密顿回路的图称为哈密顿图。 具有哈密顿通路而不具有哈密顿回路的图称为半哈密顿图。 ## 性质 设 $G=<V, E>$ 是哈密顿图，则对于 $V$ 的任意非空真子集 $V_1$ ，均有 $p(G-V_1) \leq |V_1|$ 。其中 $p(x)$ 为 $x$ 的连通分支数。 推论：设 $G=<V, E>$ 是半哈密顿图，则对于 $V$ 的任意非空真子集 $V_1$ ，均有 $p(G-V_1) \leq |V_1|+1$ 。其中 $p(x)$ 为 $x$ 的连通分支数。 完全图 $K_{2k+1} (k \geq 1)$ 中含 $k$ 条边不重的哈密顿回路，且这 $k$ 条边不重的哈密顿回路含 $K_{2k+1}$ 中的所有边。 完全图 $K_{2k} (k \geq 2)$ 中含 $k-1$ 条边不重的哈密顿回路，从 $K_{2k}$ 中删除这 $k-1$ 条边不重的哈密顿回路后所得图含 $k$ 条互不相邻的边。 ## 充分条件 设 $G$ 是 $n(n \geq 2)$ 的无向简单图，若对于 $G$ 中任意不相邻的顶点 $v_i, v_j$ ，均有 $d(v_i)+ d(v_j) \geq n - 1$ ，则 $G$ 中存在哈密顿通路。 推论 1：设 $G$ 是 $n(n \geq 3)$ 的无向简单图，若对于 $G$ 中任意不相邻的顶点 $v_i, v_j$ ，均有 $d(v_i)+ d(v_j) \geq n$ ，则 $G$ 中存在哈密顿回路，从而 $G$ 为哈密顿图。 推论 2：设 $G$ 是 $n(n \geq 3)$ 的无向简单图，若对于 $G$ 中任意顶点 $v_i$ ，均有 $d(v_i) \geq \frac{n}{2}$ ，则 $G$ 中存在哈密顿回路，从而 $G$ 为哈密顿图。 设 $D$ 为 $n(n \geq 2)$ 阶竞赛图，则 $D$ 具有哈密顿通路。 若 $D$ 含 $n(n \geq 2)$ 阶竞赛图作为子图，则 $D$ 具有哈密顿通路。 强连通的竞赛图为哈密顿图。 若 $D$ 含 $n(n \geq 2)$ 阶强连通的竞赛图作为子图，则 $D$ 具有哈密顿回路。
wiki(I:)
比赛相关
图论部分简介
