9.图的应用

欧拉图

定义

• 在连通图 G 中，经过 G 中每条边一次且仅一次的通路，称为欧拉通路
• 若欧拉通路为回路，则称为欧拉回路
• 具有欧拉回路的图称为欧拉图
• 含有欧拉通路但没有欧拉回路的图称为半欧拉图

无向图

• 无向连通图 G 是欧拉图的充分必要条件是 G 是连通的且 无奇点。
• 半欧拉图 当且仅当 G 是连通的且 只有两个奇度顶点，起点和终点就是这两个点

有向图

• 有欧拉图 当且仅当D连通，且每个顶点的入度都等于出度
• 有欧拉通路 当且仅当 D 连通，且有两个奇度顶点，其中一个入度比出度大1，一个出度比入度大1，其余顶点出度等于入度

哈密顿图

定义

• 给定无向图 G，若存在一条路 L，经过图中每个顶点一次且仅一次，则称 L 为哈密顿路，简称 H-路
• 若存在一条回路 C，经过图中每个顶点一次且仅一次，则称 C 为哈密顿回路，简称 H-回路
• 具有哈密顿回路的图称为哈密顿图，简称 H-图

必要条件：用来判断不符合

对于图\(G = <V,E>\)具有哈密顿，则 V 中的每个非空子集 \(V_S\)，都有

\(W(G-V_S)\le |V_S|\)

• \(W(G-V_S)\) 表示 \(G-V_S\)中连通分量数
• 即每个非空顶点子集满足，移除这些顶点后的图的连通分支数小于等于顶点数

充分条件

• G 为n阶无向简单图，若任意两个不相邻的顶点的度数之和大于等于 \(n-1\)，则 G 中存在哈密顿通路
• 当 \(n \ge 3\) 时，若任意连个不相邻的顶点的度数之和大于等于 n,则 G 中存在哈密顿回路
• 推论，当n 大于等于3是， Kn 均为哈密顿图

平面图

如果能将除顶点外边不相交地画在平面上，则是平面图，否则是非平面图。边可以画成弧的形式

无向树

• 无向树： 无回路的连通无向图
• 平凡树：平凡图
• 树叶：度数为1的顶点
• 分支，度数大于等于2的顶点

等价的定义

G 是n阶，m条边的无向图：

• G 是树
• G 中任意两个顶点存在唯一的路径
• G 无回路，\(m = n-1\)
• G 连通，\(m = n-1\)
• G 连通，G的任何边都是桥
• G 没有回路，任意两个顶点加一个边后有一个唯一的含新边的圈

---

• 任何一个树至少有两个树叶

生成树

G的生成树： G的生成子图，并且是树

• 生成树T的树枝： G在T中的边
• 生成树T的弦： G 不在 T 中的边
• 生成树T的余树，所有弦的集合导出的子图

最小生成树

带权图 权最小的生成树

最小生成树算法 Kruskal

• 将非环边按权从小到大排成 e1,e2,...,em
• 取e1在T中
• 检查 e2，若e2，和e1，不构成回路，则加入，否则，丢弃
• 重复上一步 直到生成树（加了n-1个边）