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

Question

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

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

这样的算法已经存在了吗？如果没有，您将采用什么方法来解决这个问题？详细给出以下参数：
1. 顶点数（例如，15）
2. 组件数量（例如，2）
3. 图表中必须包含的循环（例如，{3 循环、3 循环、5 循环}）
我只发现了几种可以在现有图中检测循环的算法（例如，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

不添加任何节点，我们可以得到以下信息：

其中

None 将生成额外的循环。所以整个算法将是：

建立你最大的请求周期。

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

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

3.2。如果没有剩余节点，则输出 no solution.
如果完成构建周期：

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

4.2。如果没有剩余节点，您就完成了。

Generate a directed graph with n cycles