Definition of Vertex Degree顶点度数的定义

In a (multi)graph G, the degree of a vertex v, denoted deg(v), is the number of edges incident with v.在一个（多重）图 G 中，任何顶点 v 的度数 (Degree)，记作 deg(v)，是指它与 G 中多少条边关联 (incident with) 的次数。

• For simple graphs:对于普通图： deg(v) equals the number of incident edges. Each edge contributes 1.顶点的度数 deg(v) 就是与它关联的边的数量。每条边贡献1度。
• For multigraphs:对于多重图： count incident edges, but loops count twice.顶点的度数是与它关联的边的数量，但环 (loops) 必须被计算两次。

正则图 (Regular Graphs)

一个正则（多重）图是指其所有顶点的度数都相同的（多重）图。

度数序列的定义

一个（多重）图的顶点度数序列是该图中所有顶点的度数按一定顺序（通常是递增或递减）排列的序列。

同构的定义

两个图 G 和 H 是同构 (Isomorphic) 的，记作 G ≃ H，当且仅当存在一个从 G 的顶点集到 H 的顶点集的双射函数 f: V(G) → V(H)，使得顶点之间的邻接关系被保留。

也就是说，对于 V(G) 中的所有顶点 v, w：

{v,w} ∈ E(G) 当且仅当 {f(v),f(w)} ∈ E(H)

图不变量的定义

图不变量是指图 G 的任何性质，该性质对于任何与 G 同构的图也成立。

核心思想：如果两个图在任何一个图不变量上不同，那么它们就肯定不是同构的。

路径的定义

在任何（多重）图 G 中，一个长度为 n 的路径 (Walk)是顶点 v_j ∈ V(G) 和边 e_i ∈ E(G) 的交替序列：

v₀, e₁, v₁, e₂, v₂, ..., v_n-1, e_n, v_n

序列中每对连续项都必须是关联的。路径的长度 n 等于它所包含的边的数量。

连通图的定义

一个（多重）图 G 是连通的，当且仅当对于 G 中的任何一对顶点 v_i, v_j ∈ V(G)，都存在一条从 v_i 到 v_j 的路径。

邻接矩阵的定义

对于任何有限的（多重）图 G 和其顶点的一个特定顺序 v₁, v₂, ..., v_n，它的邻接矩阵是一个 n×n 的矩阵 A。

其中每个 (i,j) 条目 a_i,j 是 G 中连接顶点 v_i 和 v_j 的边的数量。

更具限制性的路径概念

这些是比"路径 (Walk)"更具限制性的概念：

欧拉路径的定义

在一个连通的（多重）图 G 中：

• 一个欧拉小径 (Euler Trail)是一个小径，它恰好访问 G 的每条边一次
• 一个欧拉环路 (Euler Tour)是一个环路，它恰好访问 G 的每条边一次

哈密顿路径的定义

在一个连通的（多重）图 G 中：

• 一个哈密顿路径 (Hamilton Path)是一个路径，它恰好访问 G 的每个顶点一次
• 一个哈密顿圈 (Hamilton Cycle)是一个圈，它恰好访问 G 的每个顶点一次（除了起点和终点是同一个顶点）