介绍图论进阶知识。

前言

由于笔者已在离散数学、电路理论和算法等课程中多次接触图论的基础知识，故在此不再赘述其基本概念，将其默认为前置知识。仅介绍拓展知识。

基本知识回顾

• 一般地，𝛿(𝐺)表示图𝐺的最小度，Δ(𝐺)表示最大度
• 导出子图：若𝑉(𝐺) ⊆ 𝑉(𝐺′)且 𝐸(𝐺) ⊆ 𝐸(𝐺′)，还有𝐸(𝐺) = 𝐸 (𝐺′) ∩ 则 𝐺是𝐺′的导出子图 (induced subgraph)
• 若还有𝑉(𝐺) = 𝑉(𝐺′)则 𝐺是𝐺′的生成子图(spanning subgraph)
• 如果图中所有顶点的度数都是一个常值𝑟，则称该图为𝑟-正则图(r-regular graph)
• 简单图(Simple graph)：没有自环和重边的无向图被称为简单图。
• 握手定理(Handshaking theorem, Leonhard Euler 1736)：给定无向图𝐺 = (𝑉, 𝐸) ，
  • 推论：无向图中，度数为奇数的点一定是有偶数多个

Graph: Isomorphism and Score

图同构(Graph isomorphism): 若对图𝐺= 𝑉, 𝐸以及图 G’=(V’, E’) 存在双射函数 ,满足对任意𝑥, 𝑦∈𝑉都有 当且仅当𝑓(𝑥), 𝑓(𝑦) ∈𝐸′ 那么 我们称图𝐺和图𝐺′是同构的｡

图的计数

• 𝑛个顶点的图的数量为 完全图边数 存在 or 不存在

• 任一图G=(V, E)至多与n!个 V 上不同的图同构 。基于此，可得到不等式
  $\frac{2^{\binom{n}{2}}}{n!} \leq x \leq 2^{\binom{n}{2}}$ 。

Graph Score

• 定义：那么图G的度序列就是图G的得分。
• 与图同构的关系：同构的图必然具有相同的得分.然而，具有相同得分的图并不一定同构
• 存在性：不是每一个有限序列都能作为图的得分。判断一个序列是否为图的得分可依据Score Theorem：设$D = (d_1, d_2, \ldots, d_n)$ 是自然数序列，n>1且 $d_1 \leq d_2 \leq \cdots \leq d_n$ ，D’是 $(d_1', d_2', \ldots, d_{n - 1}')$ 序列，其中 $d_{i}'=\begin{cases}d_{i}&\text{if }i < n - d_{n}\\d_{i}-1&\text{if }i \geq n - d_{n}\end{cases}$那么D是图得分当且仅当D’是图得分。
• 证明：
  • if：D’加点构造D
  • only if: D可转换为同构图，使得后个点连接,删除这些边得到D’

Applications of Handshake lemma

• Spernner’s lemma (Sperner, 1928):对任 意 n 维单形体(𝑛-simplex)进行分割并用𝑛+ 1 种颜色去着色,则任何合适的单形体分割 着色方案下,都必有一个包含所有不同颜 色的单元｡

• Planar Brouwer’s fixed point theorem: Every continuous function has a fixed point.

• 定理(Smith):对3-正则图,包含图上任意 边𝑒的哈密顿回路必有偶数条｡

Tree

树的刻画

• 树生长引理(Tree-growing lemma):对图𝐺 及图𝐺上的叶子结点𝑣而言,如下命题等价
  • G是树
  • G - v是树
• 树的等价刻画：
  • II. 路径唯一:对任意两点 u , ,存在从 u 到 v 的唯一 路径｡
  • III. 最小连通图: G 是连通图,且去掉任意一条边后都成 为非连通图｡
  • • IV. 最大无环图: G 不含环,但增加任何一条边所得到的 图 G+e (其中 )中含有一个环｡
  • V. Euler方程: G 是连通图,且 |V|=|E|+1

树的计数

两棵树𝑇, 𝑇′是“相等”的当且仅当树𝑇的边 集与树𝑇′的边集相等｡

Caley 定理

(Caley’s formula):𝑛个顶 点能构成的不同树一共有 种。

1. 核心命题：设为正整数，且它们的和为，那么在图（完全图，个顶点中任意两个顶点都有边相连）中，顶点的度数恰好为（）的生成树的数量等于 $$\frac{(n - 2)!}{(d_1 - 1)!(d_2 - 1)!\cdots(d_n - 1)!}$$
2. 证明过程
   • 基础情况：当 n = 1, 2时，该命题显然成立。因为 n = 1时，图中只有一个顶点，可看作一种特殊的树；n = 2时，只有一条边连接两个顶点，也只有一种树的形态，符合上述公式。
   • 归纳步骤（n > 2时）：因为 $d_1 + d_2 + \cdots + d_n = 2n - 2$ ，根据握手定理，必然存在某个i使得 $d_i = 1$ 不妨设 $d_n = 1$。对于 $1\leq i\leq n - 1$ ，定义$T_i$是$K_n$中包含边 $\{i, n\}$的生成树集合。从 $T_i$中的每棵树删除顶点$v_n$ ，得到 $T_i'$ ，$T_i'$是$K_{n - 1}$的生成树，且其顶点度数为 $d_1, d_2, \cdots, d_{i - 1}, d_i - 1, d_{i + 1}, \cdots, d_{n - 1}$
     • 根据归纳假设，可得到 $|T_i| = |T_i'| = \frac{(n - 3)!}{(d_1 - 1)!\cdots(d_{i - 1}-1)!(d_i - 2)!(d_{i + 1}-1)!\cdots(d_{n - 1}-1)!}$，进一步变形为 $|T_i| = \frac{(n - 3)!(d_i - 1)}{(d_1 - 1)!(d_2 - 1)!\cdots(d_{n - 1}-1)!}$
     • 由于 $|T|=\sum_{i = 1}^{n}|T_i|=\sum_{i = 1}^{n - 1}\frac{(n - 3)!(d_i - 1)}{(d_1 - 1)!(d_2 - 1)!\cdots(d_{n - 1}-1)!}$，再通过一系列数学变换，对所有满足$d_1 + d_2 + \cdots + d_n = 2n - 2$且$d_i\geq1$的$d_1, d_2, \cdots, d_n$ 进行求和，即 $\left|T\left(K_{n}\right)\right|=\sum_{\substack{d_{1}, d_{2}, \cdots, d_{n} \geq 1 \\ d_{1}+d_{2}+\cdots+d_{n}=2 n - 2}} \frac{(n - 2)!}{(d_{1}-1)!(d_{2}-1)!\cdots(d_{n}-1)!}$ 令$k_i = d_i - 1$，则$k_1 + k_2 + \cdots + k_n = n - 2$且$k_i\geq0$，此时式子变为 $\sum_{\substack{k_{1}+k_{2}+\cdots+k_{n}=n - 2 \\ k_{1}, \cdots, k_{n} \geq 0}} \frac{(n - 2)!}{k_{1}!k_{2}!\cdots k_{n}!}$，根据多项式定理，其结果等于 $\underbrace{(1 + 1+\cdots+1)^{n - 2}}_{n - 2}=n^{n - 2}$，从而证明了n个顶点构成不同树的数量为 $n^{n - 2}$ 。

Tree Isomorphism

有根树同构

定义： 𝑇, 𝑟 ≅′ (𝑇′, 𝑟′)：

• 𝑓: 𝑉(𝑇) → 𝑉(𝑇′) 是 𝑇 ≅ 𝑇′，
• 𝑓(𝑟) = 𝑟′
• ≅′ 关系严格地强于≅关系。

使用编码证明, $(T, r) \cong'(T', r')$ 当且仅当它们具有相同的编码｡

证明：
– 充分性：从有根树同构的定义和编码可证。
– 必要性：解码，从编码恢复原始的树结构。
任意有根树的编码必然有0𝑆1的一般形式，其中

$$𝑆 = 𝑆1𝑆2 … 𝑆𝑡$$

𝑆1是𝑆中0,1个数相等的最小前缀。𝑆2是第二个0,1平衡的最小前缀，等等。
可以据此恢复出有根树，且显然这样的有根树必然是同构的。

无根树同构

问题规约:一般树同构⊑有根树同构

• 距离(Distance):图 G 中的两 个顶点 u ,v,disc(1,1)表示 𝑢, 𝑣间最短路径的长度｡
• 偏心率(Excentricity):图𝐺及图中的顶点𝑣,偏心率定义为:

$$ex_{G}(v)=max _{u \in G} dis_{G}(u, v)$$

• 中心(Center):图𝐺中偏心率最小的顶点集合叫做中心｡ 用符号𝐶(𝐺)表示｡

性质：对树𝑇 = (𝑉, 𝐸)，𝐶(𝑇)至多含有2个顶点。且若𝐶(𝑇) = 𝑥, 𝑦 ，则 𝑥, 𝑦 ∈ 𝐸

𝐶(𝑇)中只含唯一顶点𝑣：输出有根树(𝑇, 𝑣)的编码 #(𝑻, 𝒗) 。
• 𝐶(T) = {𝑥1, 𝑥2}： 𝑒 = {𝑥1, 𝑥2}
𝑇 − 𝑒：必含有正好两个连通分支𝑇1, 𝑇2。不失一般性设𝑥1 ∈ 𝑉(𝑇1)，𝑥2 ∈ 𝑉(𝑇2)。

• 计算#(𝑇1, 𝑥1) 和#(𝑇2, 𝑥2)
• 如果#(𝑇1, 𝑥1) ≤ #(𝑇2, 𝑥2)，输出 #(𝑻, 𝒙𝟏)
• 否则，输出 # (𝑻, 𝒙𝟐)

之后按照有根树编码进行证明。