graph - 图中的匹配

Question

如何找到最大基数匹配为 n/4 的图？或者说n/3？这里，n 表示图中的顶点数。连通图可以吗？

Answer 1

最简单的例子是完全二分图 K_m,n。要将匹配大小调整为某个比例 ( |V|/k)，n应该是(2*k-1)*m，从那时起|V| = n + m = 2*k*m，匹配大小是2*m。

Answer 2

您可以根据Tutte Berge 公式构建此类图表。使用它，您可以构建一个最大匹配大小为 n/4 的图形，如下所示。令 V 为图中的顶点集，令 U 为顶点的任何子集。找到一个数 k 使得 k-|U| >= |V|/2。从 VU 构造奇数大小的组件 C1、C2、...、Ck（彼此不相交），并将每个 Ci 的任意一组边添加到 U 的顶点。

请注意，C1,...,Ck 应该是我们在删除 U 时得到的奇数大小的组件。 {U, C1, ... ,Ck} 中的其他顶点可以按照上述约束以任何方式连接。