构造满足指定性质的二分图的方法问询

嘿，这个问题咱们可以借助Hall婚配定理的反向思路来构造，具体方案如下：

构造步骤 #

咱们把二分图的两个顶点集分别记为 ( A )（左边，15个顶点）和 ( B )（右边，15个顶点）：

• 把集合 ( A ) 拆分成两个子集：( A_1 )（包含8个顶点）和 ( A_2 )（包含剩下的7个顶点）
• 把集合 ( B ) 拆分成两个子集：( B_1 )（包含7个顶点）和 ( B_2 )（包含剩下的8个顶点）
• 建立边的规则：
  • ( A_1 ) 中的每个顶点只与 ( B_1 ) 中的所有顶点相连（也就是 ( A_1 ) 和 ( B_1 ) 构成一个完全二分图 ( K_{8,7} )）
  • ( A_2 ) 中的每个顶点与 ( B ) 中的所有顶点相连（也就是 ( A_2 ) 和 ( B ) 构成完全二分图 ( K_{7,15} )）

验证所有条件 #

咱们来逐一核对题目要求：

1. 两边各15个顶点：显然满足，( |A|=8+7=15 )，( |B|=7+8=15 )
2. 每个顶点度数至少7：
   • ( A_1 ) 中的顶点：每个都连向 ( B_1 ) 的7个顶点，度数为7，符合要求
   • ( A_2 ) 中的顶点：每个连向 ( B ) 的15个顶点，度数为15，符合要求
   • ( B_1 ) 中的顶点：每个连向 ( A_1 ) 的8个顶点 + ( A_2 ) 的7个顶点，度数为15，符合要求
   • ( B_2 ) 中的顶点：每个只连向 ( A_2 ) 的7个顶点，度数为7，符合要求
3. 不存在大小为15的匹配（即完美匹配）：
   根据Hall定理，二分图存在完美匹配的充要条件是：对 ( A ) 的任意子集 ( S )，其邻居集合 ( N(S) ) 的大小 ( |N(S)| \geq |S| )。
   咱们取 ( S = A_1 )（8个顶点），它的邻居集合 ( N(S) = B_1 )（7个顶点），显然 ( |N(S)|=7 < 8=|S| )，不满足Hall条件，因此这个二分图不存在完美匹配。

这样构造出来的二分图就完全符合题目所有要求啦！

备注：内容来源于stack exchange，提问作者popcorn