極点集合

ウィキペディア

極点集合

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/07/31 22:00 UTC 版)

極点集合 (きょくてんしゅうごう、英: extreme vertex set) は、グラフ理論におけるカット構造の表現のひとつである。辺連結度増大問題を解くために導入された。重み付き無向グラフ G の頂点集合の空でない真部分集合 X のカットの重みより、X のすべての空でない真部分集合 Y のカットの重みが大きいとき、極点集合と呼ばれる。G のすべての極点集合の族はラミナ族である。

アルゴリズム的側面

G のすべての極点集合の族は最小次数順序と呼ばれるグラフの順序付けを用いて算出される。

応用

• 辺連結度増大問題： G の辺連結度を目標値 k に増大させるために必要な、最小サイズの付加辺集合を算出する問題。
• 最小k-部分分割問題： G の頂点集合を k 個に分割したとき、 k 個のカットの重み総和を最小化する問題。
• 最小k-カット問題

参考文献

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

関連項目

• カット
• ゴモリ・フー木