切入加權無向連通圖

背景：我是圖論的新手，特別是在「圖切」中。請不要太技術和快速。謝謝。
假設我有一個加權無向連通圖G =（V，E）。我有一個變量A，它包含一個整數值，我想從圖G的權重低於A的值中刪除/切割所有邊。
問題1：如果這已經存在於圖論中（我看到max-cut ，min-cut，st cut等），它叫什麼名字？
問題2：如何使用數學符號正式表達/定義此方法。
謝謝你的建議。切入加權無向連通圖

來源

2015-07-28 george24

你說的「刪除/切」是什麼意思？ – MrGreen

@MrGreen我的意思是「刪除」邊緣。 – george24

您有：

一個圖形G
一組頂點V
和邊組成E這是一組頂點對（即E = {{x,y} : x ∈ V, y ∈ V}）。
每條邊都有一個權重（假定爲自然數），您可以使用函數（即∀ e ∈ E : weight(e) ∈ ℕ）指定權重。

然後圖形G'與重量除去的邊緣不小於a：由下式給出（注單數元素/值通常使用小寫而集列表/等使用大寫通常表示爲/表示）：

G' = (V, { e ∈ E : weight(e) ≥ a })
或G' = (V,E') : E' = { e ∈ E : weight(e) ≥ a }

，或者使之更加明確，你是移除元素從E，你可以長篇大論，並把它定義爲：

G' = (V, E \ { e ∈ E : weight(e) < a })
或G' = (V,E') : E' = E \ { e ∈ E : weight(e) < a }

來源

2015-07-29 10:36:11 MT0

@MTO非常感謝你的兄弟！問題領域的優秀細分和非常明確的解釋。啊，只要我能給你一瓶啤酒！還有一個問題，這個過程的最大運行時間是多少，我怎麼才能正式描述它。謝謝。 – george24

運行時間應該是'O（E）' - 您需要迭代每個邊並測試它的權重，然後創建一個代表該圖的新數據結構。每一步 - 創建一個新圖形;測試重量;並添加邊緣到新圖形 - 應該是'O（1）'（如果有效地完成），並且您將爲每個邊緣重複步驟（總共爲'O（E）'）。要正式說明它，你只需要寫一些類似的東西，但要小心地將算法分解成其組成部分並從那裏開始工作。 – MT0

是的，因爲每個邊都需要被訪問，所以在這種情況下'O（E）'看起來合乎邏輯。謝謝：） – george24

據我所知，你想刪除重量小於A的邊緣。這與cuts in graphs無關。

我想你想要的數學表達式爲：

G'(V', E') = G(V, Q) : Q = {x: x <= A and x belongs to E}

來源

2015-07-28 10:52:56 MrGreen

是的，我認爲我不必看切割。感謝數學表達。 – george24

不客氣 – MrGreen

切入加權無向連通圖

回答

相關問題