唯一最大匹配

Question

我想用偶圖有以下特性編寫我的程序：

每側
1. ，有N個頂點
2. 圖是連通的

現在，我想在我的代碼中添加一個條件，檢查邊緣的數量是否大於M，不允許用戶進行更多的活動（在簡單的句子中打印某些條件）其中M是最大邊數，使其仍具有最大匹配的唯一。

問題是我該如何找到M？

如果你的意思是找到最大米，使得存在至少一個曲線圖有n個頂點，且m與唯一的最大匹配邊緣的任何想法可以理解 由於

Answer 1

，答案爲（n + 1） * N/2。

表明存在至少一個圖形與該多個邊緣的，考慮與頂點X 的曲線圖中，x ，...，X爲一個部件和_ñ頂點y ，.. y _n另一部分。在頂點x _i和y _j iff（i < = j）之間畫一條邊。

要顯示不能有更多的邊緣，請在頂點數上使用歸納法。首先我們可以顯示圖中的每個頂點是否連接到至少兩個頂點，該圖具有至少兩個不同的最大匹配。 （考慮一個最大匹配，遵循的路徑從一個頂點，其匹配的邊緣和不匹配的邊緣之間的邊緣交替，使一個圓圈，並扭轉所有的邊緣。）

，所以我們知道有一個頂點等於一個學位。刪除這個頂點，它是鄰居，並在剩下的圖上使用歸納。

對不起英語感到抱歉。