bipartite

3熱度

3回答

我正在實現一個算法來確定一個無向圖是否是二分的。基於this pseudo-code使我的實現，它適用於圖形連接，但是當它斷開時，只是程序指出了一個錯誤的答案。我認爲如果它沒有連接，那麼每個不相交的子圖就需要一個循環。但我堅持這一點。我怎樣才能解決我的代碼，讓我打印出正確的答案？ #include <cstdio> #include <vector> #include <queue> #in

3熱度

1回答

如何將二部匹配轉換爲獨立集

我讀過「算法設計」一章，它給出瞭如何將二部匹配轉換爲獨立集問題的簡短描述，我不明白。有沒有人知道任何詳細的matriel來描述這個過程？謝謝！

2熱度

2回答

二分圖的隨機生成樹

我正在努力使用metaheuristics爲尋找固定電荷運輸問題（FCTP）的良好解決方案做一些代碼。我遇到的問題是生成一個起始解決方案，基於找到基礎二分圖的生成樹。我希望它是一個隨機生成樹，以便我可以多次運行同一個問題的過程，可能會得到不同的解決方案。我在做這個時遇到了一些困難。到目前爲止我所採用的方法是對弧進行隨機置換，然後遍歷這個列表，如果它不會創建一個循環，則將它們依次放入基礎中。

0熱度

1回答

將圖書館書籍分配給成員以使最大成員滿意的算法

我在班級測試中遇到了問題。在一個圖書館裏，每個成員要求四本書和每本書只有兩個成員要求。此信息在二分圖G =（X + Y，E）的形式給出 X：設置所有成員的Y：設置的所有書籍邊緣E =邊集（X，Y），其中x是書y所要求的成員。我們必須找到圖書管理員可以給每個成員最多兩本書的方式，以使最大成員滿意。我想出了兩種方法：引入了兩個新的頂點S（源）和T（目標）。將邊從s引入到X中容量爲2的所有成員

0熱度

2回答

繪製二分圖的工具或庫？

我正在從事與圖論相關的工作。其實我有一些關於二分圖的數據，我想通過以圖形形式顯示來測試它的有效性。我的數據是在等（三角形）形式： V 0 A V 1 B V 2 C U 0 1 E V表示頂點和U表示的邊緣（A，B，C和E是標籤）。任何人都可以推薦任何最適合我的目的的工具/庫（Java/C）。

15熱度

2回答

iGraph圖中的頂點名稱在哪裏

我的一般問題是，當使用iGraph生成圖時，我丟失了頂點名稱/標籤（不確定這裏是否有正確的單詞）。我有二分網絡的邊緣列表IC_edge_sub，看起來像以下： new_individualID new_companyID 1 <NA> 10024354c 3 10069415i 2020225c 4 10069415i 16020347c 5 10069272i 20

1熱度

2回答

查找最小頂點給定匹配最大值的二分圖覆蓋

我似乎找到了算法，但無法理解它，我想知道是否有人知道該算法的通用輪廓。這裏是鏈接到算法I 2頁 http://www.cse.iitb.ac.in/~sundar/cs435/lecture23.pdf

3熱度

1回答

Brute Force在二分圖中尋找最大獨立頂點集的算法？

有沒有人知道蠻力算法的通用輪廓在二分圖中找到最大獨立頂點集？我知道還有其他算法，例如König定理，用於查找MIS，但是我想知道蠻力方法的僞代碼是什麼？另外，這種蠻力算法的運行時間複雜度是多少？

1熱度

2回答

用戶之間非二部非加權最大匹配

情況：用戶選擇多個其他用戶作爲項目的可能合作伙伴。用戶沒有偏好他選擇的另一個用戶（即，他的列表中的任何用戶對於夥伴而言足夠好）。例如： | user_id | preferred_partners | | 1 | 2 4 | | 2 | 3 1 | | 3 | 4 2 1 | | 4 | 1 | 真實名單會大得多。我的問題：給定一組用戶及其首選合作夥

3熱度

2回答

我怎樣才能找到一個圖的非完美雙向匹配？

也就是說，我怎樣才能找到一個圖的二部分匹配，其中一些頂點可能沒有連接到任何其他頂點？編輯：一個更多的條件，假設邊緣也加權，我想匹配，使總邊權重最小化（或最大化）。