グラフ理論において、グラフ G(V, E) の頂点 V の 2 分割 (S, T) をカット（英: Cut）とよぶ。 このとき、ある辺 (u,v) ∈ {\displaystyle \in } E の端点が u ∈ {\displaystyle \in } S かつ v ∈ {\displaystyle \in } T（有向グラフの場合 u ∈ {\displaystyle \in } T でかつ v ∈ {\displaystyle \in } S の場合もある）であるとき、この辺を「カットエッジ」と呼ぶ。
グラフ理論において、グラフ G(V, E) の頂点 V の 2 分割 (S, T) をカット（英: Cut）とよぶ。 このとき、ある辺 (u,v) ∈ {\displaystyle \in } E の端点が u ∈ {\displaystyle \in } S かつ v ∈ {\displaystyle \in } T（有向グラフの場合 u ∈ {\displaystyle \in } T でかつ v ∈ {\displaystyle \in } S の場合もある）であるとき、この辺を「カットエッジ」と呼ぶ。
出典: Wikipedia「カット (グラフ理論)」 · CC BY-SA 4.0
この記事を共有: X · Bluesky