广元市楚河网络科技有限公司
首页 | 联系方式 | 加入收藏 | 设为首页 | 手机站

产品目录

联系方式

联系人:业务部
电话: 00164-826657
邮箱:service@tanaosot.com

当前位置:首页 >> 新闻中心 >> 正文

【关于DAG图的一些常用知识点】

字号:
摘要:【关于DAG图的一些常用知识点】

概念: DAG图 就是有向无环图. (也可以看做一棵有向树)[注意图不一定是连通的]。 一般要么是题目中给你提供这样的图,分辨也很简单就是 有向边并且无环 (重边的话要考虑会不会影响就够了),要么就是 用强连通分量scc+缩点来自己构建一个DAG图。 因为DAG有很多性质并且结构简单,所以能够化为DAG图当然首选。

如果题目给了一个DAG图,可以考虑如下方向 :
1 > . topo序来维护DP处理 。
例如
1 DAG图的最长路的题解
2 CF919D 题解
上面两个都是比较经典的问题。

2 > 考虑二分图
DAG图可以化为一个二分图,将每个顶点拆分为两个ax,ay,如果有a->b边,那么在二分图中建边ax->by 。(其实就是和网络流中的拆点了)。

1.DAG图最小不相交路径覆盖 (有几个弱连通的路径)
eg HDU 3861 The King’s Problem
poj 1422 Air Raid
· 定义:用最少的不相交路径覆盖所有顶点。
·定理:把原图中的每个点V拆成Vx和Vy,如果有一条有向边A->B,那么就加边Ax->By。这样就得到了一个二分图,最小路径覆盖=原图的节点数-新图最大匹配。
·简单证明:一开始每个点都独立的为一条路径,总共有n条不相交路径。我们每次在二分图里加一条边就相当于把两条路径合成了一条路径,因为路径之间不能有公共点,所以加的边之间也不能有公共点,这就是匹配的定义。所以有:最小路径覆盖=原图的节点数-新图最大匹配。

2.DAG图最小可相交路径覆盖
eg poj 2594 Treasure Exploration
定义:用最小的可相交路径覆盖所有顶点。
算法:先用floyd求出原图的传递闭包,即如果a到b有路,那么就加边a->b。然后就转化成了最小不相交路径覆盖问题。
·简单证明:为了连通两个点,某条路径可能经过其它路径的中间点。但是如果两个点a和b是连通的,只不过中间需要经过其它的点,那么可以在这两个点之间加边,那么a就可以直达b,不必经过中点的(实现了“跳跃”),那么就转化成了最小不相交路径覆盖。
3> 考虑偏序集
对于DAG图来说,是符合偏序集的定义的,所以我们可以将DAG图所描述的集合称为偏序集.
链:一条链是一些点的集合,链上任意两个点x, y,满足要么 x 能到达 y ,要么 y 能到达 x 。(每个链都可以看作一个弱连通)
反链:一条反链是一些点的集合,链上任意两个点x, y,满足 x 不能到达 y,且 y 也不能到达 x 。
定理1 令(X,≤)是一个有限偏序集,并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。
其对偶定理称为Dilworth定理:
定理2 令(X,≤)是一个有限偏序集,并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。
最大独立集(最大反链)=最小链的划分(最小不相交路径覆盖)。

  1. 如果要求最少的链划分数,根据上述定理我们知道只需要求出来其大反链的长度就可以了,而其最大反链长度又可以通过最小不相交路径的覆盖来求 。
  2. 如果要求最少的反链划分数,根据上述定理我们可以知道只需要求出来其最大链的长度就可以,其实也就是求DAG图的最长路问题 。

    如果哪里有写的不合理欢迎指出。