Knowledge
图论知识点
用于复习图、连通性、欧拉图、哈密顿图、最短路径和最小生成树。
图与度数
图由顶点和边组成，所有顶点度数之和等于边数的两倍。
重要公式
- Σdeg(v)=2|E|
- |E(K_n)|=n(n-1)/2
常见考法
用握手定理判断图是否存在，计算边数和度数。
复习提示
- 看到所有顶点度数，优先检查度数和奇偶性。
易错提醒
度数和必须是偶数。
欧拉图与哈密顿图
欧拉图关注边是否能恰好走一次，哈密顿图关注顶点是否能恰好经过一次。
重要公式
- 无向连通图为欧拉图 ⇔ 每个顶点度数为偶数
常见考法
判断欧拉回路、哈密顿回路及其必要条件。
复习提示
- 题目说边选欧拉，题目说点选哈密顿。
易错提醒
欧拉条件和哈密顿条件不能互相替代。