「辺分離定理」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: '【へんぶんりていり (edge splitting theorem)】 無向(有向)グラフにおいて1つの点$s$を選び, $s$に接続する2本の(有向)辺$(u,s),(s,v)$を1本の(...') |
|||
| 1行目: | 1行目: | ||
【へんぶんりていり (edge splitting theorem)】 | 【へんぶんりていり (edge splitting theorem)】 | ||
| − | 無向(有向)グラフにおいて1つの点 | + | 無向(有向)グラフにおいて1つの点<math>s\,</math>を選び, <math>s\,</math>に接続する2本の(有向)辺<math>(u,s),(s,v)\,</math>を1本の(有向)辺<math>(u,v)\,</math>に取り替える操作を辺分離という. このとき, <math>s\,</math>に接続する2本の辺をうまく選ぶと辺分離後も, グラフの辺連結度(正確には<math>s\,</math>以外の2点間の局所辺連結度の最小値)を変化させずに保つことができる.特に, 無向グラフに対しては(特殊な場合を除き), 辺分離後に<math>s\,</math>以外のすべての2点間の局所辺連結度を変化させない2本の辺の選択が存在する. |
2007年7月14日 (土) 14:11時点における版
【へんぶんりていり (edge splitting theorem)】
無向(有向)グラフにおいて1つの点を選び, に接続する2本の(有向)辺を1本の(有向)辺に取り替える操作を辺分離という. このとき, に接続する2本の辺をうまく選ぶと辺分離後も, グラフの辺連結度(正確には以外の2点間の局所辺連結度の最小値)を変化させずに保つことができる.特に, 無向グラフに対しては(特殊な場合を除き), 辺分離後に以外のすべての2点間の局所辺連結度を変化させない2本の辺の選択が存在する.
