放電法

放電法（ほうでんほう、Discharging_method）とは、構造的なグラフ理論の補題を証明するために用いられる技法である。

解説

放電法は四色定理の証明において中心的な役割を果たしたことで最もよく知られている。放電法は、あるクラスのすべてのグラフが、指定されたリストからある部分グラフを含むことを証明するために用いられる。

最も一般的な放電は平面グラフに適用される。 最初に、グラフの各面と各頂点に「電荷」が割り当てられる。

電荷は小さな正の数になるように割り当てられる。放電フェーズでは、放電ルールの要求に応じて、各面や頂点の電荷を近傍の面や頂点に再分配することができる。しかし、各放電ルールは電荷の合計を維持する。ルールは、放電フェーズの後、正の電荷を持つ各面や頂点が望ましい部分グラフのいずれかに位置するように設計されている。電荷の和が正である以上、何らかの面や頂点が正の電荷を持たなければならない。多くの放電の引数は、いくつかの標準的な初期電荷関数のうちの1つを使用する（これらは以下にリストされている）。放電法をうまく適用するには、放電規則を創造的に設計する必要がある。

例

1904年、ヴェルニッケは放電法を導入して次の定理を証明したが、これは四色定理の証明の試みの一部であった。

定理:平面グラフが最小の次数 (グラフ理論)を持つ場合、そのグラフは辺を5個持つ。5である場合、端点がともに次数5であるか、または端点が次数5と6である。

証明: 頂点、面、辺の集合をそれぞれ$V$，$F$，$E$で表す。 辺の端点がともに次数5であるか、次数5と6であるものを「light」と呼ぶ。 グラフを平面に埋め込む。この定理を証明するためには、平面三角形分割だけを考えれば十分である（三角形分割で成り立つのであれば、ノードを削除して元のグラフに戻すとき、グラフの最小次数を5以下にすることなく、目的の辺の両側のノードを削除することはできないからである）。三角形分割になるまで、グラフに辺を任意に追加していく。元のグラフは最小次数5なので、新しい辺の各端点は少なくとも次数6を持つ。 だから、新しい辺はどれも軽い。したがって、三角形分割に軽い辺が含まれていれば、その辺は元のグラフにもあったはずである。

各頂点$v$に$6-d(v)$を、各面$f$に$6-2d(f)$を与え、ここで$d(x)$は頂点の次数と面の長さを表す。（グラフは三角形分割なので、各面の電荷は0である。）グラフのすべての次数の和は辺の数の2倍に等しいことを思い出してほしい。同様に、すべての面の長さの和は辺の数の2倍に等しい。平面グラフのオイラーの多面体定理を使えば、すべての電荷の和が12であることが簡単にわかる：

${\begin{aligned}\sum _{f\in F}6-2d(f)+\sum _{v\in V}6-d(v)=&\\6|F|-2(2|E|)+6|V|-2|E|=&\\6(|F|-|E|+|V|)=&&12.\end{aligned}}$

私たちが使う排出ルールは1つだけ：

• 次数5の各頂点は、各隣に1/5の電荷を与える。

どの頂点が最終的に正の電荷を持つかを考える。 正の初期電荷を持つ頂点は次数5の頂点だけである。 各次数5の頂点は各隣接に1/5の電荷を与える。 したがって、各頂点は最大でも$d(v)/5$の合計電荷を与えられる。 各頂点vの初期電荷は$6-d(v)$である。 したがって、各頂点の最終的な電荷はせいぜい$6-4d(v)/5$である。したがって、頂点が正の最終電荷を持つのは、次数が最大7である場合のみである。ここで、正の最終電荷を持つ各頂点が軽い辺の端点に隣接していることを示す。

頂点$v$が次数5または6で正の最終電荷を持つ場合、$v$は隣接する次数5の頂点$u$から電荷を受け取ったので、辺$uv$は軽い。頂点$v$が次数7で最終的に正の電荷を持つ場合、$v$は隣接する少なくとも6つの次数5の頂点から電荷を受け取ったことになる。グラフは三角形分割なので、$v$に隣接する頂点はサイクルを形成しなければならず、それは次数7しか持たないので、次数5の隣接頂点はすべて高次の頂点で区切られることはない。これがライトエッジとなる。