前言

暂时只介绍无向简单图（Non-Oriented Graph）

图的基本定义

图可被定义为一个二元组G=(V,E)，其中V是顶点集，E是边集，顶点可以被编码

图的分类

图的分类

按长相和形态分类：

• Path Graph（路径图）P_n：两端的顶点度数为1，中间顶点度数为2
• Cycle Graph（圈图）C_n：每个顶点的度数均为2

按“连接紧密程度”分：

• Complete Graph（完全图）K_n

按“顶点的阵营”划分

• Bipartite Graph（二分图/偶图）K_{m,n}：图中的顶点可被分为两个互不相交的集合（比如U与V），所有的边都必须是横跨U与V连接的

按“断连还是成环”分

• Tree（树）：连通且无环的图
• Forest（森林）：由若干互不相连的树组成

正则图

正则图即图中每一个顶点度数完全相同的图，图论中常称为r-正则图（r-regular graph）

• 0-正则图：空图（Null Grpah）N_n：只有顶点无边
• 1-正则图：配对（Matching）rK_2：两两顶点成对，r对顶点的不交并
• 3-正则图：比如著名的彼得森图（Peterson Graph）
• (n-1)正则图：完全图K_n

握手定理和特殊图的边/度数

握手定理（Handshake Lemma）指出：
::: align-center
在一个有n个顶点的无向图中，所有顶点的度数之和一定等于2e（其中e代表边的数量）
:::
考虑一个有n个顶点的无向图，每画一条边，这条边连接的两个顶点的度数均会+1，画完e条边后，总度数即为2e（偶数）

对于r-正则图，其每个顶点的度数均为r，故一个顶点树为n的正则图的总度数为nr，代入nr=2e可得其边数为\frac{nr}{2}

对于完全图K_n，其一定为n-1正则图，每个顶点的度数均为n-1，度数和为n(n-1)，则其边数可以得到为\frac{n(n-1)}{2}，也即C_n^2

对于二分图K_{m,n}，其一个顶点集中的m个顶点均连接到另一顶点集的n个顶点，边数为m\times n，度数为2mn

图的子图和补图

• 子图（Subgraph）：即新图的所有顶点和边都原封不动的来自原图，点可以少，边可以少
• 生成子图（Spanning Graph）：新图包含原图的所有顶点，但可以随意删除边
  诱导子图（Induced Subgraph）：先在原图中选出一部分顶点，然后强制要求把这些顶点在原图中的边全部保留
• 补图（Complement Graph）：新图\bar{G}和原图G的顶点完全一样，但对于任意两个顶点，原图有边，新图就绝对没边；原图没边，新图就必须连上。定点完全不变，边完全取反

若我们考虑一个无向图中所有顶点均与其他顶点有边，则此图为无向完全图K_n，其边数为\frac{n(n-1)}{2}，每个顶点的度数为n-1，故对于一个无向简单图，其与其补图之间存在以下关系

• 总可能边数：m(\bar{G})=\frac{n(n-1)}{2}-m(G)
• 同一顶点的度数：\deg_{\bar{G}}(v)=(n-1)-\deg_{G}(v)

图的度序列与Havel-Hakimi定理

图的度序列

对于一个具有n个顶点的图G，设其顶点的度数分别为d_1,d_2,\cdots,d_n，将其从小到大排序后得到的序列
::: align-center
(d_1,d_2,\cdots,d_n)
:::
就被称为图G的度序列

Havel-Hakimi定理

定义

一个非递增的正整数序列S=(d_1,d_2,\cdots,d_n)是某个简单图的度序列，当且仅当将序列的第一项d_1去掉，并将接下来的d_1个项每个都减1后得到的新序列S'也是某个简单图的度序列

使用Havel-Hakimi定理递归，我们能方便地判断某个序列是否是图的度序列，即这个序列是否能“画出图”

1. 排序：保证序列从大到小排列
2. “删老大”：删去第一个数d_1
3. “罚小弟”：把接下来的d_1个数每个都减1
4. 不断递归，如果在这之中出现负数，则此序列不是图的度序列，若最后序列内剩下的数为全0，则此序列是图的度序列

Havel-Hakimi图生成算法

Havel-Hakimi定理不只可以帮助我们判断一个已知序列是否为图的度序列，也可以在给定一个已知度序列时帮助我们画出图

1. 取度数最大的顶点v，其度数为d
2. 将v与后面的d个顶点各连一条边
3. 去掉v，将后面d个顶点的度数各减1
4. 重复上述步骤，直到所有顶点的度数为0

注意：Havel-Hakimi定理是判断序列是否是图序列的充要条件，但Havel-Hakimi图生成算法生成的图只是该度序列的一个代表，但并不是唯一的

Erdos-Gallai定理

一个非递增的正整数序列S=(d_1,d_2,\cdots,d_n)是某个简单图的度序列，当且仅当

1. 满足握手定理：\sum_{i=1}^n d_i是偶数
2. 对所有k=1,2,\cdots,n有
   \sum_{i=1}^k d_i\le k(k-1)+\sum_{i=k+1}^n\min(d_i,k)

Erdos-Gallai定理是另一种判断序列是否为图序列的工具，常被用于预筛非法序列，它与Havel-Hakimi定理是等价的

图的同构

定义

两个简单无向图G_1=(V_1,E_1)和G_2=(V_2,E_2)同构当且仅当存在一个双射函数f：
::: align-center
f: V_1\rightarrow V_2
:::
使得对于任意两个顶点u,v\in V_1，边(u,v)\in E_1当且仅当(f(u),f(v))\in E_2
即，两个图的“结构”完全一致，只是顶点的“名字”或“编号”不同

规范标号法

规范表号法（Canonical Labeling）可以便捷的判断两个图是否同构

1. 提取度序列并分类：得到两个图的度序列，并按度数大小进行分组。例如图G和图H的度序列都是(3,2,2,1)，二图具备同构的潜质，将其分位3度点（A类）、2度点（B类）、1度点（C类）
2. 固定锚点：强行规定某种映射规则，通常规定度最大的顶点标号为1。例如在图G中，度为3的顶点为a，则f(a)=1；在图H中，度为3的顶点为x，则f(x)=1
3. 贪婪扩展：从当前顶点出发，优先给度数大、或处于关键位置的邻居分配较小的标号。例如图G的a连接了b,c,d，其中b,c为2度点，d为1度点，则令f(b)=2,f(c)=3,f(d)=4，同理得到图H有映射f(y)=2,f(z)=3,f(w)=4
4. 验证邻接矩阵：在得到映射关系后写出二图的邻接矩阵，若二图在同一映射下的邻接矩阵完全相同，则二图同构

同构图的不变量

若G_1\cong G_2，则以下属性必须相同

• 顶点数|V_1|=|V_2|
• 边数|E_1|=|E_2|
• 度序列
• ....

图的同构不变量是判断图是否同构的必要条件

同构图补图的关系

两个图同构当且仅当它们的补图同构
::: align-center
G\cong H\Leftrightarrow \bar{G}\cong\bar{H}
:::

这个性质使得我们在判断较为复杂（比如边数较多）的图之间是否同构时，可以将其转换为判断相对简单的补图（边数为C_n^2-原边数）是否同构

给定顶点数的非同构简单图的枚举

1. 首先确定边数范围：k=0,1,2,\cdots,C_n^2
2. 利用补图的对称性，实际只需要枚举到k=\lfloor C_n^2/2 \rfloor
3. 对每个边数k，生成所有可能的度序列，使得生成的非递增度序列满足
   握手定理：\sum_{i=1}^n d_i=2k
   简单图约束：d_i\le n-1
   图序列条件：Havel-Hakimi定理或Erdos-Gallai定理
4. 对每个合法序列，使用Havel-Hakimi图生成算法构造一个简单图（注意，在n\ge 5时一个度序列可能对应多个非同构的图，此时需要使用其他方法处理）
5. 使用图的同构不变量对4中得到的所有图进行粗分组，不同组间的图一定不同构
6. 使用规范标号法对组内的同构图进行精筛去重，去重后得到的所有图均是不同构的
7. 利用补图的对称性质，对每个已枚举的图G，取其补图\bar{G}（当边数\lfloor C_n^2/2 \rfloor为整数时，其补图就等于自己），得到另一半边数的非同构图

以上方法只适用于n\le 6，当n>6时，手动暴力枚举已经不现实，需要采用其他方法迭代解决