生成一个有n个圆周的有向图。

Question

我想生成一个有指定数量的特定长度循环的有向图。例如，该图应包含：

2个大小为3的循环 1个大小为5的循环

是否已经存在这样的算法？如果没有，您会如何解决这个问题？详细说明以下参数：

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

我只找到了几个可以检测现有图中循环的算法（例如Tarjan）。您认为是否可能也使用循环检测算法来生成具有特定循环数量的图？

- derbenoo

---

顶点数量是否固定？ - sve

这是一个有趣的问题。 - dashnick

是的，该算法将顶点的数量作为输入参数。 - derbenoo

图表中是否可能包含其他循环，还是仅包含列表中指定的循环？ - user4668606

这是棘手的部分，图表必须仅包含指定的循环。 - derbenoo

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. 如果没有节点，请输出“无解”。 4. 如果完成了循环构建： 4.1. 如果还有节点，请将它们作为链接列表添加到某个位置，以免干扰您。 4.2. 如果没有剩余节点，则完成。

- IVlad