极图理论

⚠ 转载请注明出处：作者：ZobinHuang，更新日期：Jan.30 2022

    本作品由 ZobinHuang 采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。

目录

有特定需要的内容直接跳转到相关章节查看即可。

正在加载目录...

`l` 部图

基本定义

    若简单图 `G` 的点集 `V` 有一个划分:

`V=\bigcup_{i=1}^{l}V_i`, `V_i\cap\V_j=\emptyset`

且所有的 `V_i` 非空，`V_i` 内的点均不邻接，则称 `G` 是一个 `l` 部图 (l-partite Graph)。

    值得注意的是，一个 `l` 部图也可能是一个 `l+1` 部图。

完全 l 部图

    如果在一个 `l` 部图 `G` 中，任意部 `V_i` 中的每个顶点同 `G` 中其它各部中的每个顶点都相邻，则称 `G` 为 完全 `l` 部图 (Complete l-partite Graph)，记作 `G=K_{n_1,n_2,...,n_l}`, `(n_i=|V_i|, 1 \le i \le l)`。

Turán 图

    如果在一个 `n` 个点的完全 `l` 部图 `G` 中有:

`n=kl+r`, `0 \le r < l`
`|V_1|=|V_2|=...=|V_r|=k+1`
`|V_{r+1}|=|V_{r+2}|=...=|V_l|=k`

也即各个部的顶点个数差别不超过一个顶点时，称图 `G` 为 `n` 阶完全 `l` 几乎等部图 (Turán 图)，记为 `T_{l,n}`。

    `|V_1|=|V_2|=...=|V_l|` 的完全 `l` 几乎等部图称为 完全 `l` 等部图。

    下面我们给出关于 `l` 部图的一些定理:

连通二部图的 2 部划分是唯一的

    证明如下: 假设连通二部图的 2 部划分为 `V_1\capV_2=V`，则

    取 `v\inV_1`，由于 `G` 是连通图，所以对于任何 `u\inV_1\capV_2`，`G` 中都有连接 `u` 和 `v` 的路，因此 `d(u,v)` 是有定义的。

    因为任一条以 `v` 为起点的路交替经过 `V_1` 和 `V_2` 的点，因此点 `u\inV_2` 当且仅当 `d(u,v)` 为奇数。因此基于 `v` 点，我们只能把 `d(u,v)` 为奇数的点划分为一部，把 `d(u,v)` 为偶数的点划分为另一部。因此二部图的 2 部划分是唯一的。

`n` 阶完全二部图包含的边数最多为 `\lfloor \frac{n^2}{4} \rfloor`

    证明如下: 假设`n` 阶完全二部图的其中一部有 `k` 个顶点，则另一部有 `n-k` 个顶点，因此我们可以得到这个 `n` 阶完全二部图的边数为 `k\cdot(n-k)`，则通过不等式可知使得这个值最大的取法是 `k=\frac{n}{2}`，也即两边顶点数一样多时，此时图中的边数为 `\lfloor \frac{n^2}{4} \rfloor`。

不包含三角形 (triangle-free) 的 `n` 阶简单图包含的边数最多为 `\lfloor \frac{n^2}{4} \rfloor`.

    证明如下: 观察下图 `G` 的一条边 `e`，由于图中不存在三角形，因此对于与边 `e` 关联的点 `u` 和 `v` 来说，它们有关系: `d(u)+d(v) \le n` [1 式] ( i.e. `u` 和 `v` 二者不能有公共邻居，因此两个顶点的邻居个数加起来至多为 `n(G)` )。

    如果我们将图 `G` 中的所有边的 [1 式] 进行相加，换一个角度想，度为 `d(u)` 的顶点 `u` 被相加了 `d(u)` 次，因此我们得到: `\sum_{u\inV(G)}d^2(u) \le n \cdot m` [2 式]。

    由握手定理，有: `\sum_{u\inV(G)}d(u)=2\cdotm` [3 式]。

    对 [3 式] 两边平方，得 `(\sum_{u\inV(G)}d(u))^{2}=4\cdotm^2` [4 式]。

    由不等式可以化 [4 式] 为: `4m^2=(\sum_{u\inV}d(u)\cdot1)^{2} \leq n\cdot\sum_{u\inV}d^2(v) \leq n \cdot m \cdot n = n^2 \cdot m`。

    也即 `4m^2 \leq n^2m`，故 `m=\lfloor \frac{n^2}{4} \rfloor`。

`n` 阶 `l` 部图 `G` 有最多边数的充要条件是 `G \cong T_{l,n}`。

    这里略去证明。

图兰定理

度弱

    设 `G` 和 `H` 是两个 `n` 阶图，如果存在双射 `\mu`: `V(G)\rightarrowV(H)`，使得:

`\forall v \in V(G)`，有: `d_G(v) \le d_H(\mu(v))`

则称图 `G` 度弱于 (degree-minorized) 图 `H`，则一定有 `m(G) \le m(H)`，但是反过来并不成立。

    下面给出一个定理:

若 `n` 阶简单图 `G` 不包含 `K_{l+1}`，则 `G` 度弱于某个完全 `l` 部图 `H`，且若 `G` 具有与 `H` 相同的度序列，则 `G \cong H`。

图兰定理

若 `G` 是简单图，并且不包括 `K_{l+1}`，则 `m(G) \le m(T_{l,n})`。仅当 `G \cong T_{l,n}` 时，有 `m(G)=m(T_{l,n})`。

    下面我们使用归纳假设法对图兰定理进行证明。

    当 `l=1` 时，由于 `G` 不包括 `K_{l+1}=K_{2}`，因此图 `G` 是空图，显然结论 `m(G) = 0 \le m(T_{1,1}) = 0` 成立。

    假设结论对 “`G` 是一个不包含 `K_{l}` 的简单图” 的情况成立，然后我们假设 `G` 是一个不包含 `K_{l+1}` 的简单图。我们在 `G` 中选取一个最大度点 `x` (i.e. `d(x) = \Delta(G)`)，如下图所示，我们令 `X=N(x)`, `Y=V`\`X`。然后我们将 `E[G(X)]` 称为第 1 类边，将 `E[G(Y)]` 称为第 2 类边，将 `E[X,Y]` 称为第 3 类边，我们有: `|E(G)| = |E[G(X)]|+|E[X,Y]| + |E[G(Y)]|`。

    因为 `G` 不包含 `K_{l+1}`，所以可以断言 `G[X]` 不包含 `K_{l}` (如果包含了的话，由于 `x` 与 `G[X]` 中的边都相邻，所以 `G` 图将包含 `K_{l+1}`，与假设矛盾)。因此由归纳假设可以得到: `|E[G(X)]| \le |E(T_{l-1,\Delta})|`，等号成立当且仅当 `G[X] \cong T_{l-1,\Delta}`。

    注意到，与 `Y` 中顶点关联的边要么在 `E(X,Y)` 中，要么在 `G[Y]` 中。另一方面，`Y` 中有 `n-\Delta` 个顶点，每个顶点的最大度不超过 `\Delta`，因此有 `|E[G(Y)]| + |E[X,Y]| \le \Delta \cdot (n-\Delta)`。该式子等号成立的条件是 `G[Y]` 是空图且 `G[Y]` 中每个顶点的度都为 `\Delta`。

    基于这个等号成立条件，我们令以 `V(Y)` 为顶点的空图为 `G_{l}`，让以 `G_{l} \vee G[X]=H`，易得 `E|(G)| \le E(H)` (i.e. `|E(G)| = |E[G(X)]|+|E[X,Y]| + |E[G(Y)]| \le |E(H)| = |E(T_{l-1,\Delta})| + \Delta \cdot (n-\Delta)` )。由于 `H` 是一个完全 `l` 部图 为什么？，因此有 `|E(G)| \le |E(T_{l,\Delta})|`，等号成立当且仅当 `G \cong T_{l,\Delta}` (未理解)。

交图和团图

交图

    设 `S={x_1,x_2,...,x_m}` 是一个集合，`\F={S_1,S_2,...,S_n}` 是 `S` 的不同非空子集构成的族，它们的并是 `S`。定义集族 `\F` 的 交图 (Intersection Graph) `\Omega(\F)` 为: `V(\Omega(\F))=\F`，并且当 `i \ne j` 且 `S_i \cap S_j = \emptyset` 时，`S_i` 与 `S_j` 邻接。具体例子如上图所示。

    英文的注解 intersection_graph_wiki 可能更好理解一些：

    Formally, an intersection graph `G` is an undirected graph formed from a family of sets `S_i`, `i = 0, 1, 2, ...` by creating one vertex `v_i` for each set `S_i`, and connecting two vertices `v_i` and `v_j` by an edge whenever the corresponding two sets have a nonempty intersection, that is, `E(G) = { {vi, vj} | i \ne j, Si \cap Sj \ne \emptyset }`.

    如果存在集合 `S` 的一个集族 `\F`, 使 `G \cong \Omega(\F)`，则称图 `G` 是 `S` 上的一个交图。

    下面我们给出定理:

每个图都是交图。

    我们现在给出证明: 设 `G` 是任意一个图，`V(G)={v_1,v_2,...,v_n}`。我们令: `S=E(G)`。然后我们定义由 `S` 的若干元素组成的某些真子集定义为 `S_i={e|e 与 v_i 相关联}` (i.e. 与 `v_i` 关联的所有边的集合)，令这些 `S` 的真子集组成集族 `\F`，则可得 `G \cong \Omega(\F)` (i.e. 可以认为每个 `S_i` 其实就是一个顶点)，所以 `G` 是交图。

    现在我们给出另外一个概念: `G` 是 `S` 上的交图，如果 `S` 的基数最小 (含有的元素最少)，称 `S` 的基数为图 `G` 的 交数(Intersection Number)，记为 `\upsilon(G)`。

    确定给定图的交数是否不超过给定数 `k` 的问题是 NP-完全的。因此，计算一个给定图的交数是NP-困难的。

    然而交图的交数是图的一个拓扑不变量。下面是几个关于交数的结论：

`(n, m)` 连通图 `G` 的交数满足: `\upsilon(G) \le m(G)`。

若图 `G` 为 `n(n>3)` 阶连通图, 当且仅当 `G` 中没有三角形时, 有 `\upsilon(G) = m(G)`。

团图

    简单图 `G` 的一个 团(Clique) 是指 `V(G)` 中的一个子集 `V_1`, 使 `G[V_1]` 是完全图。

    我们定义没有其它的团 真包含 该团的团是 极大团。一个给定的图`G` 的 团图(Clique Graph) 是 `G` 的极大团的族构成的交图。

    团和团图的概念可以用如下例子来进行理解: