【图论笔记】权转移法（3）：第二个简单例子

---

目录

• 1. 搜索方法
• 2. 第二个简单例题
• 返回【图论笔记】

---

1. 搜索方法

我们这一节的任务不是用反证法证明一个现有的问题，而是展示如何使用权转移法搜索图族$\mathcal{G}$的不可回避集，从而制造一个定理出来．

假定我们讨论的是平面图的某个图族，使用三种常见的初始电荷设置方法，那么，搜索的步骤是这样的：

• (1) 任取图族$\mathcal{G}$中的一个图$G$；
• (2) 对$G$设置初始电荷量（若使用三种常见方法则总电荷量为负数）；
• (3) 采用一套放电规则对$G$放电；
• (4) 找到放电后无法得到非负电荷的所有构型，它们就是$\mathcal{G}$的不可回避集．

---

2. 第二个简单例题

下面我们任然以所有最小度为$5$的平面三角剖分图所构成的图族为例，记这个图族为$\mathcal{G}$．看一下在不一样的初始电荷量和放电规则的前提下，会搜索到什么样的不可回避集．

设$G\in \mathcal{G}$．对$G$设置初始电荷量$ch_0(G)$．令
$ch_0(x)=\left\{ \begin{aligned} & 2d(x)-6, & x\in V(G)\\ & d(x)-6, & x\in F(G) \end{aligned} \right.$

很明显，面的初始电荷量都是$-3$，而顶点的初始电荷量则都是正数，而且很大．在这种情况下，常用的思路是：保证顶点非负的前提下，让尽可能多的面非负．具体来说，一般的设计原则是：

富则平均分担，穷则精打细算．

比如，在我们现在这个情况中，顶点的度数越大，那么它的初始电荷量就越大．那么，我们可以形象地说，度数很大的顶点就像富裕的土豪，我们应该把他的财富尽可能平均地分摊出去．但是，==对于度数较小的顶点，我们则要精打细算，从而逼出我们所要找的构型．==这就要求我们首先分析一下，哪些顶点是“富人”，哪些顶点是“穷人”．

设$f$是一个面．由于$ch_0(f)=-3$，所以平均来看，$f$所关联的每个顶点至少要给$f$支付$1$个电荷．但是，如果我们要求某个顶点给它所关联的每个面$1$个电荷，那么只有这个顶点的度至少为$6$才能支付得起．所以，面对这个问题时，常规思路会以$6$为分界．度数大于等于$6$的顶点算“富人”，其电荷平均分配．度数为$5$的顶点算“穷人”，需要精打细算．

在这个原则之下，我们制定了如下的放电规则．

• 规则1. $6^+$-顶点将它的电荷平均分配给它所关联的所有面．
• 规则2. 设$v$是一个$5$-顶点，$f$是$v$所关联的一个面，那么
  • 如果$f$是一个$(7^+,5,7^+)$-面，那么$v$把$5/7$个电荷送给$f$；
  • 如果$f$是一个$(6^-,5,7^+)$-面，那么$v$把$13/14$个电荷送给$f$．

事实上，我们不难想到，如果一个$5$-顶点的$6^-$-邻点的个数多于$1$个，也就是放电规则没有列出的情况，那么，放电是无论如何也不可能克服这种情况的．这就是我们要找的不可回避的构型．

换句话说，即：如果平面三角剖分图$G$的最小度为$5$，那么$G$包含一条$(6^-,5,6^-)$-路．

实际上，在我们找到不可回避集的时候，我们也就找到了一条定理，同时找到了它的证明．如果这条定理的内容足够好的话，我们也就做出来了一篇论文．请大家自行把它的证明补充完整．

例题 如果平面三角剖分图$G$的最小度为$5$，那么$G$包含一条$(6^-,5,6^-)$-路．

这一节我们解释了权转移法的一个本质，那就是搜索某个图族的不可回避集．下一节，我们将换一个角度来理解权转移法．

---

• 返回【图论笔记】