ニュースのまとめ

グラフ理論におけるカットは、グラフの頂点を2つの部分集合に分割することである。G(V, E) がグラフを表すとする。カットとは、頂点の集合 V を2つの集合 S と T に分割することを指す。任意のエッジ (u,v) $\backslash in$ E について u $\backslash in$ S でかつ v $\backslash in$ T（有向グラフの場合 u $\backslash in$ T でかつ v $\backslash in$ S の場合もある）のとき、このエッジを「カットをまたいでいる」あるいは「カットエッジ」と呼ぶ。
「カットの大きさ」は、カットをまたいでいるエッジの総数で表される。重み付けされたグラフでは、カットの大きさはカットをまたいでいるエッジの重み付けの総和で定義される。フローネットワークでは、カットの大きさは始点側から終点側へ向かうエッジの重み付けの総和で定義される（逆方向のエッジは加算されない）。