首页 > 其他分享 >Hall 定理

Hall 定理

时间:2024-08-21 15:51:18浏览次数:13  
标签:二分 一个点 cup 定理 子集 Hall

Conventions

我们约定 \(G=(V,E)\) 是一个标准的二分图,使用 \(V_1,V_2\) 来描述两侧的不同的集合,约定 \(V_1\cup V_2=V\) 且 \(\left\lvert V_1\right\rvert<\left\lvert V_2\right\rvert\)。

Theorem

一个二分图存在完备匹配的充要条件是对于左部点大小为 \(k\) 的任意子集 \(S\),这些点的邻域 \(N(S)\) 的大小不小于 \(k\)。

Proof

首先证明必要性,如果一个点集的 \(N(S)\) 不足 \(|S|\),那么该集合不能找到一个完备匹配,与定义相反。

然后证明充分性。考虑使用归纳,分为两种情况:

  1. 如果存在一个严格子集 \(S\) 满足 \(S=N(S)\),则子集本身存在完备匹配。

    如果删去 \(S,N(S)\) 后出现不满足条件的集合 \(T\),那么在原二分图中取子集 \(S\cup T\),必然有 \(|N(S\cup T)|<|S\cup T|\),与假设矛盾。

    那么由此证明如果存在 \(|S|=|N(S)|\),\(\text{Hall}\) 定理成立。

  2. 如果所有子集的 \(|N(S)|\) 均大于 \(|S|\),那么找到一个点 \(u\) 并找到 \((u,v)\in E\),删掉 \(u,v\in V,(u,*),(*,v)\in E\)。

    不难发现此时剩下的二分图每个子集 \(S\) 都能满足 \(|N(S)|\geq |S|\),而且因为删掉了一个点,问题是原问题的子问题。

    根据归纳假设,\(\text{Hall}\) 定理在此情况下也成立。

标签:二分,一个点,cup,定理,子集,Hall
From: https://www.cnblogs.com/QcpyWcpyQ/p/18371788

相关文章

  • 二项式定理
    二项式定理$\quad\quad\quad(x+y)^n=\sum_{k=0}^{n}{n\choosek}x^{n-k}y^k$证明\(\quad(x+y)^n=(x+y)*(x+y)*(x+y)*...\)我们考虑多项式乘法\((a+b)*(a+b)=a*a+a*b+b*a+b*b\)于是我们枚举每个因子相乘,可以发现\((x+y)^n\)每个括号里的\(x\)和\(y\)最多只能选......
  • 程序 · 杂谈 | DeepSeek发布最强开源数学定理证明模型
    DeepSeek-Prover-V1展示了大模型在数学定理证明领域的潜力,通过将数学问题转换为Lean编程语言,帮助数学家严格验证证明正确性。今天,DeepSeek开源Prover-V1.5版本,引入了类似AlphaGo的强化学习系统,模型通过自我迭代和Lean证明器监督,构建了一个“围棋”式的学习环境。最终,......
  • 二项式定理(二项式展开)
    目录引入正题延伸引入首先有一个广为人知的结论:\[(a+b)^2=a^2+2ab+b^2\]那么,如何求\((a+b)^3\)呢?手算,如下:\[\begin{aligned}(a+b)^3&=(a+b)\times(a+b)^2\\&=(a+b)\times(a^2+2ab+b^2)\\&=[a\times(a^2+2ab+b^2)]+[b\times(a^2+2ab+b^2)]\\&=(a^3+2a^2b+ab^......
  • 卢卡斯定理
    卢卡斯定理常用于求组合数,且质数模数\(p\)较小时的情况(常常与费马小定理结合使用,要是\(p\)不是质数直接上扩欧就可以了)。那为什么要用卢卡斯定理?因为虽然\(p\)是质数,但是如果\(x>p\),那么他俩不一定互质,所以\(x\)在模\(p\)意义下不一定存在逆元,那我们的组合数公式无法......
  • 高数3.3 泰勒公式(泰勒中值定理)
    目录1.定义:2.证明:3.麦克劳林公式:4.推论:4.1证明5.基本思想:6.例题:7.笔记:1.定义:2.证明:3.麦克劳林公式:......
  • Stolz 定理
    第一公式数列若\(\{a_n\}\uparrow\)且\(\lim\limits_{n\to\infty}{a_n}=+\infty\),又数列\(\{b_n\}\)满足\[\lim\limits_{n\to\infty}\dfrac{b_{n+1}-b_{n}}{a_{n+1}-a_{n}}=l\]其中\(l\)有限或为正负无穷(无穷不可),则有\[\lim\limits_{n\to\infty}\dfr......
  • 中国剩余定理(CRT)
    引出        在《孙子算经》中有这样一个问题:        “今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?”也就是说有如下的方程组:     求该方程组的解设为最小整数解:则  令   ,且通过取模得0的几个式子可以得到其最小公倍......
  • Apple Intelligence提示词曝光:Do not hallucinate;XLabs-AI 又发布两个脚本x-flux;吴恩
    ✨1:Somepre-promptinstructionsforAppleAppleIntelligence提示词曝光:Donothallucinate苹果在其最新的开发者测试版中推出了一些生成型AI功能,这些功能已经在WWDC大会上宣布,计划在未来几个月内陆续登陆iPhone、iPad和Mac等设备。一位用户在macOS15.1开发者测......
  • Monty Hall problem
    Theproblemcanbeformulatedasfollows.Asaparticipantofagame show,youhavetochooseoneofthreedoors.Behindoneofthedoorsisa prize,behindtwootherdoorsisnothing.Afteryoupickadoor,thegame host,whoknowswheretheprizeis,se......
  • Floyd-Warshall
    Floyd-WarshallFloyd-Warshall算法的核心思想是利用动态规划的思想,通过逐步更新距离矩阵来求解所有节点对之间的最短路径。它适用于解决图中节点对数量较小且权重可以为负的情况。时间复杂度为O(n^3)。java代码模板staticfinalintINF=Integer.MAX_VALUE;//graph中......