二分图(Bipartite Graph)

这篇具有很好参考价值的文章主要介绍了二分图(Bipartite Graph)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、简介

二分图の定义

        二分图又叫二部图,是图论中的一种特殊模型。

        假设S=(V,E)是一个无向图。如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),就可以称图S为一个二分图。简单来说,就是顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。

二分图の匹配

        给定一个二分图S,在S的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。

        极大匹配是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。

        最大匹配是所有极大匹配当中边数最大的一个匹配。

        选择这样的边数最大的子集称为图的最大匹配问题。如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。
        完全匹配一定是极大匹配,但是极大匹配不一定是完全匹配。下图就是一个最大匹配。

二分图(Bipartite Graph)

 二分图の判断

       对于二分图的判断方法最常见的是染色法,就是对每一个点进行染色操作,只用黑白两种颜色,能不能使所有的点都染上了色且相邻两个点的颜色不同?如果可以那么这个图就是一个二分图,对于判断是否是一个二分图的方法可以用dfs和bfs两种方式去实现。代码参见“代码实现”部分。

二分图の最大匹配

        给定一个二分图S,在S的一个子图M中,M的边集中的任意两条边都不依附于同一个顶点,则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。

        首先要了解两个概念:

|交替路|从一个未匹配的点出发,依次经过未匹配边、匹配边、未匹配边....

|增广路|从一个未匹配的点出发,走交替路,到达了一个未匹配过的点。  

        对于求二分图最大匹配的算法可以用网络流去跑一个最大流求解,还可以用二分图的常见算法匈牙利算法,这个算法的核心就是去找未匹配的点,然后从这个点出发去寻找增广路,因为增广路有几个主要的特点:

  • 增广路有奇数条边 。
  • 路径上的点一定是一个在X边,一个在Y边,交错出现。
  • 起点和终点都是目前还没有配对的点。
  • 未匹配边的数量比匹配边的数量多1。

        重点是第4点,我们可以根据此特性,把这条增广路中的匹配边改为未匹配边,把未匹配边改为匹配边,这样我们就可以使总匹配边数+1了,根据上面的图得出下图,很显然匹配边多了一条。

        代码见“代码实现”部分。

二、代码实现

“二分图の判断”配套代码:

BFS判断二分图

vector<int>G[maxn];//存边
int col[maxn];//标记顶点颜色
int n,m;//点和边的个数
bool bfs()
{
  queue<int>q;
  q.push(1);//放入第一个点
  memset(col,0,sizeof(col));
  col[1]=1;//先标记第一个点为1
  while(!q.empty())
  {
    int v=q.front();
    q.pop();
    for(int i=0; i<G[v].size(); i++)
    {
      int xx=G[v][i];
      if(col[xx]==0)//判断这个点是否标记过
      {
        col[xx]=-col[v];//没有标记过就标记上与v相反的颜色
        q.push(xx);
      }
      else
      {
        if(col[v]==col[xx])//如果颜色冲突说明不是二分图
        {
          return false;
        }
      }
    }
  }
  return true;
}

“二分图の最大匹配”配套代码

匈牙利算法代码

vector<int> G[maxn];//存边
int pre[maxn];//记录匹配点
bool vis[maxn];//标记是否匹配过
int n,m;//n个点 m条边
bool dfs(int x)
{
  for(int i=0; i<G[x].size(); i++)
  {
    int v=G[x][i];
    if(vis[v]==false)//判断是否标记过
    {
      vis[v]=true;
      if(pre[v]==-1||dfs(pre[v]))// 判断当前点是否匹配过 dfs为判断这个点能不能和其他的点匹配
      {
        pre[v]=x;
        return true;
      }
    }
  }
  return false;
}
int Fun()
{
  int sum=0;
  memset(pre,-1,sizeof(pre));
  for(int i=1; i<=n; i++)
  {
    memset(vis,false,sizeof(vis));//每次遍历都需要初始化
    if(dfs(i)) 
    {
        sum++;
    }
  }
  return sum;
}

参考文献:

干货|二分图详解https://www.zhihu.com/tardis/landing/m/360/art/89972891以上内容就是本文的全部内容啦!感谢阅读!文章来源地址https://www.toymoban.com/news/detail-413962.html

到了这里,关于二分图(Bipartite Graph)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • AI人工智能简介和其定义

    全称:人工智能(Artificial Intelligence) 缩写:AI / ai        亦称智械、机器智能,指由人制造出来的可以表现出智能的机器。通常人工智能是指通过普通计算机程序来呈现人类智能的技术。该词也指出研究这样的智能系统是否能够实现,以及如何实现。人工智能于一般教材中

    2023年04月18日
    浏览(42)
  • Spring IOC 入门简介【自定义容器实例】

    目录 相关导读 1. Maven专栏系列文章 2. Mybatis专栏系列文章 3. Spring系列专栏文章 前言 Spring简介 Spring体系结构 一、IOC控制反转思想 二、IOC自定义对象容器 1. 创建实体类,Dao接口,实现类 2. 创建配置文件bean.properties 3. 创建容器管理类 4. 创建StudentService类 5. 测试方法 6. 测试结

    2023年04月21日
    浏览(45)
  • Web3技术简介:重新定义互联网的未来

    在21世纪的数字时代,互联网已成为我们日常生活的不可或缺的一部分。然而,随着区块链和加密技术的快速发展,一个全新的互联网模型——Web3,正逐渐崭露头角。Web3不仅仅是技术的进步,它更是对传统互联网模型的挑战和革新,旨在构建一个更去中心化、安全、透明和用

    2024年04月27日
    浏览(38)
  • 【C++】命名空间 namespace 与 标准流 iostream ( 命名空间概念简介 | 命名空间定义 | 命名空间使用 | iostream 中的命名空间分析 )

    命名空间 namespace 又称为 名字空间 , 名称空间 , 名域 , 作用域 , 是 C++ 语言 对 C 语言 的扩展 之一 ; C++ 中的 命名空间 namespace 指的是 标识符 的 可见范围 , C++ 标准库中的 所有 标识符 , 都定义在 std 命名空间中 ; 命名空间 英文名称是 \\\" namespace \\\" , name 是 名字 , 名称 的意思 ,

    2024年02月12日
    浏览(41)
  • 【C++】构造函数分类 ① ( 构造函数分类简介 | 无参构造函数 | 有参构造函数 | 拷贝构造函数 | 代码示例 - 三种类型构造函数定义与调用 )

    C++ 构造函数可以分为以下几类 : 无参构造函数 : 最简单也是默认的构造函数 , 函数没有参数 , 如果创建一个对象 , 没有传入参数 , 调用的就是该类型的 构造函数 ; 有参构造函数 : 带参数的 构造函数 , 创建 实例对象 时 , 为成员变量提供初始值 ; 拷贝构造函数 : 拷贝现有 实例

    2024年02月07日
    浏览(39)
  • 图匹配(Graph Matching)入门学习笔记——以《Factorized Graph Matching》为例(一)

    这篇文章本身是图匹配经典论文《Factorized Graph Matching》的阅读笔记,后来发现该文介绍并串联了许多图匹配相关的知识,甚至可以看作一个小小的综述性文章,因此就作为图匹配的学习笔记了。因为笔者本人才疏学浅,对于图匹配也是刚刚开始接触,所以文章内容难免存在纰

    2024年01月20日
    浏览(40)
  • 图论(Graph theory)

    Graphic操作接口 操作接口 功能描述 操作接口 功能描述 e() 获取图的总边数 n() 顶点的总数 exits(v,u) 判断v,u两个顶点是否存在边 insert(v) 在顶点集 V 中插入新顶点 v remove(v,u) 删除从v 到u的 关联边 remove(v) 将顶点 v 从顶点集中删除 type(v,u) 边所属的类型(主要用于遍历树~) inDegree(v

    2024年04月27日
    浏览(29)
  • Graph Theory(图论)

    图是通过一组边相互连接的顶点的集合。     In this graph, V = { A , B , C , D , E } E = { AB , AC , BD , CD , DE } A graph consisting of finite number of vertices and edges is called as a finite graph.   Null Graph Trivial Graph Non-directed Graph Directed Graph Connected Graph Disconnected Graph Regular Graph Complete Graph Cycle Graph Cy

    2024年02月08日
    浏览(34)
  • Shader Graph入门

    目录 Shader Graph 简介 1. 什么是 Shader Graph 4. Shader Graph 界面 4.1 Shader Graph 窗口 4.2 Shader Graph 窗口操作方式 5. 使用 Shader Graph 编辑 Shader 通用步骤 6. Node 节点 6.1 节点概述 6.2 节点分类 7. 主堆栈 Master Stack 7.1 主堆栈 7.2 Context 上下文 7.3 Block Node 块节点 8. 示例中用到的节点 8.1 Gradie

    2023年04月13日
    浏览(37)
  • 图(Graph)详解 - 数据结构

    图(Graph)是由两个集合构成,一个是非空但有限的顶点集合V,另一个是描述顶点之间关系 ----- 边的集合E(可以是∅)。图可以表示为 G=(V,E)。每条边是一顶点对(v,w)且 v,w∈V。通常用 |V| 表示顶点的数量,用 |E| 表示边的数量。 🚀图是由顶点集合及顶点间的关系组成的

    2024年02月03日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包