首页 > 代码库 > 最小路径覆盖
最小路径覆盖
最小路径覆盖
最小路径覆盖(path covering):是“路径” 覆盖“点”,即用尽量少的不相交简单路径覆盖有向无环图G的所有顶点,即每个顶点严格属于一条路径,路径的长度可能为0(单个点)。
最小路径覆盖数=G的点数-最小路径覆盖中的边数。应该使得最小路径覆盖中的边数尽量多,但是又不能让两条边在同一个顶点相交。
拆点:将每一个顶点i拆成两个顶点Xi和Yi。然后根据原图中边的信息,从X部往Y部引边。所有边的方向都是由X部到Y部。因此,所转化出的二分图的最大匹配数则是原图G中最小路径覆盖上的边数。
因此由最小路径覆盖数=原图G的顶点数-二分图的最大匹配数便可以得解。
最小路径覆盖
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。