在圖表中匹配

Question

如何找到最大基數匹配大小爲n/4的圖形？或者說n/3？這裏，n表示圖中頂點的數量。連接圖可能嗎？

Answer 1

最簡單的例子是complete bipartite graph K_m,n。要調整匹配大小爲一定比例（|V|/k），n應該是(2*k-1)*m，從此​​，匹配大小是2*m。

Answer 2

您可以根據Tutte Berge formula構建此類圖表。使用這個，您可以構建一個最大匹配大小爲n/4的圖形，如下所示。設V是圖中的頂點集，並且U是頂點的任何子集。找到一個數字k，使得k- | U | > = | V |/2。從VU構造奇數大小的組件C1，C2，...，Ck（彼此不相交），並將每個Ci的任意一組邊緣添加到U的頂點。

請注意C1，... ，Ck應該是我們在刪除U時得到的奇數大小的分量。{U，C1，...，Ck}中的其他頂點可以以任何方式連接，但要受到上述約束。