草庐IT

二分图--最小点覆盖及证明

cc！ 2023-04-04 原文

目录

(1) 定义:

(2)结论:

(3) 证明:

(4)例题:

看了往上诸多博客,感觉讲的稍有欠缺,于是自己写了一篇(耐心浏览)

最小点覆盖 :

(1) 定义:

假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。

(2)结论:

最小点覆盖 = 最大匹配数

(3) 证明:

先了解一些概念

匹配点:匹配边两端的端点

增广路径,即:一边的非匹配点到另一边的非匹配点的一条非匹配边和匹配边交替经过的路径. (开头和结尾一定是非匹配点且不在一个集合中)

如图绿色的线就是增广路径:

 然后简单说一下匈牙利算法:

(1)找出一条增广路，通过将增广路取反，得到新的M’来代替原M，新的匹配数相对于原匹配数多1

(2)重复(1)操作，直至匹配过程中找不到增广路为止。

进入正题:

证 最小点覆盖 == 最大匹配数

设 最小点覆盖数 为 s ,最大匹配数 为 m

(1)首先 证 s >= m 

我们知道 当我们得到最大匹配数 时,所有边是没有交点的,即所有匹配边没有公共点,这个时候我们就可以在这些边中选一端作为覆盖点 ,我们要找到最小个数的点集使其关联所有边,必然包含我们从匹配边中的到的覆盖点,所以 证得 s>=m

(2) 接下来我们证明 m为最小覆盖点数 (通过构造方法)

我们先通过构造得到一个点集,再证明这些点就是最小覆盖点

构造方法如下:

1.我们在一个二分图中先得到最大匹配

如图红色的是匹配边

2.从左边的每一个非匹配点开始做增广路径(即使不能构成增广路径,因为成功的话就不是最大匹配了,最大匹配后没有增广路径),并且对走过的点进行标记

 3.选择方式:选出左边所有未被标记的点+右边所有被标记的点(用红色圈出),我们设为 K

我们通过上面的描述可以得到三个性质: 

  1. 右部所有非匹配点一定没有被标记(因为右边非匹配点被标记的话,就会形成增广路径,这会和我们在最开始已经进行最大匹配矛盾)
  2. 左部非匹配点一定被标记,因为起点增广标记起点就是非匹配点
  3. 一条匹配边要么同时被标记要么同时不被标记

接下来       我们证明 k == m 

所有边可以分为匹配边和非匹配边,所以我们可以分开说明

先证明 这些点覆盖了所有匹配边(所有点都是匹配点)

  • 在选择的时候,我们选择左边所有未被标记的点,即匹配点(性质二可知),形如图中的最下面那条匹配边的左边那个点
  • 我们还要选择 右边被标记的点,即由于性质一可以得到
  • 对于每个匹配边,左右两个点要么同时被标记,要么同时不被标记,
  •        同时被标记的点所在的匹配边,由于我们选择了右边所有被标记的点,(因为增广路径,我们从非匹配点出发,左边被标记一定是因为右边的点先被标记了,所以他是根据右边的标记点来的) ,所以这些匹配边我们全选了
  •        同时未标记的点所在的匹配边,由于我们选择了左边所有不被标记的点,所以这些匹配边我们全选了

      可知,我们的选择是所有的m条匹配边,且每个匹配边我们只会选择左,或者右边一个点
一共m个点

由此我们证明了k个点都是匹配点 , 覆盖了所有匹配边

再者证明 这些点覆盖了所有非匹配边

而非匹配边又可以分为两种情况:

  • (1)左边是非匹配点 ------ 右边是匹配点 (形如图中 s1 的边) :
  • 每次我们选左边非匹配点作为起点做增广路径,所以右边的点一定被标记,且在选择的时候,我们会选择右边的标记的匹配点, 所以选出来的点在此情况下覆盖了非匹配边
  • (2)左边是匹配点------右边是匹配点
  • 形如 s2 ,如果存在这样的边,就说明存在增广路径,和我们最开始求了最大匹配矛盾了,所以在最大匹配后不存在这种情况

所以由此证明选出来的点包含所有边,且 个数 等于从匹配边里选出的覆盖点,即最大匹配数(每条边选一个点)

所以,

最小点覆盖 = 最大匹配数 !!!!!!!!!!!

证毕!

心累,点赞吧!!!!

例题:

 输入:

5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0

输出:

3

思路:把每个任务看作一个匹配边,我们要选择最少的点覆盖所有的边,模式为0的我们一开始就让他做,可以忽略

上代码:

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1e3;
int g[maxn][maxn];
int match[maxn];
int vis[maxn];
int n,m;

int find(int x){
    for(int i = 1;i<=m;i++){
        if(vis[i]||!g[x][i])continue;
        vis[i] = 1;
        if(match[i] == 0 || find(match[i]) ){
            match[i] = x;
            return 1;
        }
    }
    return 0;
}

int main(){
    int k=0;
    while(cin>>n,n){
      memset(match,0,sizeof match);
      memset(g,0,sizeof g);
    cin>>m>>k;
    while(k--){
        int a,b,c;
        cin>>a>>b>>c;
        if(!b||!c)continue;
        g[b][c] = 1;
    }
    int res = 0 ;
    for(int i = 1;i<=n;i++){
        memset(vis,0,sizeof vis);
        if(find(i))res++;
    }
    cout<<res<<endl;
    }
}

二分二分图strong增广blockquote算法$图论$蓝桥杯$数据结构

有关二分图--最小点覆盖及证明的更多相关文章

  1. ruby-on-rails - 在混合/模块中覆盖模型的属性访问器 - 2

    我有一个包含模块的模型。我想在模块中覆盖模型的访问器方法。例如:classBlah这显然行不通。有什么想法可以实现吗？ 最佳答案 您的代码看起来是正确的。我们正在毫无困难地使用这个确切的模式。如果我没记错的话，Rails使用#method_missing作为属性setter，因此您的模块将优先，阻止ActiveRecord的setter。如果您正在使用ActiveSupport::Concern(参见thisblogpost)，那么您的实例方法需要进入一个特殊的模块:classBlah

  2. ruby - 无法覆盖 irb 中的 to_s - 2

    我在pry中定义了一个函数:to_s，但我无法调用它。这个方法去哪里了，怎么调用？pry(main)>defto_spry(main)*'hello'pry(main)*endpry(main)>to_s=>"main"我的ruby版本是2.1.2看了一些答案和搜索后，我认为我得到了正确的答案:这个方法用在什么地方？在irb或pry中定义方法时，会转到Object.instance_methods[1]pry(main)>defto_s[1]pry(main)*'hello'[1]pry(main)*end=>:to_s[2]pry(main)>defhello[2]pry(main)

  3. ruby - 覆盖相似的方法，更短的语法 - 2

    在Ruby类中，我重写了三个方法，并且在每个方法中，我基本上做同样的事情:classExampleClassdefconfirmation_required?is_allowed&&superenddefpostpone_email_change?is_allowed&&superenddefreconfirmation_required?is_allowed&&superendend有更简洁的语法吗？如何缩短代码？ 最佳答案 如何使用别名？classExampleClassdefconfirmation_required?is_a

  4. ruby - 是否可以覆盖 gemfile 进行本地开发？ - 2

    我们的git存储库中目前有一个Gemfile。但是，有一个gem我只在我的环境中本地使用(我的团队不使用它)。为了使用它，我必须将它添加到我们的Gemfile中，但每次我checkout到我们的master/dev主分支时，由于与跟踪的gemfile冲突，我必须删除它。我想要的是类似Gemfile.local的东西，它将继承从Gemfile导入的gems，但也允许在那里导入新的gems以供使用只有我的机器。此文件将在.gitignore中被忽略。这可能吗？ 最佳答案 设置BUNDLE_GEMFILE环境变量:BUNDLE_GEMFI

  5. ruby - 获取数组中的值并最小化某个类属性的最优雅的方法是什么？ - 2

    假设我有以下类(class):classPersondefinitialize(name,age)@name=name@age=ageenddefget_agereturn@ageendend我有一组Person对象。是否有一种简洁的、类似于Ruby的方法来获取最小(或最大)年龄的人？如何根据它对它们进行排序？ 最佳答案 这样做会:people_array.min_by(&:get_age)people_array.max_by(&:get_age)people_array.sort_by(&:get_age)

  6. Ruby - 如何处理子类意外覆盖父类(super class)私有(private)字段的问题？ - 2

    假设您编写了一个类Sup，我决定将其扩展为SubSup。我不仅需要了解你发布的接口(interface)，还需要了解你的私有(private)字段。见证这次失败:classSupdefinitialize@privateField="fromsup"enddefgetXreturn@privateFieldendendclassSub问题是，解决这个问题的正确方法是什么？看起来子类应该能够使用它想要的任何字段而不会弄乱父类(superclass)。编辑:equivalentexampleinJava返回"fromSup"，这也是它应该产生的答案。 最佳答案

  7. ruby - 解释为局部变量会覆盖方法名称吗？ - 2

    如thisquestion，当在其自己的赋值中使用未定义的局部变量时，它的计算结果为nil。x=x#=>nil但是当局部变量的名称与现有的方法名称冲突时，就比较棘手了。为什么下面的最后一个示例返回nil？{}.instance_eval{a=keys}#=>[]{}.instance_eval{keys=self.keys}#=>[]{}.instance_eval{keys=keys}#=>nil 最佳答案 在Ruby中，因为可以在没有显式接收器和括号的情况下调用方法，所以在局部变量引用和无接收器无参数方法调用之间存在语法歧义:f

  8. ruby-on-rails - capybara poltergeist - 覆盖用户代理 - 2

    有人知道如何将capybarapoltergeist的用户代理覆盖到移动用户代理以进行测试吗？我发现了一些有关为seleniumwebdriver配置它的信息:http://blog.plataformatec.com.br/2011/03/configuring-user-agents-with-capybara-selenium-webdriver/这在capybara闹鬼中怎么可能？ 最佳答案 请参阅poltergeistgithub页面上的链接:https://github.com/teampoltergeist/polte

  9. ruby-on-rails - 安装多个版本的 Rails 会覆盖以前的安装吗？ - 2

    如果我一直输入geminstallrails使用不同版本的Rails会怎样？例如，我可以输入:geminstallrails--verson3.2.10或geminstallrails这给了我版本3.2.12。问题每次安装都会覆盖之前的吗？它会删除所有旧文件并添加我正在安装的新版本吗？或者如果我运行它两次，它会保留一些文件吗？我正在使用Ubuntu。 最佳答案 它将安装两个独立的gem。实际的可执行文件rails将调用最新版本。你可以覆盖它__例如，rails_3.2.10_将执行Rails3.2.10。bundler顺便说一下，如

  10. Ruby隐藏与覆盖 - 2

    我刚刚了解到，在Java中，覆盖和隐藏之间是有区别的(静态方法是隐藏的，而不是覆盖)，这意味着Java使用早期绑定(bind)和后期绑定(bind)。是否有与方法隐藏类似的东西，或者它只是具有方法重写？ 最佳答案 Java具有三种不同的“方法”:实例方法，静态方法和构造函数。Ruby只有一个:实例方法。在Java中，静态方法的行为必须不同于实例方法，因为类不是对象。它们没有类，因此也没有父类(superclass)，因此没有要覆盖的内容。在Ruby中，类与其他任何对象一样都是对象，它们具有一个类，该类可以具有父类(superclas

随机推荐