图论是离散数学的应用核心。本笔记覆盖图的定义与性质、连通性、欧拉图与哈密顿图（判定定理是重点），以及树、生成树、最小生成树和根树。

图的基本概念

定义

• 无向图 G=(V,E)：V 为顶点集，E 为边集（无序对）
• 有向图：E 为有序对（弧）
• 简单图：无环、无重边；多重图：有重边；完全图：任意两顶点相邻（Kₙ 有 n(n−1)/2 条边）
• 子图/生成子图：子图顶点集包含于 V；生成子图顶点集 = V

度（考点）

• 度 d(v)：与 v 关联的边数；有向图中分入度、出度
• 握手定理：所有顶点的度之和 = 2·边数（每条边贡献 2 个度）
• 推论：奇数度顶点的个数必为偶数

连通性

• 通路/回路：顶点序列，边不重复为简单通路；顶点不重复为初级通路
• 连通图：任意两顶点间有通路；连通分支数是图的连通分量个数
• 无向连通图：边数 ≥ 顶点数 − 1
• 强连通（有向图任意两点双向可达）/ 弱连通

欧拉图（重点）

概念	定义
欧拉通路	经过每条边恰好一次的通路
欧拉回路	经过每条边恰好一次且回到起点的回路
欧拉图	含欧拉回路的图

判定定理（核心考点）：

• 无向图有欧拉回路 ⇔ 连通且所有顶点度数为偶数
• 无向图有欧拉通路（非回路）⇔ 连通且恰有两个奇度顶点（起点终点为它们）
• 有向图有欧拉回路 ⇔ 连通且每点入度 = 出度

一笔画问题 = 找欧拉通路。奇度点为 0 可一笔画成圈，恰 2 个奇度点可从奇度点出发一笔画。

哈密顿图（重点）

概念	定义
哈密顿通路	经过每个顶点恰好一次的通路
哈密顿回路	经过每个顶点恰好一次并回到起点
哈密顿图	含哈密顿回路的图

• 必要条件：若图是哈密顿图，则删去任意 k 个顶点后连通分支数 ≤ k
• 充分条件：n≥3 的简单图，若每对不相邻顶点度数之和 ≥ n，则是哈密顿图
• 欧拉图与哈密顿图互不包含：欧拉看"边"、哈密顿看"顶点"

树（考点）

树的定义与性质

• 树：连通且无回路的无向图
• 等价定义：连通且边数 = 顶点数 − 1；无回路且边数 = 顶点数 − 1；任意两点间有唯一通路
• 树的性质：n 个顶点的树有 n−1 条边；树叶（度 1 顶点）至少 2 个（n≥2）

生成树与最小生成树

• 生成树：图的生成子图且为树（n 顶点连通图的生成树有 n−1 条边）
• 最小生成树：边权和最小的生成树

算法	思想	复杂度
Kruskal	按边权从小到大选边，不成环则加入（并查集）	O(E log E)
Prim	从某顶点出发，每次选连接已选集合的权最小边	O(V²) / 堆优化 O(E log V)

详细算法见 最小生成树。

根树

• 根树：一个有向/有根的树，一个根顶点 + 若干子树
• m 叉树：每个顶点至多 m 个孩子；二叉树最常用
• 二叉树遍历：先序（根左右）、中序（左根右）、后序（左右根）
• 正则二叉树：每个内部顶点恰有 2 个孩子。树叶数 = 内部顶点数 + 1

一句话总结

欧拉图判"边"（奇度顶点 0 或 2 个）、哈密顿图判"点"（条件多为充分）；树 = 连通 + n−1 条边；最小生成树用 Kruskal 或 Prim。

相关概念

• 最小生成树 — Kruskal/Prim 算法实现细节
• Dijkstra最短路径 — 图上的最短路算法
• 离散数学-集合与证明方法 — 树的递归定义
• 人工智能导论-智能机器人 — 路径规划中的图搜索