Minty 1960 の定理 3.1
Korte と Vygen の「組み合わせ最適化」を読んでいたら、突然以下のような補題が出てきました(以下は第二版 23 ページからの引用).
補題 2.6 (Minty [1960]) を有向グラフとし, とする. は黒で彩色され,残りの各辺は赤,黒あるいは緑のいずれかで彩色されているとする.このとき,以下の (a) あるいは (b) のいずれかが成立し,両方同時に成立することはない.
(a) を含み,赤と黒の辺だけからなる無向閉路で,黒い辺は全て同一の向きを持つようなものが存在する.
(b) を含み,緑と黒の辺からなる無向カットで,黒い辺はすべて同一の向きを持つようなものが存在する.
元論文では定理 3.1 に該当するものです.
正しいことは正しいのですが、果たしてこの命題にどれほどの意義があるのか、一見しただけではわかりませんでした.気になって元論文を調べてみたところ、単にその後の定理のために必要というのもありますが、なにやら電気回路中の電流の向きと関係があるようです.
こんなこといちいち調べてるから時間がなくなって忙しいんだなぁと思いました.