algorithm - 生成具有 n 个循环的有向图

Question

我想生成一个有向图，其中精确包含指定数量的循环及其各自的长度。例如，图表应包含:

2 cycles of the size 3 1 cycle of the size 5

• 这样的算法是否已经存在？如果没有，您将采用什么方法来解决这个问题？详细的，给出了以下参数:

  1. 顶点数(例如，15)
  2. 组件数量(例如 2)
  3. 图中必须包含的循环(例如，{3-cycle, 3-cycle, 5-cycle})

• 我只发现了几种算法(例如 Tarjan)可以检测现有图中的循环。您是否认为也可以使用循环检测算法来生成具有特定循环数的图形？

Answer 1

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

请注意，如果我们有一个长度为 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。如果没有剩余节点，您就完成了。