首页 > 试题广场 >

拓扑排序是指将有向无环图 G 中的所有顶点排成一个线性序列,

[填空题]
拓扑排序是指将有向无环图 G 中的所有顶点排成一个线性序列,使得图中任意一对 顶点 u 和 v,若 ∈E(G),则 u 在线性序列中出现在 v 之前,这样的线性序列成为拓 扑序列。如下的有向无环图,对其顶点做拓扑排序,则所有可能的拓扑序列的个数 为 1

先考虑前 7 个点,显然 1 和 6 是必然放在最前面和最后面的,然后考虑另外 5 个点,5 任意放,3 在 2 之后,4 和 7 在 3 之后,那么就有 1 2 3 4 7 6 和 1 2 3 7 4 6 两种情况,在里面插入 5 则有 12 种情况,然后考虑 8 和 9,9 要在 8 后面,则对于每一种情况有 1 + 2 + ... + 8 = 36 种情况,12 * 36 = 432。
发表于 2019-10-15 14:16:44 回复(0)
1、首先考虑8->9这两个点,根据拓扑排序规则,8,9两个点可以在序列的任意位置,1->7一共有8个空,又8要在9前,所以不计算8和9之间的相对排列顺序产生的答案。我们可以吧8和9绑在一起,也可以把他们分开,这样产生对答案的贡献有C(1,8)+C(2,8)。
2、模拟拓扑排序的过程,当把1删掉后,5可以插在2->6之间(6个空),这样对答案的贡献有C(1,6)。
3、当把3删掉后,4可以放在7的两边,对答案的贡献有C(1,2)。
4、根据乘法原理统计答案 ans=( (C(1,8)+C(2,8) ) * C(1,6) * (1,2)=432
发表于 2019-10-13 21:28:21 回复(0)