知识点练习

有向无环图 $G$ 顶点集为 ${1, 2, 3, 4}$，边集为 ${(1, 2), (1, 3)}$，顶点 4 与任何顶点均不相邻。该图不同的拓扑序共有多少种（ ）。

对于一个包含 $n$ 个结点和 $m$ 条边的有向无环图（DAG），其拓扑排序的结果有多少种可能？

一个包含 $8$ 个顶点的完全图（顶点的编号为 $1$ 到 $8$），任意两点之间的边权等于两顶点编号的差的绝对值。例如，顶点 $3$ 和 $7$ 之间的边权为 $|7 - 3| = 4$。该图的最小生成树总权重是多少？

如图是一张包含 $7$ 个顶点的有向图，如果要删除其中一些边，使得从节点 $1$ 到节点 $7$ 没有可行路径，且删除的边数最少，请问总共有多少种可行的删除边的集合？（ ）

如图是一张包含 $6$ 个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这 $6$ 个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？（）

有如下的有向图，节点为 $A ,B , \cdots , J$, 其中每条边的长度都标在图中。则节点 $A$ 到节点 $J$ 的最短路径长度为（ ）。