精华内容
下载资源
问答
  • 二部图 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定理) 设二部图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,YX,Y (XY|X|\le|Y|)
    若任意 WXW\in XWN(W)|W|\le |N(W)|
    那么二部图存在X部匹配完的方案
    二分图的最大匹配数:XmaxWS(WN(W))|X|-max_{W\in S}(|W|-|N(W)|)

    展开全文
  • 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次查询,每次...
  • 6.1 二部图 二部图(偶图),互补顶点子集,完全二部图(完全偶图) 判断是否是二部图的定理 匹配,极大匹配,最大匹配,匹配数,饱和点,非饱和点,完美匹配 完备匹配 存在完备匹配的充要条件(Hall定理),相异性...
  • 匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的...二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点...
  • 前言  匈牙利算法是由匈牙利数学家Edmonds于1965年提出,... 二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关...
  • ...   二分图的最大匹配、完美匹配和匈牙利算法 匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是二部图匹配最常见的算法,该算法的核...
  • 匈牙利算法是基于Hall定理中充分性证明的思想,它是二部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。 这篇文章讲无权二分图(unweighted bipartite graph)的...
  • 匈牙利算法是基于Hall定理中充分性证明的思想,它是二部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。 #include<stdio.h> #include<string.h> #...
  • 匈牙利算法是基于Hall定理中充分性证明的思想,它是二部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。设 G=(V,E) 是一个无向图。如顶点集V可分割为两个互不相交的...
  • 求二分图最大匹配(指派问题)的匈牙利算法: 谈匈牙利算法自然避不开Hall定理,即是:对于二部图G,存在一个匹配M, 使得X的所有顶点关于M饱和的充要条件是:对于X的任意一个子集A,和A邻接的...
  • 离散数学-图论相关

    千次阅读 2019-04-11 16:25:29
    文章目录图的基本概念无向图和有向图无向图有向图关联和度关联度握手定理简单图与完全图简单图通路、回路和图的连通性通路回路一些关于通路和回路的定理定理1定理2连通性割集二部图定义二部图判定Hall定理欧拉图...
  • 1135: [POI2009]Lyz

    2018-12-02 20:26:00
    1135: [POI2009]Lyz ... 分析:  hall定理+线段树连续区间的最大的和。  首先转化为二分图的模型,然后根据...此定理使用于组合问题中,二部图G中的两部分顶点组成的集合分别为X, Y, X={X1, X2, X3,X4,............
  • 匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。 -------等等,看得头大?那么请看下面的版本: 通过数...
  • 匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。 -------等等,看得头大?那么请看下面的版本:...
  • 匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。 维基: 设G=(V,E)是一个无向图。如顶点集V可分区为两个...
  • 匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。 -------等等,看得头大?那么请看下面的版本: ...
  • 匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。-------等等,看得头大?那么请看下面的版本:通过数代人的...
  • 匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。 -------等等,看得头大?那么请看下面的版本: 通过数...
  • Hall 定理定理 3.3.1):设 G 是具有二划分 ( X ,Y ) 的二部图,则 G 有饱和 X 的匹配当且仅当对 ∀S ⊆ X , N (S) ≥ S ,其中 N (S) 表示 S 的所有邻点之集。 Berge 定理定理 3.1.1):图 G 的匹配 M 是最大...
  • 匈牙利算法

    千次阅读 2004-12-26 16:53:00
    二部图最大匹配(指派问题)的匈牙利算法: 谈匈牙利算法自然避不开Hall定理,即是:对于二部图G,存在一个匹配M,使得X的所有顶点关于M饱和的充要条件是:对于X的任意一个子集A,和A邻接的点集为T(A),恒有: |T...
  • 匈牙利算法java版本

    千次阅读 2016-12-21 16:43:17
    匈牙利算法java版本匈牙利算法java版本 ...匈牙利算法是基于Hall定理中充分性证明的思想,它是二部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。(摘

空空如也

空空如也

1 2
收藏数 36
精华内容 14
关键字:

二部图hall定理