Muk*_*pta 4 algorithm graph-theory graph bipartite graph-algorithm
我有一个断开的二分无向图.我想完全断开图表.只有我可以执行的操作是删除节点.删除节点将自动删除其边缘.任务是最小化要删除的节点数.图中的每个节点最多有4个边.
通过完全断开图形,我的意思是不应该通过链接连接两个节点.基本上是一个空边集.
我认为,你无法证明你的算法是最优的,因为事实上它并不是最优的.
要完全断开图形,最大限度地减少要删除的节点数,必须删除属于图形最小顶点覆盖的所有节点.搜索最小顶点覆盖通常是NP完全的,但对于二分图,存在多项式时间解.
在图中找到最大匹配(可能使用Hopcroft-Karp算法).然后使用König定理得到最小的顶点覆盖:
考虑一个二分图,其中顶点被划分为左(L)和右(R)集.假设存在最大匹配,将边缘划分为匹配(E_m)中使用的边缘和不匹配(E_0)的边缘.令T由来自L的所有不匹配顶点以及通过沿着E_0的边缘从左到右沿着从E_m的边缘向右到左的所有顶点组成.这实质上意味着对于L中的每个不匹配的顶点,我们将在E_0和E_m的边之间交替的路径中出现的所有顶点添加到T中.
然后(L\T)OR(R AND T)是最小顶点覆盖.