辺分離定理

提供: ORWiki
2007年7月13日 (金) 11:24時点における122.17.2.240 (トーク)による版 (新しいページ: '【へんぶんりていり (edge splitting theorem)】 無向(有向)グラフにおいて1つの点$s$を選び, $s$に接続する2本の(有向)辺$(u,s),(s,v)$を1本の(...')
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

【へんぶんりていり (edge splitting theorem)】

無向(有向)グラフにおいて1つの点$s$を選び, $s$に接続する2本の(有向)辺$(u,s),(s,v)$を1本の(有向)辺$(u,v)$に取り替える操作を辺分離という. このとき, $s$に接続する2本の辺をうまく選ぶと辺分離後も, グラフの辺連結度(正確には$s$以外の2点間の局所辺連結度の最小値)を変化させずに保つことができる.特に, 無向グラフに対しては(特殊な場合を除き), 辺分離後に$s$以外のすべての2点間の局所辺連結度を変化させない2本の辺の選択が存在する.