About: ゴモリ・フー木

ゴモリ・フー木 (ゴモリ・フーぎ、英: Gomory-Hu tree) は、グラフ理論におけるカット構造の表現のひとつである。 同一の頂点集合 V を持つ 2 個の重み付き無向グラフ G と H が与えられたとき、V に属する任意の 2 点 u と v に対して、 H における u, v 間の局所辺連結度と G における u, v 間の局所辺連結度が等しいとき、 H は G にフロー同等とよばれる。 G にフロー同等な木 T において、 T から辺 e を除去して分かれる連結成分を A と B とする。 T の任意の辺 e に対して、 A のカットの重みと B のカットの重みが等しいとき、 T はゴモリ・フー木とよばれる。