精华内容
下载资源
问答
  • Air Raid + Treasure Exploration 最小边覆盖: 最小路径覆盖: 有向无环图->二分图 传递闭包

    最小边覆盖

    边覆盖集:通俗地讲,所谓边覆盖集,就是G中所有的顶点都是E*中某条边的邻接顶点(边覆盖顶点),一条边只能覆盖2个顶点。


    注意:在无向图中存在用尽量少的边去“覆盖”住所有的顶点(注意:单独一个点没有与它相连的边,也算作一次边去覆盖这个点),所以边覆盖集有极小与最小的区别。
    极小边覆盖:若边覆盖E*中的任何真子集都不是边覆盖集,则称E*是极小边覆盖集。

    最小边覆盖:边数最小的边覆盖集称为最小边覆盖,通俗地讲,就是极小边覆盖中的最小的一个集合。


    最小边覆盖在二分图中的应用:最小边覆盖 = 最大独立集 = n - 最大匹配,这个是二分图上的一个性质。
    两个很小的点:必须要求原图为二分图;边覆盖集中可能有多条边覆盖同一个顶点,其实可以这条边说是为了覆盖另一个顶点而存在的。

    最小路径覆盖

    用尽量少的不相互交叉简单路径覆盖有向无环图G的所有结点(不交叉指的是原图,而非后来构造的二分图)。即覆盖点(同样地,在路径覆盖中单独一个点没有与它相连的边,也算作一次路径去覆盖这个点)。建立一个二分图模型,把所有顶点i拆成两个:X集中的i和Y集中的i',如果有边i->j,则在二分图中引入边i->j',结果就是最小路径覆盖 = N - 最大匹配数。(N为原图中结点数)

    最小路径覆盖和最小边覆盖不同,不要求给的图是二分图,而是要求是N×N的有向图,且不能有环,然后根据原图构造二分图,构造方法是将点一分为二,如:i分为i`和i``然后如果i和j有边,那么就在i`和j``之间连一条边。由此构成二分图。

    然后最小路径覆盖 = n-m,n为原图的点的个数,m为新造二分图的最大匹配。证明也是特别简单的,根据定义最小路径覆盖里要求同一个点只可以属于一条路径,即路径是不可以开叉的,如果在二分图里选两条有公共点的边那么反应在原图上就是路径有岔路了,所以二分图里选的边必须是无公共交点的,这就是转化到最大匹配了。
    (图片来源)
    上图中,对应左边的DAG建立构造右边的二分图,可以找到二分图的一个最大匹配M:1-3',3-4',那么M中的这两条匹配边怎样对应DAG中的路径的边?
    使二分图中一条边对应DAG中的一条有向边,1-3'对应DAG图中的有向边1->3,这样DAG中1就会有一个后继顶点(3会是1的唯一后继,因为二分图中一个顶点至多关联一条边!),所以1不会成为DAG中一条路径中的结尾顶点,同样,3-4'对应DAG中3->4,3也不会成为结尾顶点,那么原图中总共4个顶点,减去2个有后继的顶点,就剩下没有后继的顶点,即DAG路径的结尾顶点,而每个结尾顶点正好对应DAG中的一条路径,二分图中寻找最大匹配M,就是找到了对应DAG中的非路径结尾顶点的最大数目,那么原图DAG中顶点数-|M|就是DAG中结尾顶点的最小数目,即DAG的最小路径覆盖数.即上图中找到的最小路径覆盖集合为2, 1->3->4。

    若是题目要求可多次经过一个点的最小路径覆盖呢?如下图:

    (图片来源)

    此时构造二分图,得到的匹配答案是2,最小路径覆盖答案便是5-2=3。而对于可多次经过同一点来说正确答案明显是2。

    问题究竟出在哪里呢?其实就和这个交点2有关。既然边有相交,那么他们的连通性也应该连通下去。

    解决的办法是对原图进行一次闭包传递(通过Warshell传递闭包算法),于是便增加了四条边:1->3, 1->5, 4->3, 4->5,然后再去求最小路径覆盖。

    传递闭包概念:

    一个有n个顶点的有向图的传递闭包为:有向图中的初始路径可达情况我们存入邻接矩阵A,邻接矩阵中A[i,j]表示i到j是否直接可达,若直接可达,则A[i,j]记为1,否则记为0;有向图中i到j有路径表示从i点开始经过其他点(或者不经过其他点)能够到达j点,如果i到j有路径,则将T[i,j]设置为1,否则设置为0;有向图的传递闭包表示从邻接矩阵A出发,求的是所有节点间的路径可达情况,该T矩阵就为所要求的传递闭包矩阵。

    这时再求最大匹配数,匹配答案便是3,最小路径覆盖值为2,这是正确答案!


    最小路径覆盖例题1(POJ-1422):

    题意:一个镇里所有的路都是单向路且不会组成回路。派一些伞兵去那个镇里,要能够到达所有的路口,且超过一个 伞兵访问不交叉的路口(visits no intersection),其实题目应该是想表达伞兵访问路径时不能相互交叉,每个路口只能访问一次。每个在一个路口着陆了的伞兵可以沿着街去到其他路口。我们的任务是求出去执行任务的伞兵最少可以是多少个。

    代码:

    #include <algorithm>
    #include <string.h>
    #include <cstdio>
    using namespace std;
    const int maxn = 250;
    const int maxm = maxn*maxn;
    const int BAS = 120;
    struct node
    {
    	int v, next;
    } edge[maxm];
    int no, head[maxn];
    int n, m, ans;
    int match[maxn], vis[maxn];
    inline void init()
    {
    	no = 0; ans = 0;
    	memset(head, -1, sizeof head);
    	memset(match, -1, sizeof match);
    }
    inline void add(int u, int v)
    {
    	edge[no].v = v;
    	edge[no].next = head[u];
    	head[u] = no++;
    }
    int dfs(int cur)
    {
    	for(int k = head[cur]; k != -1; k = edge[k].next)
    	{
    		if(vis[edge[k].v]) continue;
    		vis[edge[k].v] = 1;
    		if(match[edge[k].v] == -1 || dfs(match[edge[k].v]))
    		{
    			match[edge[k].v] = cur;
    			return 1;
    		}
    	} 
    	return 0;
    }
    int main()
    {
    	int t, u, v;
    	scanf("%d", &t);
    	while(t--)
    	{
    		scanf("%d %d", &n, &m); init();
    		for(int i = 1; i <= m; ++i)
    		{
    			scanf("%d %d", &u, &v);
    			add(u, BAS+v);
    		}
    		for(int i = 1; i <= n; ++i)
    		{
    			memset(vis, 0, sizeof vis);
    			if(dfs(i)) ++ans;
    		}
    		printf("%d\n", n-ans);
    	}
    	return 0;
    }

    最小路径覆盖例题2(POJ-2594):

    题意:给一个有向无环图,有n个点,m条有向边。一个机器人可以从任意点开始沿着边的方向走下去。对于每一个机器人:走过的点不能再走过。对于每个点可被多个机器人走。问你最少用几个机器人可以走完所有的n个点,不同的机器人可以走相同的点(two different robots may contain some same point)。

    分析:路径可以相互交叉,所以就是最小路径覆盖+Warshell传递闭包。

    代码:

    #include <string.h>
    #include <cstdio>
    using namespace std;
    const int maxn = 505;
    bool G[maxn][maxn];
    int match[maxn], vis[maxn]; 
    int n, m;
    void Warshell()
    {
    	//进行求解最小路径覆盖问题前提是有向无环图
    	//所以不会出现传递闭包形成G[i][i]=1的情况 
    	for(int i = 1; i <= n; ++i)
    	for(int j = 1; j <= n; ++j)
    	if(!G[i][j])
    	for(int k = 1; k <= n; ++k)
    	if(G[i][k] && G[k][j])
    	{
    		G[i][j] = 1;
    		break;
    	}
    }
    int dfs(int cur)
    {
    	for(int i = 1; i <= n; ++i)
    	{
    		if(!G[cur][i] || vis[i]) continue;
    		vis[i] = 1;
    		if(match[i] == -1 || dfs(match[i]))
    		{
    			match[i] = cur;
    			return 1;
    		}
    	}
    	return 0;
    }
    int main()
    {
    	int u, v, ans;
    	while(scanf("%d %d", &n, &m) && (n || m))
    	{
    		memset(G, 0, sizeof G);
    		memset(match, -1, sizeof match);
    		for(int i = 1; i <= m; ++i)
    		{
    			scanf("%d %d", &u, &v);
    			G[u][v] = 1;
    		}
    		Warshell(); ans = 0;
    		for(int i = 1; i <= n; ++i)
    		{
    			memset(vis, 0, sizeof vis);
    			if(dfs(i)) ++ans;
    		}
    		printf("%d\n", n-ans);
    	}
    	return 0;
    }

    继续加油~

    展开全文
  • poj 3020题目大意 一个矩形中,有N个城市’*’,现在这n个城市都要覆盖无线,若放置一个基站... 最小路径覆盖数 = 顶点数 - 最大匹配数 下面列举几个二分图问题的常用定理: 定理1:最大匹配数 = 最小点覆盖数(这是

    poj 3020

    题目大意

    一个矩形中,有N个城市’*’,现在这n个城市都要覆盖无线,若放置一个基站,那么它至多可以覆盖相邻的两个城市。问至少放置多少个基站才能使得所有的城市都覆盖无线?

    分析

    在这道题上卡了很久,才接触二分图也没什么好的思路。这道题需要用到一个定理:

    二分图最小边覆盖 = 两边顶点数 - 最大匹配数
    无向图的最小边覆盖 = (二分图两边顶点数 - 二分图的最大匹配数)/2.

    下面列举几个二分图问题的常用定理:

    定理1:最大匹配数 = 最小点覆盖数(这是 Konig 定理)
    定理2:二分图最小边覆盖 = 顶点数 - 最大匹配数
    定理3:最大匹配数 = 最大独立数

    这些定理是需要掌握的基础,但问题的关键是如何将要解决的问题归约成我们熟悉的模型。也就是如何建图的问题。
    基站将两个城市覆盖可以看成是在两个城市间连了一条边,这样问题变成了一个图论问题,对于图中的每一个联通分量,至少用多少边才能将所有点都覆盖,这就是比较典型的无向图最小边覆盖问题。

    接下来讲如何将无向图最小边覆盖问题转化为二分图的最小边覆盖问题的。

    比如原来的无向图是这样的:
    这里写图片描述
    这里经过一个叫做拆点的操作,其实就是将原图复制了一份,显而易见,拆点后图的最小边覆盖数是原图的两倍。注意观察里面点的命名,一条边总是连接一个实点和一个虚点(二分图一条边总是连接左边的点后右边的点)
    这里写图片描述
    实际上经过拆点之后图变成了一个二分图(只是重排了一下点的位置,但它们之间的拓扑关系不变)
    这里写图片描述
    这个二分图和拆点后的无向图的最小边覆盖数是相等的,所以也是原无向图的两倍。

    注意

    用以上方法思考之后我产生一个问题,对于那些孤立的城市(旁边没有其他城市),它也需要一个基站来覆盖,但在无向图的建图中是没有边的,为什么以上程序还能正常运行呢?

    仔细想了想后发现其实这是没有问题的,因为对于孤立的点这个联通分量,也是满足:
    二分图最小边覆盖 = 两边顶点数 - 最大匹配数=2
    无向图的最小边覆盖 = (二分图两边顶点数 - 二分图的最大匹配数)/2=1
    是没有问题的。

    不知道很多博客里为什么是最小路径覆盖

    代码

    #include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<cstdlib>
    #include<queue>
    using namespace std;
    int T;
    int B,A;
    int grid[100][100];
    int find_node[100][100];
    int mat[500][500];//储存二分图的边
    int link[500];//与y节点相配对的x节点
    int visit[600];//y节点是否被配对了
    int nodecount=0;
    bool Can(int t)
    {
         for(int i=1;i<=nodecount;i++)
         {
               if(mat[t][i]==1 && visit[i]==0)
               {
                    visit[i]=1;
                    if(link[i]==-1 || Can(link[i]))
                    {
                        link[i]=t;
                        return 1;
                    }
               }
         }
         return 0;
    }
    int Match()
    {
          int ans=0;
          for(int i=1;i<=nodecount;i++)
          {
                memset(visit,0,sizeof(visit));
                if(Can(i))ans++;
          }
          return ans;
    }
    void Build()
    {
          for(int j=B;j>=1;j--)
          {
                for(int i=1;i<=A;i++)
                {
                      if(grid[i][j]==1)
                      {
                          if(grid[i+1][j]==1){mat[find_node[i][j]][find_node[i+1][j]]=1;mat[find_node[i+1][j]][find_node[i][j]]=1;}
                          if(grid[i][j-1]==1){mat[find_node[i][j-1]][find_node[i][j]]=1;mat[find_node[i][j]][find_node[i][j-1]]=1;}
                      }
                }
          }
    }
    int main()
    {
         scanf("%d",&T);
         char c;
         while(T--)
         {
               nodecount=0;
               memset(mat,0,sizeof(mat));
               memset(grid,0,sizeof(grid));
               memset(link,-1,sizeof(link));
               scanf("%d%d",&B,&A);
               for(int j=B;j>=1;j--)
               {
                   getchar();
                   for(int i=1;i<=A;i++)
                   {
                        scanf("%c",&c);
                        if(c=='*')
                        {
                              find_node[i][j]=++nodecount;
                        }
                        grid[i][j]= c=='*' ? 1: 0;
                   }
               }
               Build();
               cout<<(nodecount*2-Match())/2<<endl;
         }
    }
    
    展开全文
  • 换言之,如果原本总共有n+m个点,最大匹配数是k(即覆盖前2*k个点得最小边数为k),那么剩余的点的个数为n+m-2*k,即需要用n+m-2*k条边去覆盖,因此总共需要n+m-2*k+k==n+m-k条边去覆盖,即最小边覆盖== 总 顶点数-...

    先说概念:

    1、最小顶点覆盖:用最少的点覆盖所有的边(只要边的一个端点被选取,即算“被覆盖”);

    2、最大独立集:不直接相连的点的最大个数;

    (注意:最大独立集是一个点集,其中的点两两不直接相连(独立集)、且在所有独立集中点数最多,但是我们一般只求其元素个数(即点数))

    3、最小边覆盖:用最少的边覆盖所有的点。

    由于二分图不存在孤立点(即无边相连的点),上述问题必定有解。


    举个例子

    对于上面这个二分图,

    最小顶点覆盖是3,把左边三个点取完是一种可行解。有什么规律呢?设想一下,一条边要被覆盖,那么它两个端点至少有一个被取;所有边要被覆盖,即最小点覆盖,要保证每条边都至少被取了其中一个端点。这和二分图最大匹配是不是相似?如果当前存在一个匹配,剩下的未匹配点中有两点直接相连(即该边两端点都未取),那么它一定不是最大匹配;反之,若为最大匹配,其必定不存在未被覆盖的边。故最小点覆盖==最大匹配数,这即是Konig定理。

    最小边覆盖是4,取1-3、2-1、2-4、3-2是一种可行解。要探究它与最大匹配的关系,我们还是先看一看它的一些性质。首先,在最优的情况下,一条边可以覆盖两个点,且选取这条边前,这两个点是不相匹配的;那么根据贪心的原则,我们可以先取一次最大匹配,这时选取出来的每条边都匹配(覆盖)了两个点。剩下的点怎么办呢?这时每条边只能覆盖一个点了。换言之,如果原本总共有n+m个点,最大匹配数是k(即覆盖前2*k个点得最小边数为k),那么剩余的点的个数为n+m-2*k,即需要用n+m-2*k条边去覆盖,因此总共需要n+m-2*k+k==n+m-k条边去覆盖,即最小边覆盖==顶点数-最大匹配。

    (另外,正如前文所说,因为二分图没有孤立点,必定存在最小边覆盖;因为最终未匹配的点必定存在与之相连并未使用的边)

    最大独立集也是4,取右边整个集合是一种可行解。根据定义:最大独立集中的点相互之间无边相连,故它们不存在匹配关系。那么可以简单地理解成:把最大匹配中的点以及与它们相连的边中砍掉,剩下的就是孤立点了。因此,最大独立集==总点数-最大匹配==最小边覆盖。

    展开全文
  • 二分图之最小边覆盖(poj3020)

    千次阅读 2014-07-17 09:39:43
    基本裸的最小边覆盖。 分析: 最小边覆盖 = 点总数 - 最大匹配 所以就是转化为求最大匹配。 跟前面一道题目很相似,也是相同的建图方法,奇偶性建图。 #include #include #include #include #...

    题目:poj3020


    题意:给出一个图,让你用最少的1*2的纸片覆盖掉图中的所有*出现过的地方。基本裸的最小边覆盖。


    分析:

    最小边覆盖 = 点总数 - 最大匹配

    所以就是转化为求最大匹配。


    跟前面一道题目很相似,也是相同的建图方法,奇偶性建图。


    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    const int N = 1200;
    #define Del(x,y) memset(x,y,sizeof(x))
    int map[N][N],link[N],vis[N],vlink[N];
    char path[50][50];
    int line[50][50];
    int n,m,t,tmp1,tmp2;
    bool dfs(int x)
    {
        for(int i=1; i<tmp2; i++)
        {
            if(map[x][i]==1 && vis[i]==0)
            {
                vis[i]=1;
                if(link[i]==-1 || dfs(link[i]))
                {
                    link[i]=x;
                    return true;
                }
            }
        }
        return false;
    }
    void solve()
    {
        int ans=0;
        Del(link,-1);
        for(int i=1; i<tmp1; i++)
        {
            Del(vis,0);
            if(dfs(i))
                ans++;
        }
        //printf("%d\n",ans);
        printf("%d\n",tmp1+tmp2-ans-2);
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        //freopen("Input.txt","r",stdin);
        while(T--)
        {
            scanf("%d%d",&n,&m);
            Del(path,0);
            for(int i=1;i<=n;i++)
            {
                getchar();
                for(int j=1;j<=m;j++)
                    scanf("%c",&path[i][j]);
            }
            Del(line,-1);
            tmp1=1,tmp2=1;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    if(path[i][j]=='*')
                    {
                        if((i+j)%2==0)
                            line[i][j]=tmp1++;
                        else
                            line[i][j]=tmp2++;
                    }
                }
            }
    
            Del(map,0);
            for(int i=1; i<=n; i++)
            {
                for(int j=1; j<=m; j++)
                {
                    if(path[i][j]=='*' && (i+j)%2==1)
                    {
                        if(line[i-1][j]>=1)
                            map[line[i-1][j]][line[i][j]]=1;
                        if(line[i+1][j]>=1)
                            map[line[i+1][j]][line[i][j]]=1;
                        if(line[i][j-1]>=1)
                            map[line[i][j-1]][line[i][j]]=1;
                        if(line[i][j+1]>=1)
                            map[line[i][j+1]][line[i][j]]=1;
                    }
                }
            }
            solve();
        }
        return 0;
    }
    


    展开全文
  • 最小边覆盖:用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点; 最大独立集:实质是个点集,这个集合里的点无论怎样都两两相连不到一起,满足这个要求的点数最少的一个。 1、二分图中最小点覆盖等于最大...
  • 最小边覆盖 = 最大独立集 = |V| - 最大匹配数 这个是在原图是二分图上进行的 最小路径覆盖和最小边覆盖不同,不要求给的图是二分图,而是要求是N x N的有向图,不能有环,然后根据原图构造二分图,构造方法是将点...
  • 对于图G=(V,E)中的一个点覆盖是一个集合S⊆V使得每一条至少有一个端点在S中。最小点覆盖:就是中点的个数最少的S集合。 普通图的最小点覆盖数好像只能用搜索解,没有什么比较好的方法(可能我比较弱。。)所以在...
  • 匹配:实质上是二分图中的一个集,集中出现的点不会重合,比如有a-b了,就不会有a-c了,要是有了a就重合了 最大匹配:这个集的数目最大的那个匹配   匈牙利算法—— 增广路:一条在X和Y之间交错的路
  • 最大匹配: 匹配:在图论中,一个「匹配」...对于图G=(V,E)中的一个点覆盖是一个集合S⊆V使得每一条至少有一个端点在S中。 最小点覆盖:就是中点的个数最少的S集合。  结论: 二分图的最小点覆盖数=该...
  • 最小边覆盖:实质是个边集,这个集合里的边能覆盖所有的点,最小边覆盖是满足这个要求的所有边集中边数最少的一个。 这里顶点数等于总的顶点数,是二分图两边的顶点数,不是一边。 证明:...
  • 最小路径覆盖】 首先给出公式:DAG的最小路径覆盖数=DAG图中的节点数-相应二分图中的最大匹配数. 一个PXP的有向图中,路径覆盖就是在图中找一些路径,使之覆盖了图中的所有顶点,且任何一个顶点有且只有一条路径...
  • 最小边覆盖:在一个二分图中,找出一些边,使这些边覆盖所有的顶点,且任何一个顶点有且只有一条边与之关联,这样的最小的边集合。 最小路径覆盖(不可相交):要求可以不是二分图,但是是有向无环图,将原图的点...
  • 最小边覆盖(原图是二分图)】:在图中找一些边,使之覆盖了图中所有顶点,且任何一个顶点有且只有一条边与之关联。最小边覆盖 = 最大独立集 = |V| - 最大匹配数 【最小顶点覆盖】:用最少的点(左右两边集合的...
  • 仅仅用于自己理解,若有共鸣,别太吐槽就...理解到这里其实才只是个开始,我想解决的是最大匹配与最小顶点覆盖数、最小边覆盖数、最大点独立集之间的关系是怎么得来的。首先是结论: 在任意图中:(《挑战》里的结论)
  • 写这篇博客有两个原因,一是由于网上对这些结论的解释和证明太模糊,有些甚至是错的(有的人没分清楚最小路径覆盖和最小边覆盖,用错误的证明来推出结论)。二也是为了纪念人生头一次区域赛没拿奖吧(少做的一道题就是...
  • 无向图的最小边覆盖

    千次阅读 2013-04-12 09:01:00
    边覆盖的定义: 无向图G(V,E)边覆盖的求解步骤: 1.将无向图拆点,即若在无向图中存在节点i,则将节点i拆为i1,i2分别位于二分图的X部和Y部.若存在边ij,则连接二分图的i1j2,i2j1。 2.原无向图中的节点...
  • 最小边覆盖 = 最大独立集 = |V| - 最大匹配数 这个是在原图是二分图上进行的 最小路径覆盖和最小边覆盖不同,不要求给的图是二分图,而是要求是N x N的有向图,不能有环,然后根据原图构造二分图,构造方法是...
  • 最小边覆盖:实质是个边集,这个集合里的边能覆盖所有的点,最小边覆盖是满足这个要求的所有边集中边数最少的一个。 个人理解:关于最小边覆盖的理解,其实就是最大匹配的边数(能覆盖两个点的先覆盖上)+单个的点...
  • 最小路径覆盖和最小边覆盖不同,不要求给的图是二分图,而是要求是PXP的有向图,不能有环,即有向无环图。然后根据原图构造二分图,构造方法是将点一分为二(拆点),v分为v*和v**然后如v*和u**有边,那么就在v*和u*...
  • 鉴于我一直没有分清楚最小边覆盖与最小路径覆盖的关系,于是我就写写总结。 边覆盖集:通俗地讲,所谓边覆盖集,就是G中所有的顶点都是E*中某条边的邻接顶点(边覆盖顶点),一条边只能覆盖2个顶点。 注意:在无向...
  • 最小边覆盖= 最大独立集 = |V| - 最大匹配数 这个是在原图是二分图上进行的 最小路径覆盖和最小边覆盖不同,不要求给的图是二分图,而是要求是N x N的有向图,不能有环,然后根据原图构造二分图,构造方法是将点...
  • 前言:  有自己写的,有摘的别人的,前面是摘的,也是无心整理,出错是难免的,反正我都不会证明,智人见...或者说是“点” 覆盖了所有“”。。极小点覆盖(minimal vertex covering):本身为点覆盖,其真子集都不是
  • 最小边覆盖...
  • 覆盖集:无向图G的一个点集,使得该图中所有都至少有一点端点在该集合内。 b.点独立集:无向图G的一个点集,使得任两个在该集合中的点在原图中不相邻。 最大独立集:点独立集中元素个数最大的独立集,那么...
  • POJ 3020 最小边覆盖

    千次阅读 2012-04-10 09:52:55
    看到是两两连边不由得想起二分图匹配,实际上就是用最少的边覆盖所有的点的问题,我觉得最小边覆盖实际上就是最小路径覆盖的一个特殊情况,只不过要求必须是二分图才行而最小路径覆盖只要是PxP的有向图就行。...
  • 最小边覆盖 = 最大独立集 = |V| - 最大匹配数 这个是在原图是二分图上进行的 最小路径覆盖和最小边覆盖不同,不要求给的图是二分图,而是要求是N x N的有向图,不能有环,然后根据原图构造二分图,构造方法是...
  • 对于(a)可以想一下 我们要令最大匹配加边变成最小边覆盖 设最大匹配了x 那么覆盖了x条边 就要覆盖剩下的n-2x个点 而剩下用来覆盖的边只能覆盖一个点 所以需要n-2x条 最小边覆盖就是n-x了 对于(b) 借助这些...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 36,603
精华内容 14,641
关键字:

最小边覆盖