DAG中的topological sort个数等价于统计一个partially ordered set上linear extension的个数,后面这个问题已知是#P-complete的,所以目前还没有polynomial-time的做法
看到本问题下面的一个非常惊艳的匿名回答。
好久没看到了。
DAG中的拓扑排序的个数等价于统计一个偏序集合上线性组合的个数。
而求这个线性组合的后面这个问题已经有人证明了是P完全问题。
NP问题就不解释了。
现在举例子来解释。
跟书上说的不同,存在回路的连通有向图是可以排序的。方法就是缩点。即把回路当成一个要素(结点)来处理。
上面是缩点的示意,就不再解释。
上面是文科生经常用到的一个研究方法。流程如下:
上面是另外一种计算方法。计算流程如下:
最终求出的对抗层级拓扑图就是一种拓扑排序
上面就是哈斯图,又叫对抗哈斯图,也叫对抗层级拓扑图。
任何一边的图,从上到小一个个数下来就是一个拓扑序。
按理只数个数这不是一个P完全问题。
根据每一层的组合情况可以直接得出。
但是观察右边的F5,它可以跟F6同一层。
而且转化成线性列的时候,要去重,这就蛋疼了。
如果碰巧是刚性系统,即没有活动要素的时候。
只算个数就很容易。
比如上面这种没有跃迁要素的。
也就是两边是一样的。
那好办,直接算组合就出来了。是一个多项式的解。
应该只有指数级做法,状态压缩动态规划可以做到 O((n+m)2^n),n为总点数m为总边数。