首页 > 其他分享 >二分图的一些概念

二分图的一些概念

时间:2023-08-15 17:33:28浏览次数:26  
标签:二分 匹配 最大 最小 概念 一些 集合 顶点


二分图:将图中的顶点分为两个集合X和Y,X与Y集合没有交集,并且各自集合内的点没有边相连,X集合与Y集合形成边
二分匹配:在二分图的基础上,X Y两个集合所形成的边集中的子集M,M中的任意两条边没有公共的顶点
最大匹配:当M中的边数达到二分图的上限时称为最大匹配
完美匹配:二分图中的所有顶点都在匹配的边上,称为完美匹配
增广路:在图中的一条路径从未匹配的顶点开始到未匹配的顶点结束,其中路径是待匹配边与已匹配边交替出现
最小点覆盖:选取最少的点数(可以是X||Y集合),使这些点和所有的边都有关联(把所有的边的覆盖)
最小边覆盖:在图中找一些边,使之覆盖了图中所有顶点,且任何一个顶点有且只有一条边与之关联。
最大独立集:在集合中的任意两点没有边,并且集合中的顶点个数达到上限
最大团:在集合中的任意两点有边,并且集合中的顶点个数达到上限

匈牙利算法:每次寻找增广路,如果能寻到匹配加1

二分图的最小顶点覆盖数 = 二分图的最大匹配数
二分图的最大独立集数 = 节点数(n)- 最大匹配数(m)
最大团=节点数-补图的最大独立集

最小边覆盖数=节点数(n)- 最大匹配数(m)


标签:二分,匹配,最大,最小,概念,一些,集合,顶点
From: https://blog.51cto.com/u_3936220/7091418

相关文章

  • 浅谈5G技术会给视频监控行业带来的一些变革情况
    5G是第五代移动通信技术,能够提供更高的带宽和更快的传输速度,这将为视频技术的发展带来大量机会。随着5G技术的逐步普及与商用,人们将能够享受到更加流畅的高清视频体验,并且5G技术还拥有更低的延迟和更高的网络容量。这些优势不仅将推动视频技术的变革,也将创造出更多的商业机会和产业......
  • Python基础概念以及命名规范
    PythonBasicIntroduction介绍Pythonisadynamicandstronglytypedprogramminglanguage.Itemploysbothducktypingandgradualtypingviatypehints.WhilePythonsupportsmanydifferentprogrammingstyles,internallyeverythinginPythonisanobject......
  • JavaScript 如何封装一些常见的函数来提高工作效率
    前言为什么要封装函数JavaScript封装函数的主要目的是为了保护代码的安全性和可维护性。封装可以隐藏实现细节:将函数内部的实现细节封装起来,只暴露给外部必要的接口,可以使代码更加安全,防止意外修改或者滥用。封装可以提高代码的可维护性:将功能模块封装成函数,可以使代码更加模......
  • [二分图] 学习笔记
    定义无向图可以分成两个点集,集合内的点不相连通,不允许存在奇环//二分图的判定#include<bits/stdc++.h>usingnamespacestd;constintN=1e3+10,M=2e6+10;struct{ intto,next;}e[M];inttop,h[N],color[N],n,m;voidadd(intx,inty){ e[++top]......
  • HDU 3829 Cat VS Dog 猫和狗(二分图)结题报告
    听学长说这道题很ex,但是思路想到的话还是挺简单的。可能是受上一道题(放置机器人)的启发,也是找互相冲突的点连线。但是并不是完全一样(废话)放置机器人那道题是找到冲突点连线后直接求最大匹配即可。这道题稍微把思路变换一下,求出最大完美匹配数\(n\)后,说明有\(n*2\)个人的喜好......
  • Nginx基本概念
    安装Nginx源码安装环境准备安装GCC编译器Nginx是使用C语言编写的程序,因此想要运行Nginx就需要安装一个编译工具。GCC就是一个开源的编译器集合,用于处理各种各样的语言,其中就包含了C语言。使用命令yuminstall-ygcc来安装安装成功后,可以通过gcc--version来查看gcc是否......
  • 泛基因组的概念
     001、Tettelin等在2005首次在细菌的研究中提出泛 基因组(pan-genome)的概念,指整个物种基因组序列的非冗余集合,其中包括存在于该物种几乎所有个体中的核心基因组(coregenome)和仅在部分个体中存在的可变基因组(accessory/variable/dispensablegenome)。 reference:Tet......
  • IT初学者在哪里可以发现一些好的基础视频呢?
     经常碰到一些粉丝说参加了某某培训机构的培训课程,什么都没写会,还白白打上了一两万块。想到这里挺为他们心痛的,我认为你如果是初学者,必然是没什么基础的;为了薪资高而学习IT行业,而没有浓厚的兴趣,很难在参加培训的脱产班3个月的时间内学习比较深入的东西。如果你是IT兴趣爱好者,而且......
  • 【机器学习之路】开山篇 | 机器学习介绍及其类别和概念阐述
    ......
  • shiro框架基本概念介绍
    什么是Shiro:Shiro是一个强大灵活的开源安全框架,可以完全处理身份验证、授权、加密和会话管理Shiro的核心功能包括:身份验证(Authentication):验证用户的身份,确保用户是合法的。授权(Authorization):控制用户对系统资源的访问权限,限制用户只能访问其被授权的部分。会话管理(Ses......