程序员经验分享-hwhale

给定最大匹配，找到二分图的最小顶点覆盖

2023-12-25

我似乎找到了一种算法，但无法理解它，我想知道你们中是否有人知道该算法的一般概要。

这是我在第 2 页找到的算法的链接

http://www.cse.iitb.ac.in/~sundar/cs435/lecture23.pdf http://www.cse.iitb.ac.in/~sundar/cs435/lecture23.pdf


算法很简单：

  1. 找到不匹配的顶点，将其标记为不包含在最小顶点覆盖中。
  2. 将该顶点的所有匹配邻居标记为包含在最小顶点覆盖中。
  3. 将上一步中的所有顶点配合视为不匹配的顶点并重复步骤 1。
  4. 如果递归结束，则从步骤 1 开始重复（即图的多个连通分量的情况）。
  5. 如果没有不匹配的顶点，则取出所有剩余的顶点对并以您喜欢的方式标记它们（请记住，对中的一个顶点必须 包含在最小顶点覆盖中，而其他一个必须不包含 包括）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

Graph

set

matching

bipartite

给定最大匹配，找到二分图的最小顶点覆盖 的相关文章

随机推荐

  • Tensorflow模型保存和加载

    如何像我们在 do keras 中所做的那样用模型图保存张量流模型 我们可以保存整个模型 权重和图表 并稍后导入 而不是在预测文件中再次定义整个图表 在喀拉斯 checkpoint ModelCheckpoint RightLane epo

  • 新手：了解 main 和 IO()

    在学习 Haskell 时 我想知道何时执行 IO 操作 我在几个地方发现了这样的描述 I O 操作的特殊之处在于 如果它们落入主函数中 就会执行它们 但在下面的示例中 greet 永远不会返回 因此不应打印任何内容 import Cont

  • 更改所有页面的文本方向

    我正在开发一个可以使用多种语言的网络项目 我已经完成了所有这些 我还有一件事 以英文显示时的页面是从左到右 我网站上的某些语言需要从右到左 请注意 我的问题是关于整个页面而不是字段中的文本 请问我该怎么做 我使用此代码来启动多种语言的线程

  • 如何在 Rails 4 中查询数组列？

    我找不到关于如何查询的好文章array columns在 Rails 中 我遇到需要查询 Rails 中的数组列 我从一篇教授如何进行基本查询的文章中找到here http blog arkency com 2014 10 how to s

  • 如何在 MySQL 中调度存储过程

    我有这个存储过程 例如 我如何以 5 秒的间隔运行它 就像删除时间戳超过一天的数据的例程一样 DROP PROCEDURE IF EXISTS delete rows links GO CREATE PROCEDURE delete row

  • 如何用零替换交叉表查询中的空值？

    基于 Access 中的以下 SQL TRANSFORM Sum Shape Length 5280 AS MILES SELECT ONSHORE AS Type Sum qry CurYrTrans Miles AS Total Of

  • Android 的 SceneKit 等效项是什么？ [关闭]

    Closed 这个问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 我创建了一个ARKit https developer apple com augmented rea

  • 有没有办法在 R Markdown 中的嵌入式 LaTeX 方程中使用 r 代码的结果

    有没有类似的命令 Sexpr可以在 R Markdown 文档中的嵌入式 LaTeX 方程中使用吗 我想用这样的东西形成一个简单的线性回归方程 hat Y Sexpr coef model 1 Sexpr coef model 2 cdot

  • 从android中的SeekBar获取值

    我如何从 a 获取值SeekBar 我有一个具有三个 SeekBar 的类的代码 PRICEbar 我想将这些 SeekBars 的值传递给下一个 Activity 屏幕 作为意图 我知道如何实现 OnClickListener 但如何提取

  • Django：DetailView从外键获取对象

    我的模型事件有一个基于类的 DetailView 并且想要显示通过外键相关的类别条目 模型 py class Event models Model name models CharField max length 50 def get ab

  • Subversion 中的 Mercurial：移动、重命名和标签

    我有一个具有以下布局的 subversion 存储库 svnrepo projectA trunk svnrepo projectA tags svnrepo projectA branches svnrepo projectB trunk

  • 如果显式使用同一模块中的类型，则 Prism 框架不会加载模块

    我们有一个使用 prism 5 框架的 WPF 应用程序 使用 DirectoryModuleCatalog 加载模块 同时 如果我引用引导程序所在的启动项目中的模块之一并使用其中的类型 则该模块将被跳过加载 看起来 prism 框架正在跳

  • 关于 Z3 for Java 的性能问题

    我在当前使用 Z3 for Java 的项目中遇到了一些性能问题 基本上我当前的大多数限制都非常简单 例如 f x 2 f y lt 3 f x lt 5 我正在使用整个项目共享的静态上下文和解算器实例 public class Const

  • 如何从服务器发送数据到Android？

    我正在开发一个项目 我希望我的服务器向我的应用程序发送一些数据 无需从移动设备调用 Web 服务 它就像一个网络面板 可以操作移动应用程序来添加数据 因此 当用户在网站中添加数据并单击 添加 时 应该将该数据添加到移动应用程序 如果移动设备

  • QEMU、无可启动设备、Linux 的 Windows 子系统

    我正在学习如何构建基本的操作系统内核https intermezzos github io https intermezzos github io 我已经创建了我的 iso文件 我现在正在运行qemu system x86 64 cdrom

  • 如何在“共享”（git 管理）Xcode 项目中使用“私有”.xcconfig？

    通常 我会使用现有的 xcconfig在某些子模块中 以简化 Xcode 工作区 或项目 中某些 git 子模块 或我自己的 Xcode 子项目 之一 的集成 这非常有效 并且减少了对可能存在的项目进行大量本地配置更改的需要在其自己的 或者

  • 将扁平化的键->值对转换为嵌套对象

    将以下键 gt 值对象 数组 转换为正确的 JSON 样式对象的最简单方法是什么 下面的示例将输入转换为图表 var input graph default seriesColor cccccc 3c3c3c graph default s

  • 软件安装时如何生成数据库后端？

    我开发了一个带有 SQL SERVER 后端的小型应用程序 并且还使用 Indigo Rose 安装工厂 8 0 为该应用程序制作了一个安装程序 我需要的是我想在应用程序安装过程中自动创建具有特定用户帐户的数据库后端 在安装程序之前 系统会

  • 使用一个查询通过 wp_query 搜索多个关键字

    我使用这个 wp query 来获取特定关键字的结果并按价格排序 我需要同时搜索多个关键词并返回结果并按产品价格排序 如何使用一个 wp query 实现这一点 例如有三个标题记录 我在这里很好谢谢我很好 谢谢我现在很好 如果我搜索文本 m

  • 给定最大匹配，找到二分图的最小顶点覆盖

    我似乎找到了一种算法 但无法理解它 我想知道你们中是否有人知道该算法的一般概要 这是我在第 2 页找到的算法的链接 http www cse iitb ac in sundar cs435 lecture23 pdf http www cs

热门标签