7

我想生成一个有向图，其中包含完全指定数量的循环以及它们各自的长度。例如，图表应包含：

2个尺寸3的周期
1个5号的周期

  • 这样的算法是否已经存在？如果不是，您将采取什么方法来解决这个问题？具体来说，给出以下参数：

    1. 顶点数（例如，15）
    2. 组件的数量（例如，2）
    3. 必须在图中的循环（例如，{3-cycle, 3-cycle, 5-cycle}）

  • 我只发现了几种可以检测现有图中循环的算法（例如，Tarjan）。您认为还可以使用循环检测算法来生成具有特定循环数量的图形吗？

4

1 回答 1

2

在某些情况下可能会失败的贪心算法需要同行评审。

请注意，如果我们有一个一定长度的循环k：

1 -> 2 -> 3 -> ... -> k -> 1

我们可以通过引入一个其他节点来制作另一个相同长度的循环：

1 -> 2 -> 3 -> ... -> k -> 1
k' -> 1 -> 2 -> ... -> k - 1 -> k'

或相同长度的循环 - 1：

1 -> 2 -> 3 -> ... -> k -> 1
k' -> 1 -> ... -> k - 2 -> k'

这可以通过始终引入一个新节点并将其连接到一个初始的、足够大的循环中的其他两个节点来永远持续下去。

所以，如果你能负担得起无限数量的节点，就这样做，从你需要的最大周期开始。

如果您必须使用固定数量的节点，我们应该尽量减少用于构建请求循环的节点数量。任何剩余节点都可以轻松添加，因此它们不会形成任何循环。

再次从最大的循环开始：

1 -> 2 -> ... -> k -> 1

通过不再添加任何节点，我们可以从中获得以下信息：

  1. k长度2周期：2 -> 1, 3 -> 2, ... 1 -> k.

  2. k - 2长度3周期：3 -> 1, 4 -> 2, ..., k -> k - 2.

  3. 一般来说，k - p + 1长度p周期。

这些都不会产生额外的循环。所以整个算法将是：

  1. 建立您最大的请求周期。

    1.1。如果超过一个最大的，则通过为每个节点添加一个新节点来构建更多。请注意，这会影响所描述的通过不添加任何新节点从大循环中构建较小循环的过程，因为您会得到一个特定大小的新循环。会有一些重叠，所以你不能简单地将解决方案的数量加倍。据我所知，它只会将数字增加 1。

  2. 通过不添加任何新节点来构建较小的周期。

  3. 如果没有完成构建所需的周期：

    3.1。如果您还有节点，请使用它们。

    3.2. 如果您没有剩余节点，则输出no solution.

  4. 如果完成构建周期：

    4.1。如果您还有节点，请将它们作为链表添加​​到某处，这样它们就不会打扰您。

    4.2. 如果没有节点剩下，你就完成了。

于 2016-02-08T18:18:14.440 回答