查找圖中的'瓶頸邊緣'

給定一個隨機單向圖，我必須找到'瓶頸邊'來從一個頂點到另一個頂點。查找圖中的'瓶頸邊緣'

我所謂的「瓶頸邊緣」（！必須有一個更好的名字） - 假設我有以下的單一方向圖：

A 
/| \ 
B--C--D 
|  | 
E--F--G 
    \ |/
    H

爲了從A至H的獨立選擇的必須始終遍歷路徑邊緣BE和DG，因此造成「瓶頸」。

是否有一個多項式時間算法呢？

編輯：是的，這個名字是'我的意思是女巫的瓶頸'的'最低限度'。

來源

2011-04-27 Noros

HE HF和HG是否也被認爲是瓶頸？你有不同的定義嗎？ – 2011-04-27 21:19:31

這聽起來非常像[旅行推銷員問題]（http://en.wikipedia.org/wiki/Travelling_salesman_problem），只是用計算時間替換距離。與你的問題具體相關的是[瓶頸旅行推銷員問題]（http://en.wikipedia.org/wiki/Bottleneck_traveling_salesman_problem） – osknows 2011-04-27 21:24:44

你的意思是邊緣BE **或** DG必須總是遍歷？ – sawa 2011-04-28 12:19:56

聽起來就像你需要最小的切割，最小的一組邊緣去除將你的圖分成兩部分。

http://en.wikipedia.org/wiki/Minimum_cut

來源

2011-04-27 21:22:48 unbeli

這可能就是這樣。並使用最大流量=最小切:-) – 2011-04-27 21:23:14

謝謝，是的，最低限度它是！ :) – Noros 2011-04-28 20:05:22

你所尋找的是一個cut。給定一個圖，剪切是一組邊將頂點分割成兩個不相交的子集。

假設您試圖儘可能縮小切割範圍，這是經典的最小切割問題。這是Ford-fulkerson算法的僞代碼版本，針對您的案例進行了重新設計（無向圖，未加權圖）。我很確定它應該可以工作，但我不確定我是否在這裏最有效率/慣用。

reorganize your graph into a directed graph, 
    with two directed edges (u->v, v->u) for each original edge (u-v) 

while there is a path P from A to H: 
    (hint: use breadth first search to find paths - long story here) 
    //augment the path P: 
    for each edge (u->v) in P: 
    remove (u->v) from the graph and add (v->u) to it 
    (if v->u isn't there already) 

Label all vertices as reacheable or not reacheable from A. 

The bottleneck edges is the set of edges 
    that connect a reacheable and a unreacheable vertex

例如，你的情況BFS會給我們的路徑A-B-E-H。去除這些邊緣後，我們仍然能夠找到路徑A-D-G-H。在刪除這些邊之後，該圖被分割成可重新獲得的頂點{A，B，C，D}和不可更新的{E，F，G，H}。每個（B-E和D-G）集具有頂點的邊是瓶頸邊。

來源

2011-04-27 22:53:36 hugomg

我忘記了如果使用BFS可以讓我們直接刪除邊緣（在這個不加權的，無向的），而不是做所有的定向邊緣的東西。有人記得嗎？ – hugomg 2011-04-27 22:59:45

查找圖中的'瓶頸邊緣'

回答

相關問題