首页 > 代码库 > 最小路径覆盖

最小路径覆盖

最小路径覆盖

    最小路径覆盖(path covering):是“路径” 覆盖“点”,即用尽量少的不相交简单路径覆盖有向无环图G的所有顶点,即每个顶点严格属于一条路径,路径的长度可能为0(单个点)。

    最小路径覆盖数=G的点数-最小路径覆盖中的边数。应该使得最小路径覆盖中的边数尽量多,但是又不能让两条边在同一个顶点相交。

    拆点:将每一个顶点i拆成两个顶点Xi和Yi。然后根据原图中边的信息,从X部往Y部引边。所有边的方向都是由X部到Y部。因此,所转化出的二分图的最大匹配数则是原图G中最小路径覆盖上的边数。

    因此由最小路径覆盖数=原图G的顶点数-二分图的最大匹配数便可以得解。

最小路径覆盖