二部图最小顶点覆盖算法
我试图找出一种算法来寻找二部图的最小顶点覆盖。
我在考虑一个解决方案，将问题简化为二部图中的最大匹配。众所周知，可以使用从bip创建的networ中的最大流量来找到它。图表
最大匹配M应该决定最小。顶点覆盖C，但我无法处理选择要设置C的顶点。假设bip。图有部分X、Y，作为最大匹配边endpoint的顶点在集合A中，那些不属于B的顶点。
我会说，我应该为M到C中的边选择一个顶点。特别是M中的边e的endpoint，它连接到集合B中的顶点，否则，如果它只连接到A中的顶点，这并不重要。不幸的是，这个想法通常不起作用，因为我的算法中可以找到反例，因为A中的顶点也可以通过M中包含的顶点以外的其他边连接。
任何帮助都将受到感谢。
共有1个答案
Kőnig定理证明正是这样做的——从二部图的最大匹配中构建最小顶点覆盖。
假设你有一个二部图，在X和Y之间分开。
正如您所说，首先您必须找到最大匹配（例如，可以使用Dinic算法实现）。让我们调用此最大匹配。
然后构造最小顶点覆盖：
- 在X中查找不匹配顶点集（可能为空），即未连接到M中的任何边
维基百科的文章详细介绍了如何证明K确实是最小顶点覆盖。
1或Y，两者都是对称的
-
我试图理解如何将寻找树的最小顶点覆盖的问题表述为一个动态规划问题，但遇到了一些麻烦。对我来说，涉及深度优先搜索的非动态规划公式具有最直观的意义。从本质上讲，这涉及到对叶节点进行DFS，包括最小大小顶点覆盖中的父节点，并重复到根节点。伪代码是这样的： 我从这里得到的动态规划公式如下： 我想我理解子问题的思想是计算根植于每个顶点的子树的最小大小顶点复盖，包括复盖中的那个顶点，并从复盖中排除那个顶点。我
-
将求解第一个点的第一个圆放置在适当位置。 通过检查这两个点之间的距离是否小于2*r来求解最小圈数中的第二个点。并继续处理所有n个点。我认为是贪婪算法，但它是最优的，线性的吗？
-
我需要为以下问题找到一种“动态编程”的解决方案： 完美二叉树，T=（V，E）-（每个节点只有两个子节点，除了叶子） V=V（蓝色）∪ V（黑色）。V（蓝色）∩ V（黑色）=∅. （换句话说，树中的一些顶点是蓝色的） 树根'r'. 整数k 顶点V'V的子集，它是T的顶点覆盖，并且|V'∩V（蓝色）|=k。（换句话说，覆盖V'包含k个蓝色顶点） 合法解V'的值是集合中的顶点数=|V'|。为了方便起见，
-
}
-
问题内容： 我是django的新人。 我想创建一个自定义窗口小部件。 forms.py： widget.py： project / widgets / filter.html： 但是它不会呈现新模板，而是仍然呈现旧方法。 你能给我一些提示吗？ 问题答案： Django版本 <1.11： 小部件必须实现该方法才能呈现不同的模板： Django 1.11版： 在渲染器的文档中，我们可以找到以下内容：
-
我在leetcode中遇到了一个名为“二叉树相机”的问题。 我在想如何处理这个类似的问题：- 你必须把摄像机放在一个图的节点上，这样整个图就被覆盖了。一个节点上的摄像机监视它的所有近邻节点和它自己。找到覆盖所有节点所需的最小摄像机数量。