放電法 (数学)
放電法（ほうでんほう、Discharging_method）とは、構造的なグラフ理論の補題を証明するために用いられる技法である[1]。
解説
放電法は四色定理の証明において中心的な役割を果たしたことで最もよく知られている。放電法は、あるクラスのすべてのグラフが、指定されたリストからある部分グラフを含むことを証明するために用いられる[1]。
最も一般的な放電は平面グラフに適用される。 最初に、グラフの各面と各頂点に「電荷」が割り当てられる。
電荷は小さな正の数になるように割り当てられる。放電フェーズでは、放電ルールの要求に応じて、各面や頂点の電荷を近傍の面や頂点に再分配することができる。しかし、各放電ルールは電荷の合計を維持する。ルールは、放電フェーズの後、正の電荷を持つ各面や頂点が望ましい部分グラフのいずれかに位置するように設計されている。電荷の和が正である以上、何らかの面や頂点が正の電荷を持たなければならない。多くの放電の引数は、いくつかの標準的な初期電荷関数のうちの1つを使用する（これらは以下にリストされている）。放電法をうまく適用するには、放電規則を創造的に設計する必要がある。
例
1904年、ヴェルニッケは放電法を導入して次の定理を証明したが、これは四色定理の証明の試みの一部であった。
定理:平面グラフが最小の次数 (グラフ理論)を持つ場合、そのグラフは辺を5個持つ。5である場合、端点がともに次数5であるか、または端点が次数5と6である。
証明:
頂点、面、辺の集合をそれぞれ
- 放電法 (数学)のページへのリンク
