ゴモリ・フー木

ゴモリ・フー木 (ゴモリ・フーぎ、英: 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 はゴモリ・フー木とよばれる。

参考文献

• 茨木, 永持 and 石井, グラフ理論―連結構造とその応用―, 朝倉書店, (2010)

関連項目

• カット
• 極点集合