【图论笔记】权转移法（2）：初始电荷量和放电规则

目录

1. 初始电荷量

设P\mathcal{P}是全体可平面图构成的图族．权转移法通常在这个图族的某个子族上实施．

注意：可平面图和平面图是不同的两个概念：存在平面嵌入的图是可平面图；固定可平面图的一个平面嵌入，从而得到的一个拓扑图是平面图。一言以蔽之，可平面图仍然是抽象的图，但平面图是平面的一个拓扑子空间。

设G\mathcal{G}是P\mathcal{P}的一个子族．再设G∈GG\in \mathcal{G}．固定图GG在欧氏平面上的一个平面嵌入．下面的问题是如何在GG上设置初始电荷量ch0(⋅)ch_0(\cdot)．

初始电荷量的常见设置方法有三种，即顶点充电法、面充电法和均衡充电法．

顶点充电法的初始电荷量的设置如下：
ch0(x)={2d(x)−6,x∈V(G)d(x)−6,x∈F(G).ch_0(x)=\left\{ \begin{aligned} &2d(x)-6, & x&\in V(G)\\ &d(x)-6, & x&\in F(G). \end{aligned} \right.

使用欧拉公式可以算出，在顶点充电法之下，GG的初始电荷量的总和为
∑x∈V(G)∪F(G)ch0(x)=4e(G)−6v(G)+2e(G)−6f(G)=−12<0.\sum_{x\in V(G)\cup F(G)}ch_0(x)=4e(G)-6v(G)+2e(G)-6f(G)=-12<0.

面充电法的初始电荷量的设置如下：
ch0(x)={d(x)−6,x∈V(G)2d(x)−6,x∈F(G).ch_0(x)=\left\{ \begin{aligned} &d(x)-6, & x&\in V(G)\\ &2d(x)-6, & x&\in F(G). \end{aligned} \right.

使用欧拉公式很容易算出，在面充电法之下，GG的初始电荷量的总和为
∑x∈V(G)∪F(G)ch0(x)=2e(G)−6v(G)+4e(G)−6f(G)=−12<0.\sum_{x\in V(G)\cup F(G)}ch_0(x)=2e(G)-6v(G)+4e(G)-6f(G)=-12<0.

均衡充电法的初始电荷量的设置如下：
ch0(x)=d(x)−4,   x∈V(G)∪F(G).ch_0(x)=d(x)-4,~~~x\in V(G)\cup F(G).

再次使用欧拉公式可得，GG在均衡充电法下的初始电荷量的总和为
∑x∈V(G)∪F(G)ch0(x)=2e(G)−4v(G)+2e(G)−4f(G)=−8<0.\sum_{x\in V(G)\cup F(G)}ch_0(x)=2e(G)-4v(G)+2e(G)-4f(G)=-8<0.

在三种常见的充电法里，初始电荷量的总和都是负．所以如果在某组放电规则下放电之后，出现每个顶点和每个面的电荷量都是非负，那么一定存在某个矛盾．

也就是说：图GG原本没有某个性质或结构，但是我们假定它有，结果导致了矛盾．实际上，【权转移法(0)】中的例题就是这样证明的．

2. 放电规则

那么如何设计放电规则呢？

这就是一件很艺术的事情了．一般原则上是就近放电，但并不绝对．

事实上，正是由于放电规则设计的不同（以及初始电荷量的不同），导致了我们能够借助权转移法，找到不同的不可回避集．

而恰恰是这些不同的不可回避集，能在不同的图论问题中起到关键的作用．

下一节我们将给出第二个简单例子，来看一下：变更初始电荷量和放电规则可以给我们带来什么．