首页 > 其他分享 >关于二分图上的最大匹配、最小点覆盖、最大独立集以及最大权闭合子图的联系

关于二分图上的最大匹配、最小点覆盖、最大独立集以及最大权闭合子图的联系

时间:2024-08-08 21:05:12浏览次数:14  
标签:二分 最大 覆盖 点权 子图 最小 图上

  1. 没有点权和边权的时候,不讨论最大权闭合子图,最大匹配=最小点覆盖=点数-最大独立集

    最小点覆盖=点数-最大独立集:这个很好理解,考虑只有一条边的二分图的情况,点覆盖要求两个端点至少选一个,独立集要求两个端点最多选一个,是互补的关系,这意味着一个合法点覆盖的点集与一个合法独立集的点集一一对应,所以最小点覆盖的方案取反就得到最大独立集的方案。这个性质在一般图上仍然成立,不依赖于二分图的结构。

    最大匹配=最小点覆盖:这里利用网络流的概念简单理解。二分图内原来的边按左指向右定向且容量为无穷,从源点向左部的所有点连边,从右部的所有点向汇点连边,新连边容量为 1,此时一个流对应一个匹配,一个割对应一个点覆盖,而又有最大流=最小割,自然有最大匹配=最小点覆盖。

  2. 只有边权的时候,只有最大匹配有意义。此时就从最大流的模型变成了最大费用流的模型。

  3. 只有点权的时候,不考虑最大匹配,最大权闭合子图在这里特指左边都是正点权,右边都是负点权,边从左连向右的时候的二分图的最大闭合子图的点权和,有最小权点覆盖=总点权-最大权独立集=右部点权和+最大权闭合子图

    首先最小权点覆盖和1.中描述的分析方法相同,由于一个割对应一个点覆盖,只要将容量改为点权,那么割的容量就是点覆盖的值了。与2.中描述的最大权匹配会被加强为费用流不同,最小权点覆盖仍仅需要求解最小割

    然后我们整体地解释这个等式。

    现在有一个二分图,点有点权,点权全部是正的。现在约定一条边表示它所连接的两个端点不能同时选,求能选出的最大点权和,这是最大权独立集的模型。

    同样的二分图,同样的要求,但我事先将所有点的点权拿走表示全选,然后把所有点权置负表示选择这个负权意味着退回之前拿的点权,此时一条边的含义转化为至少选一个点退回,这是最小权点覆盖的模型。

    如果上一次事先拿点权时只拿了右边的点权表示咱且选择右边的所有点,然后把右边的点权置负表示选择这个负权意味着退回之前拿的右部点,现在一条边的含义就变为了如果选择了左边的正点权,就必须选择右边的负点权表示退回这个点,这是最大权闭合子图的模型。

    第一种情况实际求解的时候是直接取反然后用最小割求解最小点覆盖,而第三种情况的一般图标准做法也是先拿走所有正权点求最小割,总的来说三种情况本质相同,都是在做最小割,最终建的图都是一样的。

标签:二分,最大,覆盖,点权,子图,最小,图上
From: https://www.cnblogs.com/nkxjlym/p/18349750

相关文章

  • 最大匹配、最小顶点覆盖、最大独立集、最小路径覆盖(转)(再转)
    在讲述这两个算法之前,首先有几个概念需要明白:二分图:二分图又称二部图,是图论中的一种特殊模型。设G=(V,E)是一个无向图,如果顶点V可以分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(iinA,jinB),则称图G是二分图。......
  • Vue2和Vue3中的生命周期钩子图示
    原up写的非常简单易懂,还有简单代码示例:reference:https://cloud.tencent.com/developer/article/1514771一、Vue2和Vue3中的生命周期附原图:......
  • java 时间段划分 1.把一个时间段划分为 整天 和非整天的时间段 2. 把List<Loca
     时间段划分  1.把一个时间段划分为整天和非整天的时间段  例如: "2024-07-1108:30:00" ~   "2024-07-2308:30:00";例如 完整的日期:2024-07-122024-07-132024-07-142024-07-152024-07-162024-07-172024-07-182024-07-192024-07-202024-07-21202......
  • 雷达气象学(8)——反射率因子图分析(非气象回波篇)
    目录8.0雷达回波的分类8.1地物回波8.2海浪回波8.3干扰回波(同波长干扰)8.4生物回波8.5超折射回波8.6旁瓣回波8.0雷达回波的分类雷达回波可分为气象回波和非气象回波:\[雷达回波\begin{cases} 气象回波\begin{cases} 层状云降水回波\\ 积状云降水回波(对流性降水回......
  • C语言入门基础题:最大公约数(三个数间取最大公约数)
    1.题目描述输入三个正整数x,y,z,求它们的最大公约数(GreatestcommonDivisor)g:最大的正整数g>=1满足x,y,z都是g的倍数,即(x modg)=(ymodg)=(zmodg)=0。2.输入格式输入一行三个正整数x,y,z。3.输出格式输出一行一个整数g,表示x,y,z的最大公约数,4.输入......
  • 升级 Windows AD 域控制器的基本步骤和注意事项,帮助你顺利进行升级并减少潜在的中断风
    简单的初级教程大纲,帮助你理解如何升级WindowsAD域控制器:1. 准备阶段评估当前环境确认当前域控制器的操作系统版本和硬件配置。确保域控制器上的所有关键服务和应用程序支持升级后的操作系统版本。备份使用系统备份工具(如WindowsServerBackup)备份当前域控制器......
  • 情绪,往往是工作中最大的阻碍
    按照昨天的计划,我今天开始启动番茄钟了,上午完成的还不错,而且因为内心比较平静,而且也能静下心来做事,进展得比较顺利,而下午的时候,明显心态没有上午平静,变得有点儿浮躁不安,不会有不想做事的情绪,但是很容易分心,尽管开启了番茄钟,但是依然不能把每一个番茄钟的时间都花在工作上。 ......
  • 雷达气象学(7)——反射率因子图分析(气象回波篇)
    从本篇文章开始介绍反射率因子图(即雷达回波强度图)的分析与识别方法。目录7.0雷达回波的分类7.1层状云降水回波7.2积状云降水回波(对流性降水回波)7.3层积混合降水回波7.4零度层亮带7.5晴空回波7.0雷达回波的分类雷达回波可分为气象回波和非气象回波:\[雷达回波\begin{cas......
  • 【学习笔记】Matlab和python双语言的学习(最大最小化规划)
    文章目录前言一、最大最小化规划二、选址问题三、代码实现----Matlab1.Matlab的`fminimax`函数2.Matlab代码四、代码实现----python总结前言通过模型算法,熟练对Matlab和python的应用。学习视频链接:https://www.bilibili.com/video/BV1EK41187QF?p=28&vd_sour......
  • 数论——绝对素数、素数筛法、埃氏筛法、欧拉筛法、最大公约数
    绝对素数绝对素数是指一个素数在其十进制表示下,无论是从左向右读还是从右向左读,所得到的数仍然是素数。例如,13是一个素数,从右向左读是31,31也是素数,所以13是一个绝对素数。#include<iostream>#include<cmath>usingnamespacestd;boolisPrime(intnum){if(......