どこにも流れないゼロの流れ

グラフ理論において、どこにもゼロがないフローまたはNZ フローは、どこにもゼロがないネットワーク フローです。これは、平面グラフの色付け と (双対性によって) 密接に関係しています。

G = ( V , E ) を有向グラフ、 M をアーベル群とする。写像φ : E → MがM循環であるとは、任意の頂点 v ∈ Vに対して

${\displaystyle \sum _{e\in \delta ^{+}(v)}\varphi (e)=\sum _{e\in \delta ^{-}(v)}\varphi (e),}$

ここで、δ ⁺ ( v ) はvからのエッジの集合を表し、δ ⁻ ( v ) はvへのエッジの集合を表します。この条件はキルヒホッフの法則と呼ばれることもあります。

φ ( e ) ≠ 0 であれば、 e ∈ E のいずれの e に対してもφ をゼロのないフロー、Mフロー、またはNZフローと呼ぶ。kが整数で0 < | φ ( e )| < kであれば、φ はkフローである。^[1]

G = ( V , E ) を無向グラフとする。E の向きがモジュラーkフローである場合、すべての頂点v  ∈  Vに対して 次が成り立つ。

${\displaystyle |\delta ^{+}(v)|\equiv |\delta ^{-}(v)|{\bmod {k}}.}$

• Mフローのセットは、1 つのエッジ上の 2 つのフローの合計が 0 になる可能性があるため、必ずしもグループを形成するわけではありません。

• (Tutte 1950) グラフGがMフローを持つ場合、かつその場合に限り、| M | フローを持つ。結果として、フローが存在するのは、 kフローが存在する場合のみである。^[1]結果として、G がkフローを許容する場合、 hフローも許容する(ただし ) 。${\displaystyle \mathbb {Z} _{k}}$${\displaystyle h\geq k}$

• 方向の独立性。グラフG上のどこにもゼロがないフローφ を変更するには、辺e を選択し、それを反転してから、φ ( e ) を − φ ( e ) に置き換えます。この調整後も、φ はどこにもゼロがないフローのままです。さらに、φ が元々kフローだった場合、結果のφもkフローになります。したがって、どこにもゼロがないMフローまたはどこにもゼロがないkフローの存在は、グラフの方向に依存しません。したがって、無向グラフGは、 Gの一部 (したがってすべての) の方向にそのようなフローがある場合、どこにもゼロがないMフローまたはどこにもゼロがないkフローを持つと言われます。

G上のMフローの数を とする。これは削除縮約公式を満たす: ^[1]${\displaystyle N_{M}(G)}$

${\displaystyle N_{M}(G)=N_{M}(G/e)-N_{M}(G\setminus e).}$

これを帰納法と組み合わせると、 が群Mの位数である多項式であることを示すことができます。 Gとアーベル群Mのフロー多項式と呼びます。 ${\displaystyle N_{M}(G)}$${\displaystyle |M|-1}$${\displaystyle |M|}$${\displaystyle N_{M}(G)}$

上記は、同じ位数の2つのグループには同じ数のNZフローがあることを意味します。位数は、Mの構造ではなく、唯一の重要なグループパラメータです。特に、${\displaystyle N_{M_{1}}(G)=N_{M_{2}}(G)}$${\displaystyle |M_{1}|=|M_{2}|.}$

上記の結果は、1953年にタットがフロー多項式の一般化であるタット多項式を研究していたときに証明されました。 ^[2]

ブリッジレス平面グラフのk面彩色とkフローの間には双対性がある。これを確認するには、Gを適切なk面彩色を持つ有向ブリッジレス平面グラフとし、色マップを構築する。 ${\displaystyle \{0,1,\ldots ,k-1\}.}$

${\displaystyle \phi :E(G)\to \{-(k-1),\ldots ,-1,0,1,\ldots ,k-1\}}$

次の規則によります。辺e の左側に色xの面があり、右側に色yの面がある場合、 φ ( e ) = x – yとします。すると、xとy は異なる色でなければならないため、φは (NZ) kフローになります。

したがって、GとG* が平面双対グラフであり、G*がk色可能（ Gの面の色付けが可能）である場合、G にはNZ kフローがあります。| E ( G )|の帰納法を使用して、Tutte は逆も真であることを証明しました。これは次のように簡潔に表現できます。^[1]

${\displaystyle \chi (G^{*})=\phi (G),}$

ここで、右辺はフロー数、つまりGがkフローを許容する最小のkです。

この双対性は一般的なMフローにも当てはまります。

• をMの値を持つ面彩色関数とします。${\displaystyle c}$

• r _1がeの左側の面、r _{2 が}右側の面であると定義します。${\displaystyle \phi _{c}(e)=c(r_{1})-c(r_{2})}$

• すべてのM循環に対して、次のような着色関数c が存在する(帰納法によって証明)。${\displaystyle \phi}$${\displaystyle \phi =\phi _{c}}$

• c は、 NZ Mフロー (単純) である場合に限り、| E ( G )| 面彩色です。${\displaystyle \phi _{c}}$

最後の 2 つの点を組み合わせると、双対性がわかります。 を特殊化することで、上で説明したkフローと同様の結果が得られます。 NZ フローと色付けの間にこの双対性があること、また任意のグラフ (平面グラフだけでなく) に対して NZ フローを定義できることから、これを使用して面色付けを非平面グラフに拡張できます。^[1]${\displaystyle M=\mathbb {Z} _{k}}$

• Gは、すべての頂点が偶数次である場合に限り、2面彩色可能である（NZ 2フローを考慮する）。^[1]

• をクライン4群とする。すると、3次グラフがKフローを持つのは、3辺彩色可能である場合のみである。系として、3辺彩色可能な3次グラフは4面彩色可能である。^[1]${\displaystyle K=\mathbb {Z} _{2}\times \mathbb {Z} _{2}}$

• グラフが 4 面彩色可能であるのは、NZ 4 フロー ( 4 色定理を参照) が許される場合のみです。ピーターセン グラフにはNZ 4 フローがないため、4 フロー予想が生まれました (以下を参照)。

• G が三角形分割である場合、すべての頂点の次数が偶数である場合にのみ、Gは 3-(頂点) 彩色可能です。最初の箇条書きにより、双対グラフG * は 2-彩色可能であり、したがって二部かつ平面立方体です。したがって、G * は NZ 3-フローを持ち、したがって 3-面彩色可能であり、G は3-頂点彩色可能です。^[1]

• ループ辺を持つグラフには適切な頂点彩色がないのと同様に、ブリッジを持つグラフには、任意のグループMに対して NZ Mフローが存在することはできません。逆に、ブリッジのないグラフには NZ フローが存在する(ロビンズの定理の一種)。^[3]${\displaystyle \mathbb {Z} }$

kの値が小さい場合に、どこにもゼロのないkフローを見つけようとすると、興味深い疑問が生じます。次のことが証明されています。

イェーガーの4フロー定理。すべての4辺連結グラフには4フローが存在する。^[4]

シーモアの6フロー定理。ブリッジのないグラフには必ず6フローが存在する。 ^[5]

2019年現在、以下の問題は未解決です（Tutteによる）。

3フロー予想。すべての4辺連結グラフには、どこにもゼロのない3フローが存在する。^[6]

4-フロー予想。ピーターセングラフをマイナーとして持たないブリッジレスグラフはすべて、どこにもゼロのない4-フローを持つ。^[7]

5フロー予想。ブリッジのないグラフには、どこにもゼロがない5フローが存在する。^[8]

4-フロー予想の逆は成り立たない。なぜなら、完全グラフ K ₁₁にはピーターセングラフと4-フローが含まれているからである。^[1]ピーターセンマイナーのないブリッジレス立方グラフの場合、スナーク定理(Seymour, et al 1998、未発表) により 4-フローが存在する。4色定理は、スナークは平面ではないという主張と同等である。^[1]

• 自転車スペース
• サイクル二重被覆予想
• 四色定理
• グラフの色付け
• エッジカラーリング
• トゥッテ多項式

• Zhang, Cun-Quan (1997)。グラフの整数フローとサイクルカバー。Chapman & Hall/CRC 純粋および応用数学シリーズ。Marcel Dekker, Inc. ISBN 9780824797904LCCN  96037152 。
• 張 存全 (2012)。回路図の二重カバー。ケンブリッジ大学出版局。ISBN 978-0-5212-8235-2。
• Jensen, TR; Toft, B. (1995)。「13 方向とフロー」。グラフの色付け問題。Wiley-Interscience の離散数学と最適化に関するシリーズ。pp . 209–219。ISBN 9780471028659。
• Jacobsen, Jesper Lykke; Salas, Jesús (2013). 「5フロー予想はほぼ誤りか?」. Journal of Combinatorial Theory . Series B. 103 (4): 532–565. arXiv : 1009.4062 . doi :10.1016/j.jctb.2013.06.001. MR  3071381. S2CID  41483928.