前言

暂时只介绍无向简单图（Non-Oriented Graph），无向、无自环、无重边

图的基本定义

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

图的分类

图的分类

按长相和形态分类：

• 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（树）：连通且无环的图，e=n-1*
• Forest（森林）：由若干互不相连的树组成

正则图

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

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

超立方体图

超立方体图Q_m是一类图，它的前几维的表示分别是：

1. Q_1：一维立方体，一条线段。此时只有一个坐标轴，两个端点，用二进制表示为0（左）和1（右）
2. Q_2：二立方体，一个正方形。两个坐标轴，2位二进制数表示（00，01，10，1 1）
3. Q_3：一个正方体，3位二进制表示
4. ...

Q_m的顶点数为2^m（对应m位2进制向量的取值数）

同时Q_m是m-正则图，首先明确在Q_m的二进制表示中，一个顶点于另一个顶点相邻的条件为当且仅当两个顶点的表示中仅有一位不同。所以对于一个确定的顶点（m位二进制），其相邻顶点有m个（将这个顶点的二进制表示任意挑选一位进行修改），故这个顶点的度为m，由任意性得Q_m是m-正则图

由正则图的边公式得到Q_m的边数为m2^{m-1}

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

握手定理（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定理

一些符号

图的最大度常用\Delta(G)表示，最小度常用\delta(G)表示

图的度序列

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

1. d_i非负
2. d_i\le n-1
3. 满足握手定理\sum d_i=2e（偶数）

取逆否命题后，这些性质可以用于判断一个序列是否不是图序列

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时，手动暴力枚举已经不现实，需要采用其他方法迭代解决

自补图及其性质

自补图即\bar{G}=G

一个有n个顶点的自补图有以下性质：

1. e(G)=\frac{1}{2}e(K_n)=\frac{n(n-1)}{4}
2. 将1进行变换，容易得到顶点数n一定为4k或4k+1（因为n与n-1一定互质）

图的连通性

一些概念

图内的路径的类型可以分为四种：

1. 路（Walk）：沿着边一段一段走下去，只要相邻两步能接上就行

• 可以重复顶点
• 可以重复边
• 只要求走的顺序是合法的

2. 迹（Trail）：不允许重复边

• 顶点可以重复
• 边不能重复，每条边都只走一次
• 闭迹（Circuit）：迹+起点=终点（v_0=v_k）且长度\ge 1

3. 径（Path）：不允许重复顶点

• 顶点（也包括边）都不允许重复

4. 环（Cycle）：“首尾回到同一点”的特殊 Path 型结构

如果一条边e删掉以后，图变得不连通，那么e称为这个图G的一个桥（Bridge）

边连通度和点连通度

图的边连通度\lambda(G)表示最少删多少条边，图会断开，对于常见的图有：

• \lambda(P_n)=1
• \lambda(C_n)=2
• \lambda(K_n)=n-1
• \lambda(K_{s,t})=\min\{s,t\}

对应地最小的影响图连通性的边集称为边割集（Edge Cutset）A

图的点连通度\kappa(G)表示最少删多少个顶点，图会断开，对于常见的图有：

• \kappa(P_n)=1(n\ge 3)
• \kappa(C_n)=2
• \kappa(n)=n-1
• \kappa(K_{s,t})=\min\{s,t\}

若删去一个顶点图的连通性改变，则该点称为割点（Cut Vertex）

点连通度、边连通度和最小度的关系

::: align-center
\kappa(G)\le \lambda(G)\le \delta(G)
:::

• \lambda(G)\le \delta(G)： 在图中最小度数的顶点度数为\delta(G)，将其所有的边删去图的连通性一定改变，故边连通性\lambda(G)不会超过\delta(G)
• \kappa(G)\le \lambda(G)：若删掉一些边可以改变图的连通性，则删掉这些关键边上的顶点往往会“更快”改变图的连通性

几种常见图的连通性

1. 树：树的每条边都是桥，只要n\ge 2一定有\lambda(T)=1，内部顶点通常是割点
2. 环C_n：无桥无割点，\lambda(C_n)=\kappa(C_n)=2
3. 完全图K_n：\lambda(K_n)=\kappa(C_n)=\delta(C_n)=n-1

Ramsey理论与图染色问题

Ramsey理论指出：
::: align-center
在任何足够大的结构中必然存在给定大小的规律性子结构
:::
该理论旨在回答"需要多大混沌才能确保特定秩序存在"的数学问题
在图论中，一类问题是图的染色问题，考虑给K_n的每条边染色（红/蓝），因为在K_n里每一对点之间一定有一条边，所以每对点要么全为蓝色，要么全为红色。我们将“染红色边的部分”看作图G，则染蓝色边的部分就可看作图\bar{G}

一个经典的理论是：
::: align-center
任意给K_6的边染红蓝两色，一定出现红三角形或蓝三角形
:::
也即K_3一定存在于K_6的某个任意子图或它的补图里（或二者均），使用拉姆齐理论，可以用拉姆齐数描述为R(3,3)=6（或R(3)=6）

证明：
在K_6内任取一个顶点a，它与其他5个顶点间均有一条边，每条边只可能有两种颜色，由鸽巢原理，5条边分配2种颜色，至少有3条边为同一种颜色（假设为红色），假设这三条边连向顶点u,v,w。现在检查u,v,w之间的边uv,uw,vw的颜色

• 若三条边中有至少有一条为红色（假设为uv），则这条边的两个顶点+顶点a一定构成红色K_3
• 若三条边全为蓝色，则u,v,w构成蓝色K_3

证毕

而要证明R(3,3)=6，还需要证明比6小的情况不可能出现。考虑K_5中的一个反例：取其子图C_5，其中没有K_3，而C_5是自补图，其补图是自身，也没有K_3，故R(3,3)=6

欧拉图

欧拉回路与欧拉通路

欧拉回路（Euler circuit）：表示为起点和终点是同一个点，访问完所有边刚好绕一圈回到出发的位置
欧拉通路（Euler trail）：表示为起点和终点不是同一个点，访问完所有边但不用/无法回到出发的位置
欧拉图：存在欧拉回路的图

欧拉定理

欧拉定理指出：
一：
::: align-center
连通图G是欧拉图（存在欧拉回路）当且仅当G中没有奇度点
:::
二：
::: align-center
连通图G存在欧拉通路但不存在欧拉回路当且仅当G中恰好有2个奇度点
:::
三：
::: align-center
若连通图G存在两个以上奇度点，则G既不存在欧拉回路又不存在欧拉通路
:::

Fleury算法

Fleury算法给出了对于一个满足欧拉条件的连通图，如何实际构造出一条欧拉回路或欧拉通路的方法

1. 确认条件：图连通且满足欧拉定理（奇度点数为0或2）
2. 确认起点：若为全偶度图（存在欧拉回路），则可任选起点；如果恰好存在2个奇度点（存在欧拉通路），则必须选其中一个奇度点作起点
3. 从当前点开始走，对于连接这个点的一条候选边e

• 如果e是桥：则不优先考虑走
• 如果e是非桥，则考虑优先走e

4. 重复3直到走完所有的边
5. 检查三条规律：

• 连续性：每一步的两个相邻顶点之间，原图里一定有边
• 边不重复：每条边只出现了一次
• 边全用完

6. 检查起点和终点：如果起点=终点（首尾重合）则为欧拉回路；如果起点\ne终点则为欧拉通路

中国邮递员问题

想象你是邮递员，负责一条片区的每一条街。你从邮局出发，必须把每条街至少走一遍，最后回到邮局。问：最短走多少路？

在无向图中，由握手定理推论，奇度点必须成对出现，所以针对中国邮递员问题（Chinese Postman Problem, CPP）的图可以分为两类

• 全偶度图（0个奇度点）
• 有2k个奇度点（k\ge 1）

当图为全偶度图（欧拉图）时，其一定存在欧拉回路，所有顶点均会经过且每一条边走且只走一次，又因为欧拉图上任何一条欧拉回路的总长度都等于所有边的权重之和，故“最短路”们的路程都是相同的，使用Fleury算法可以直接得到答案

当图有2k个奇度点时，事情便起变化了，因为对于每一个经过的顶点，我们必须要求“有进有出”，而对于奇度点来说，在每一条边至少走一次的约束下，必然存在一条边无法再和其他边进行配对（要么进没法出，要么出没法进，在其他边都用过了的前提下），所以一些边必须走第二遍，于是问题变为
::: align-center
把2k个奇度点两两配对，每对之间的连接代价等同于两点在原图上的最短路径长度，求总和最小的配对方案
:::

1. 找全图所有奇度顶点
2. 在这2k个点之间，计算每对(i,j)的最短路径
3. 做最小权完美匹配
4. 对每一对匹配到的(i,j)，将i\to j的最短路径上每条边的权重\times 2
5. 现在的新图所有顶点均为偶度，问题变为寻找欧拉回路

图的边覆盖问题*

找到一组迹，使得每条边恰好出现在某一条迹中（覆盖所有边），并且迹的总条数最小

同样地，当图不存在奇度顶点时，1条欧拉回路（封闭迹）即可覆盖所有的边。如果奇度顶点数>0，则必然会出现非封闭迹，由于每条非封闭迹都会“消耗”两个奇度顶点作为其端点，所以至少需要\text{奇度顶点数}/2条封闭迹才能把所有奇度顶点“用完”

图的最短路径

此部分设计Djikstra和Floyd-Warshall算法，不再阐述

哈密顿图

Hamiltonian路径与Hamiltonian回路

哈密顿路径：要求所有顶点都恰好访问一次（推论：所有顶点的度数至少\ge 2）
哈密顿回路：要求所有顶点都恰好访问一次，且最后回到起点

狄拉克定理

Dirac定理指出：如果G是一个n\ge 3的简单图，若其最小度\delta (G)\ge\frac{n}{2}，则G是哈密顿图

奥雷定理

奥雷定理（Ore's Theorem）是Dirac定理的推广，它指出如果G是一个n\ge 3的简单图，对任意两个不相邻的顶点u和v，都有
::: align-center
\deg(u)+\deg(v)\ge n
:::
那么G是哈密顿图（存在哈密顿回路）

狄拉克定理

狄拉克定理（Dirac Theorem）指出，若图有n\ge 3个顶点，且每个顶点度数\ge\frac{n}{2}，则此图为哈密顿图

图的平面性

图的平面图示、平面图和围长

图的平面图示（Plane Diagram）：在图的图示中边仅在顶点处相交
平面图（Planar Graph）：存在平面图示的图
外平面图（Outerplanar Graph）：所有顶点属于同一个面的图
围长（Girth）：图中最短圈的长度

图的面

一般我们将图画在平面上时有一个“讨厌”的事情：“总感觉外面和里面不一样”，就比如一个三角形K_3将平面分为外内两个部分，但我们总觉得外面不一样，因为外面延伸到无限远

为了解决这个问题，我们可以想象将图画在球面上，如此，“外面”便不再延伸至无限远

在有了球面视角后，我们想象把图钉在球面上，边像橡皮筋一样贴着表面拉紧。这些橡皮筋把球面切成了几块，每一块就叫做图的一个面（Face）

欧拉公式

欧拉公式告诉我们，对一个连通图的任意平面嵌入（有N个顶点、E条边、F个面），总有
::: align-center
N-E+F=2
:::
若图非连通，有推广版本：
::: align-center
N-E+F=1+C
:::
其中C为连通分支数

例如：

这个图有6个顶点，8条边，4个面，满足了欧拉公式

欧拉公式的推论

对于简单平面图，如果其是连通的。我们考虑每个面至少由3条边围成，所以所有面的边数总和\ge 3F，而每条边最多属于2个面，所以所有面的边数总和\le 2E，所以得3F\le 2E，代入欧拉公式得：
::: align-center
E\le 3N-6
:::
此推论经常被用于快速证明图是否不是平面图，如果此不等式不满足，则该一定不是平面图；但反之，如果满足此不等式，图不一定是平面图（例如，彼得森图）

外平面图的边数上界

对于任意n\ge 3的外平面图，其边数一定满足
::: align-center
e\le 2n-3
:::

库拉托夫斯基定理（Kuratowski's Theorem）

拓扑版本：

一个图是平面图，当且仅当它不包含任何同胚（Homeomorphic）于K_{3,3}或K_5的子图

收缩版本：

一个图是平面图，当且仅当它不包含任何可收缩（Contractible）于K_{3,3}或K_5的子图

图的着色

图的顶点着色

给简单图的每个顶点分配颜色，要求相邻顶点（有边相邻的顶点）颜色不同。若图G能用恰好k种颜色完成上述着色，则称G是k-可着色的，其色数\chi(G)表述为：满足G是k-可着色，但不是(k-1)$-可着色的最小正整数k

常见的几种图的顶点色数为：
完全图K_n：\chi(G)=n，因为所有顶点都两两相邻
完全二分图K_{s,t}：\chi(G)=2，因为组内无连接，组间两两相连
超立方体图Q_m：\chi(G)=2，为二分图，将顶点按二进制表示各位和的奇偶分为两组，每一组分配一种颜色即可合法着色
树：\chi(G)=2，按层数奇偶分为两组，层内无边，层间有边，每一组分配一种颜色即可合法着色
偶环C_{2n}：\chi(G)=2，为二分图，按环中位置的奇偶分为两组，每一组分配一种颜色即可合法着色
奇环C_{2n+1}：\chi(G)=3，不是二分图，按环中位置奇偶分为两组，最后一个顶点在着色时其颜色一定会与第一个顶点颜色相同，故需要额外一种颜色
彼得森图：不是二分图，\chi(G)=3

图的边着色

与顶点着色类似，色数定义为\chi'(G)

对于任意图G，其色数满足Vizing定理
::: align-center
\Delta\le\chi'(G)\le\Delta +1
:::
其中\Delta是图的最大度

Vizing定理告诉我们一个图的边着色数只可能取两个值：\Delta或\Delta+1，我们按照取值将其分为两种图：

1. Class I图：色数\Delta
2. Class II图：色数\Delta +1

特例：所有二分图都是Class I图

常见图的边着色数为：
偶环C_{2n}：\chi'(G)=2
奇环C_{2n+1}：\chi'(G)=3
完全二分图K_{s,t}：\chi'(G)=\max(s,t)
偶完全图K_{2n}：\chi'(G)=2n-1，属于Class I图
奇完全图K_{2n+1}：\chi'(G)=2n+1，属于Class II图
彼得森图：\chi'(G)=4