|
ゴモリ・フー木 (英: 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) == 関連項目 == * カット * 極点集合 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ゴモリ・フー木」の詳細全文を読む スポンサード リンク
|