从给定的多种拓扑排序构建一个DAG

Question

我需要从其给定的拓扑排序来构建一个DAG（即图 $ g $ 创建必须将所有订单作为其拓扑排序所指定）。为简单起见，顶点标记为第一个<跨度类=“math-container”> $ n $ 自然数字。 （请注意，一旦创建，图 $ g $ 可能与给定的拓扑排序相比。）
应满足以下约束：

1. 每个节点的最大undedee应该是1
2. 具有Indegree 0的节点的数量应最小。

可以有多种解决方案，其中任何一个都应该工作。

我尝试了什么。 （方法1 这是错误的，因为它失败了答案中给出的一个例子。请滚动到第二种方法，这仍然无法找到错误。）

方法1
从所有给定的订单中，首先，通过从每个节点创建指向边沿到下一个节点来创建定向图。这意味着如果订单是：
$$ 1,3,2,5,4,6 $$ $$ 3,1,5,2,4,6 $$ $$ 1,5,3,2,4,6 $$

我将使用从 $ 1 $ 到 $ 3,3,3 $ 的定向图 $ 2,2 $ 到 $ 5 $ 等等。



这可确保具有Indegree 0的节点数量仍然最小。现在，我将删除所有周期并确保所有订单都有效，最后，消除任何节点的所有额外边缘。在这样做的同时，我会确保如果有两个边缘来自同一节点的节点，我将从具有较高的indegree的节点中删除边缘，以便满足条件2。 那么构造的图表应该如下所示：

创建的DAG，遵循约束，IMO具有Indegree的最小数量为0，虽然，但它没有被证明。

我已经编码了这种方法，它为我提供的用例提供了预期的结果，但我知道这是错误的。 我在这里遗漏了什么？任何人都可以提供替代用例，这失败了上述方法吗？

方法2
我创建了一个定向图 $ g $ ，通过从 $ a_i $ 到 $ A_J $ 对于所有 $ j> i $ 在给定的所有订单中。 所以，对于订单：
$$ 1,2,3,4,5 $$ $$ 2,4,1，5,3 $$

我将创建以下图：
在此之后的第一步是验证所有排序。不需要分别去除周期，因为它们将被这一步自身删除。

任何订购 $$ a_1，a_2，a_3，a_4，... a_n $$ 我会检查是否存在来自 $ a_j $ 到 $ a_i $ 其中 $ j> i $ ，我将删除该边缘。
这样做，将提供以下图：
最后一步是从所有节点中删除额外的边缘，因为任何节点的最大undedege可以是 $ 1 $ max。我将删除传出的边缘，使得具有Indegree $ 0 $ 的节点的数量最小。首先，我计算每个节点的图形。然后，对于具有超过1个传出边的每个节点，我将删除除了最小图形的所有边缘。

最终图 $ g $ 将如下所述：

本图满足约束。但我知道这种方法是错误的！有人可以帮助找到原因错误吗？

Answer 1

方法1

例如，考虑两个订单：1,2,3,4,5和2,4,1,5,3。

根据您的方法，我们将获得一个循环1-> 2-> 3-> 4-> 1。然后我们删除3-> 4和4-> 1，并获得图形：

     ______
    /      \
1->2->4->5->3
 \______/

.

现在5-> 3和1-> 2分别违反第一个和第二个订单，因此我们删除它们，并获得

     ______
    /      \
1  2->4->5  3
 \______/

.

现在节点2有2个传出边。删除任何一个，做一个最终图，其中3个节点（1,2,3或1,2,4）具有型号0。

但是，存在图形

1->3 2->4->5

.

在其中满足两个订单，但只有2个节点有0.

所以方法1不正确。

方法2

考虑最佳解决方案。此最佳解决方案中的每个边缘必须是 $（a_i，a_j）$ 其中 $ i 在每个订单中。这意味着最佳解决方案中的所有边缘都包含在中间图中。因此，如果您删除外向边沿，使得具有型号的节点的数量最小，您将获得正确的最佳解决方案。

但是，您尝试使具有型号为0的节点数量的方法是不正确的。

例如，考虑三个订单： \ begin {align} 1,2,3,4,5,6,7,8 \\ 5,1,6,3,8,2,4,7 \\ 2,7,3,8,1,4,5,6 \结束{对齐}

首先，我们可以获得以下中间图：

    _____
   / ____\__
  / / ____\_\__
 / / /     \ \ \
1 2 3->4 5->6 7 8
 \ \__/
  \__/

.

应用您的方法，我们将删除1-> 4，2-> 4和3-> 4（或3-> 8），有5个具有在0：1,2,3,4的节点（或8），5。但是，最佳解决方案是

     _______
    / ____ _\__
   / /       \ \
1 2 3 4 5->6 7 8
 \___/

.

其中4个节点的程度为0：1,2,3,5。