本笔记总结了 MATH1081 离散数学课程中图论部分的 Lecture 5.02（顶点度数与同构）和 Lecture 5.03（标准路径、欧拉通路与哈密顿通路）的核心概念、定理及其应用。

Lecture 5.02：顶点度数与同构 (Vertex Degree and Isomorphisms)

本讲座深入探讨了图的局部属性（顶点度数）和全局结构（图同构）。

1. 顶点度数 (Vertex Degrees)

1.1 顶点度数的定义

在一个（多重）图 G 中，任何顶点 v 的 度数 (Degree)，记作 deg(v)，是指它与 G 中多少条边 关联 (incident with) 的次数。

• 对于普通图 (Graph) G**：** 顶点的度数 deg(v) 就是与它关联的边的数量。每条边贡献1度。
• 对于多重图 (Multigraph) G**：** 顶点的度数是与它关联的边的数量，但环 (loops) 必须被计算两次。
  • 解释环算两次的原因： 想象一个环连接顶点 v。当你沿着这条环边走时，你从 v 出发，经过环又回到了 v。这条边在概念上“占用”了 v 的两个连接“槽位”，因为它既是“进入”也是“离开” v 的通道。

1.2 特殊度数的顶点

• 孤立顶点 (Isolated Vertex)：度数为 0 的顶点被称为 孤立顶点 (Isolated Vertex)。
  • 形象理解：就像一个社交圈里，这个人没有任何朋友，自己玩自己的。
• 悬挂顶点 (Pendant Vertex)：度数为 1 的顶点被称为 悬挂顶点 (Pendant Vertex)。
  • 形象理解：就像一串风铃，最末端只被一根绳子吊着的那一个。

1.3 特殊图的顶点度数示例

• 路径图 Pn：
  • 两个端点（首尾顶点）的度数都是1。
  • 中间所有顶点的度数都是2。
• 环图 Cn：
  • 所有顶点的度数都是2。
• 完全图 Kn：
  • 所有顶点的度数都是 n−1。因为每个顶点都与除了它自身以外的所有 n−1 个顶点相连。
• 完全二分图 Km,n：
  • V1 集合中的 m 个顶点的度数都是 n。
  • V2 集合中的 n 个顶点的度数都是 m。
• 立方图 Qn：
  • 所有顶点的度数都是 n。

1.4 正则图 (Regular Graphs)

• 定义：一个 正则（多重）图 (Regular (Multi)graph) 是指其所有顶点的度数都相同的（多重）图。
• 示例：
  • 环图 Cn：是2-正则图。
  • 完全图 Kn：是 (n−1)-正则图。
  • 完全二分图 Kn,n：是 n-正则图（当两个划分的大小相等时）。
  • 立方图 Qn：是 n-正则图。