bipartite

0熱度

2回答

的integraloty定理告訴我們，如果在流動網絡中的所有能力都是整數，再有就是，每一個值是一個整數但最顯着的部分是一個最大流量存在，不是每個最大流量！這意味着這一說法並不要求每最大流量爲整數值我想不出爲什麼如果所有的容量是整數，但存在一個最大流量不整數值！或者我剛剛弄錯了這個試圖告訴我的定理的想法嗎？

5熱度

1回答

加權二分配匹配

我知道有很多類似的話題。但他們中的大多數在我的情況下給我留下了一些疑問。我想要做的是找到完美的匹配（或者儘可能接近完美，以防萬一沒有完美的匹配），然後從所有匹配中你能匹配k個n個頂點（其中k儘可能高）），我想選擇儘可能高的總重量。所以乾脆把我說的是以下優先級：匹配儘可能多的頂點儘可能因爲（非加權）在大多數情況下，最大匹配是毫不含糊的，我想選擇有最大的一個邊上的權重總和。如果它們中有幾個具有

2熱度

1回答

如何去除邊緣以生成圖形二部分？

我有可能（或可能不）包括一組邊緣，使其二分的曲線圖。我怎麼能發現這樣的一套存在？將移除所有邊緣BFS遍歷有助於在一個特定的水平？

0熱度

1回答

檢查由多個不連通圖組成的大圖中的二分性？

我在SPOJ上做了一個問題SPOJ:BUGLIFE 它需要我檢查圖形是否是二分圖。我知道單個連通圖的方法，但對於不連通圖的組合，我的方法給出超時時間限制的錯誤。這是我的方法 - 廣度優先搜索，使用圓形隊列和由鄰接表實現的圖形。方法 - >選擇一個源，並且如果該源頂點=未訪問，則開始一個寬度優先搜索，假定它是源。如果我在BFS中發現了衝突，那麼我會放棄整個事情。否則，我會轉移到另一個未訪問的來源

8熱度

2回答

最小化在二部圖口岸的數量

下面的算法問題發生在我身上，同時繪製圖形的東西無關：我們有一個二分圖的平面圖紙，與設置在獨立集合如圖所示。我們如何重新排列每列中的節點，以便邊緣交叉點的數量最小化？我知道這個問題對於普通圖（link）是NP-hard，但考慮到圖是雙方的，有一些技巧嗎？作爲後續，如果有什麼是第三列瓦特，其中只有邊緣v？還是進一步？

0熱度

1回答

爲二分圖優化索引腳本

我正在使用雙分圖來分析給定主題和地理位置下載的推文的網絡和語義值。使用Python，我創建了一個包含2組節點和邊的.net文件。該文件是我單獨創建的文件的合併：2組頂點和邊。問題是創建.net文件的邊緣組件。我有3個文件： tweeterers.csv與發件人/ tweeterers（「號/ ID」和「名」） words.csv，與語義標籤/字我從推文中提取。格式爲「編號/ ID」和「

0熱度

1回答

埃德蒙茲算法匹配

我想找到使用埃德蒙茲算法在二部匹配最大匹配二分最高。不幸的是，我無法獲得僞代碼。誰能幫我？

0熱度

1回答

如何將SPOJ Quest4轉換爲最小頂點覆蓋

以下是最大二點匹配問題：http://www.spoj.com/problems/QUEST4/ 通過論壇我發現問題可以轉化爲最小頂點覆蓋問題，而最小頂點覆蓋問題又可以通過Maximum二分配匹配。但是，我不明白問題是如何轉換成最小頂點覆蓋的。請幫我理解這一點。

4熱度

1回答

關於算法的Skiena設計

我被困在Skiena的算法設計問題上。我不知道我的解決方案是否正確。 5-18。考慮一組電影M_1，M_2，... M_k。有一組客戶，每個客戶都指出他們希望在本週末看到的兩部電影。電影將在週六晚上和週日晚上播放。多部電影可能會同時放映。您必須決定哪些電影應在週六和週日哪些電視上播放，以便每位顧客都能看到他們所需的兩部電影。是否有一個時間表，每部電影最多隻顯示一次？設計一個有效的算法來找到這樣的時

0熱度

1回答

我應該用什麼來實現C++中的加權二分匹配算法？

我有一個項目，它要求我將課程分發給學生。所有學生都要求提供一些課程，但他們只能獲得一些課程（這可能是他們要求的，不到的或只是0 ），所有課程都有配額，我需要找到完美匹配（所有配額是否滿員，學生是否獲得了他們所允許的配額）是否存在 - 如果存在匹配的輸出。我剛剛獲得輸入並將其存儲在對象中。項目中存在時間限制，我不知道從哪裏開始。對於此項目的任何建議或方法？我想我應該實現二部匹配算法。我是新的C+