生成具有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

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

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

建立您所要求的最大周期。

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

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

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

4.1. 如果还剩下节点，请将它们添加为链接列表，这样它们就不会打扰您。

4.2. 如果没有剩余节点，则完成。