精华内容
下载资源
问答
  • 二部图 Hall定理

    千次阅读 2018-12-06 21:31:20
    hall定理是判定二部图是否存在完备匹配的定理 定理内容 设二分图中G=<V1,V2,E>中 |V1|=m<=|V2|=n,G中存在从V1到V2的完备匹配当且仅当V1中任意k(k=1,2,…,...

    参考:[feynman1999的博客]
    (https://blog.csdn.net/feynman1999/article/details/76037603)
    二部图课件:http://www.docin.com/p-116405961.html

    前言

    hall定理是判定二部图是否存在完备匹配的定理

    定理内容

    设二分图中G=<V1,V2,E>中 |V1|=m<=|V2|=n,G中存在从V1到V2的完备匹配当且仅当V1中任意k(k=1,2,...,m)个顶点至少邻接V2中的k个顶点。
    这里注意:k取1,2,。。。|V1|,都成立时i,才是二部图的充要条件

    Hall定理的一个推论

    设二部图中G=<V1,V2,E>中|V1|=m<=|V2|=n,

    • V1中每个顶点至少关联正整数t条边,
    • V2中每个顶点至多关联t条边(t条件),

    则G存在从V1到V2的完备匹配。

    展开全文
  • 二部图Hall定理学习笔记

    千次阅读 2019-08-16 17:12:13
    定理(Hall定理) 设二部图G=<V1,V2,E>中,|V1|≤|V2|. G中存在从V1到V2的完备匹配当且仅当V1中任意k 个顶点至少与V2中的k个顶点相邻(k=1,2,…,|V1|). 定理 设二部图G=<V1,V2,E>中, 如果存在t≥1, 使得V1...

    离散数学PPT:

    Hall定理

    定理(Hall定理) 设二部图G=<V1,V2,E>中,|V1|≤|V2|. G中存在从V1到V2的完备匹配当且仅当V1中任意k 个顶点至少与V2中的k个顶点相邻(k=1,2,…,|V1|).

    定理 设二部图G=<V1,V2,E>中, 如果存在t≥1, 使得V1中每个顶点至少关联 t 条边, 而V2中每个顶点至多关联t条边,则G中存在V1到V2的完备匹配.

    Hall定理中的条件称为“相异性条件”, 第二个定理中的条件称为 t 条件. 满足 t 条件的二部图一定满足相异性条件.

    换种说法是这样的:

    对于一个二分图G={U+V,E},
    {\forall} S\subset U, \vert S\vert \leq \vert N(S)\vert ⟺ X中的每个结点都有匹配。

    其中N(S)为图G中所有与W相连的结点的集合。

     

    这个定理给出了判断一个二分图中是否存在完备匹配充要条件,即任意U部的子集的元素的个数要不大于其相连的V部的元素的个数。

     

    Hall定理还有个推论:

    对于二分图(U+V, E)最大匹配数为

     \vert M\vert=|U|-\max \limits_{ (S\subset U)}(\vert S\vert - \vert N(S) \vert)

    其中N(S)是S的邻点

     

    解释:设最小匹配不了的点个数设为p,那么最大匹配的个数就是|U| - p, p等于max (|S| − N(S)),其中S是U部的任意子集, N(S) 是和S相连的V部的点的个数。

     

    例1 

    [ARC076F]Exhausted?

    题意:有N个人,1 ~ M号座位,第i个人想坐的座位是 [1,Li] 或 [Ri,M],问最少有多少人的意愿得不到满足。

    思路:

    二分图 G = {X+Y, E},X中的所有结点满足:若其编号为i,则只与Y中编号小于等于Li或编号大于等于Ri的结点连边。给出 |X|, |Y| 和所有的Li, Ri,求G的最大匹配M。( 输出|X|−M,即最多有多少人能有座位坐 )

    根据Hall定理的推论,此题中,已知 |X|,要求G的最大匹配|M|,只要求 max(|S|−|N(S)|)。对于任意的人的子集S(S\subset X),N(S) 必然可以表示成[1,lb]U[ub,M],也即 Y - [lb, ub],[lb, ub]是Y中一个编号的区间。所以我们可以枚举N(S),再求最大的|S|是多少,即枚举[lb, ub],Li <= lb && ub <= Ri的人即可以放在S中。

    所以这样可以简单的用O(n ^ 2)的算法解决,用线段树可以优化到O(nlogn).

    //我还没写这题的代码

     

     

    例2

    2019杭电多校第8场1011


    参考文献:

    屈婉玲《离散数学》课件

    AtCoder Regular Contest 076 F - Exhausted (Hall's marriage theorem 或 贪心)

    【学习】Hall’s Marriage Theorem

     

    待阅读

    例1exhausted贪心

    例1exhausted二分图最大匹配等于最小覆盖

    例1网络流做法

    自己研究一个东西然后写博客好累,我还是先看书补基础吧。。。

     

    展开全文
  • /* 二分答案,判mid是否合法 如何判断:如果是在直线上,那么遍历匹配即可 现在在环上,即既可以向前匹配也可以向后匹配,那么将环拆开,扩展成三倍 ...重要推论:二部图G中的两部分顶点组成的集合分别为X,Y...
    /* 
    二分答案,判mid是否合法 
    如何判断:如果是在直线上,那么遍历匹配即可
    现在在环上,即既可以向前匹配也可以向后匹配,那么将环拆开,扩展成三倍
    
    显然a和b的匹配边是不可能交叉的,因为交叉必定没有不交叉优 
    hall定理:二分图两个点集A,B,连续一段A的点对应连续一段B的点的 充要条件是 这些点对的匹配边之间不交叉
    重要推论:二部图G中的两部分顶点组成的集合分别为X,Y, 若|X|=|Y|,
              且G中有一组无公共端点的边,一端恰好组成X中的点,一端恰好组成Y中的点,则称二部图G中存在完美匹配 
    
    有了这个定理,就可以用在判定上:a的点集对应b点集的连续一段,即b的n个点也是连续的,因为之前已经确定匹配边不交叉 
    先求出a[1]的范围[a[1]-mid,a[1]+mid]对应的能控制的b数组的范围[l1,r1]
    那么a[2]的控制范围要和[l1+1,r1+1]交叉得到[l2,r2] 
    那么a[3]的控制范围要和[l2+1,r2+1]交叉得到[l3,r3] 
    ...依次类推

    可以这个区间长度只会减小不会变大
    */ #include<bits/stdc++.h> using namespace std; #define maxn 200005 long long n,L,a[maxn],b[maxn<<2],c[maxn],m; int judge(int mid){//a[i]的控制区间是[a[i]-mid,a[i]+mid] int l=1,r=m; for(int i=1;i<=n;i++){ while(a[i]-mid>b[l]) ++l; while(a[i]+mid<b[r]) --r; if(l>r)return 0; ++l,++r; } return 1; } int main(){ cin>>n>>L; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)cin>>c[i]; sort(c+1,c+1+n);sort(a+1,a+1+n); for(int i=1;i<=n;i++)b[i]=c[i]-L; for(int i=1;i<=n;i++)b[i+n]=c[i]; for(int i=1;i<=n;i++)b[i+2*n]=c[i]+L; m=3*n; int l=0,r=L,ans,mid; while(l<=r){ mid=l+r>>1; if(judge(mid)) ans=mid,r=mid-1; else l=mid+1; } cout<<ans<<'\n'; }

     

    转载于:https://www.cnblogs.com/zsben991126/p/11176246.html

    展开全文
  • Hall定理

    2020-11-27 20:35:33
    二部图两集合分别为 X,YX,YX,Y (∣X∣≤∣Y∣|X|\le|Y|∣X∣≤∣Y∣) 若任意 W∈XW\in XW∈X 有 ∣W∣≤∣N(W)∣|W|\le |N(W)|∣W∣≤∣N(W)∣ 那么二部图存在X部匹配完的方案 二分图的最大匹配数:∣X∣−maxW∈S...

    设二部图两集合分别为 X , Y X,Y X,Y ( ∣ X ∣ ≤ ∣ Y ∣ |X|\le|Y| XY)
    若任意 W ∈ X W\in X WX ∣ W ∣ ≤ ∣ N ( W ) ∣ |W|\le |N(W)| WN(W)
    那么二部图存在X部匹配完的方案
    二分图的最大匹配数: ∣ X ∣ − m a x W ∈ S ( ∣ W ∣ − ∣ N ( W ) ∣ ) |X|-max_{W\in S}(|W|-|N(W)|) XmaxWS(WN(W))

    展开全文
  • HALL定理

    千次阅读 2015-06-18 10:18:41
    维基百科:...Hall 结婚定理(Hall’s MarriageTheorem or Hall's theorem)由英国数学家Philip Hall提出(The graph theoretic formulation deals witha bipartite graph. It giv
  • 二分G中的两部分顶点组成的集合分别为X, Y(假设有\(\lvert X \rvert \leq \lvert Y \rvert\))。G中有一组无公共点的边,一端恰好为组成X的点(也就是存在完美匹配)的充分必要条件是:X中的任意k个点至少与Y中的k个...
  • Hall定理: 设G为具有分类(X,Y)的偶图,则G包含饱和点X的每个顶点的匹配当且仅当|N(S)|>=|S|,对所有S是X的子集都成立。 发现上面这句话读的很拗口,虽然是课本原话,这里我引用wiki。hall定理全名hall ...
  • Hall定理的内容是:二部图G中的两部分顶点组成的集合分别为X, Y;边集中有一组无公共点的边,一端恰好为组成X的所有点的充分必要条件是:X中的任意k个点至少与Y中的k个点相邻。 听起来像屁话一样 我们在一段区间[l...
  • 给出一个二部图,左边nn个点,标记分别为a1,a2,...,ana_1,a_2,...,a_n,右边mm个点,标记分别为b1,b2,...,bmb_1,b_2,...,b_m,给出一个n×mn\times m的矩阵表示二部图的边,11表示连边00表示不连边,qq次查询,每次...
  • 题意 题目链接 Sol 好的又是神仙题。。。 ...我的思路:对于区间分两种情况讨论,一种是完全包含,另一种是部分...首先这题可以看是二分匹配,最暴力的写法是对于每个a[i],直接拆成a[i]个点,然后分别向$[l_i, r_...
  • 定理使用于组合问题中,二部图 G中的两部分顶点组成的集合分别为X, Y, X={X1, X2, X3,X4, ......... ,Xm}, Y={y1, y2, y3, y4 , ........., yn},G中有一组无公共点的边,一端恰好为组成X的点的充分必要条件是: ...
  • 图论: 二部图的匹配问题 总结

    千次阅读 2020-04-13 17:44:09
    2. 二部图的匹配与覆盖 3. Tutte定理 1. 图的匹配与Berge定理 1.1 图的匹配的相关概念 匹配M: 不含自环;任意两边无公共顶点; M饱和点: 匹配M中某条边的顶点; M非饱和点: 不是M中某条边的顶点; 极大匹配...
  • 二部图G中的两部分顶点组成的集合分别为X, Y. X = X 1 , X 2 , X 3 , X 4 , . . . . . . . . . , X m , Y = Y 1 , Y 2 , Y 3 , Y 4 , . . . . . . . . . , Y n X={X_1, X_2, X_3,X_4,.........,X_m}, Y={Y_1, Y_2, ...
  • 二部图

    2020-08-28 21:52:24
    二部图
  • 根据Hall定理,二部图G=(V1,V2;E)有一个浸润V1匹配的充要条件是:SV1,N(S)∩V2≥S,即V2中与V1的任一子集S相邻的顶点数不小于S中的顶点数。当V1中的顶点数较多时,用该条件判定较为困难。本文给出了一个基于顶点度判别...
  • 目录石墨笔记 PPT版1 二部图 偶图 双图 二分图 Ks,t G(V1,V2,E)2 欧拉图3 哈密顿图4 平面图欧拉公式推论: n-m+r = k+1m <=3n-6是平面图的必要条件m <= ((k-2)/k )*(n-2)是平面图的必要条件库拉图斯基定理: ...
  • 二部图 G中的两部分顶点组成的集合分别为X, Y, X={X1, X2, X3,X4, ......... ,Xm}, Y={y1, y2, y3, y4 , ........., yn},G中有一组无公共点的边,一端恰好为组成X的点的充分必要条件是: X中的任意k个点至少与...
  • 6.1 二部图 本节大多都是概念的引入,我就用我自己的话去记录了。 二部图(偶图):我们将图里的点分为两个集合V1V_1V1​,V2V_2V2​后,每一条边的端点分别属于V1V_1V1​,V2V_2V2​。我们将二部图记做GGG = <V1V...
  • /* 这个问题将是每行一个x作为节点x,没有列y作为节点y,障碍物的坐标xy来自x至y的 边缘。...定理:最小点覆盖数 = 最大匹配数。即求的最大匹配就可以,匈牙利算法 ------------------------------...
  • 一、组合存在性定理、Ramsey 定理内容概要 、
  • 目录染色法增广路的性质一些二分的概念和定理二分最大匹配匈牙利算法二分匹配模型的两个要素二分最小点覆盖的一个要素DAG的最小路径点覆盖DAG的最小可重复路径点覆盖最小可重复路径点覆盖模板 二分: 如果...
  • 6.1 二部图 二部图(偶图),互补顶点子集,完全二部图(完全偶图) 判断是否是二部图的定理 匹配,极大匹配,最大匹配,匹配数,饱和点,非饱和点,完美匹配 完备匹配 存在完备匹配的充要条件(Hall定理),相异性...
  • \) 是一个无向, 如果顶点V可分割为两个不相交的子集 \((X, Y)\), 且中的每条边 \((i, j)\)均满足\(i \ in X, j \in Y\), 则称\(G\)为一个二分。 二分判定 无向 \(G=<V, E>\) 为二分的充要条件...
  • 【转http://www.cppblog.com/abilitytao/archive/2009/09/02/95147.html -> http://yejingx.ycool.com/post.2801156.html;... 二分最小覆盖的Konig...
  • 匈牙利算法是基于Hall定理中充分性证明的思想,它是二部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。 这篇文章讲无权二分图(unweighted bipartite graph)的...
  • 转化后的题意就是:有N个人,1 ~ M号座位,第i个人愿意坐的座位是[1,Li]或 ...在二分匹配中有个Hall's marriage theorem定理(https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem),这个定理给出了
  • 二分匹配——匈牙利算法

    千次阅读 多人点赞 2019-05-31 16:57:03
    匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。 基本原则就是在原有匹配(最开始的按优先顺序匹配)基础上...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 499
精华内容 199
关键字:

二部图hall定理