nサイクルの有向グラフを生成する

Question

指定した長さのサイクルを正確に含む有向グラフを生成したい。例えば、グラフが含まれている必要があります

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

• は、このようなアルゴリズムは、すでに存在していますか？もしそうでなければ、この問題を解決するあなたのアプローチは何でしょうか？具体的には、以下のパラメータが与えられる：
  1. 頂点（例えば、15）の数
  2. 成分の数（例えば、2）
  3. グラフである必要サイクル（例えば、{3-サイクル、3サイクル、5サイクル}）

• Iのみ既存のグラフにサイクルを検出することができるいくつかのアルゴリズム（例えば、Tarjan）を発見しました。サイクル検出アルゴリズムを使用して、特定のサイクル数のグラフをに生成することも可能だと思いますか？

Answer 1

場合によっては失敗する可能性がある貪欲アルゴリズムは、ピアレビューを必要とします。

なお、我々はいくつかの長さkのサイクルがある場合：

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

または：私たちは、単一の他のノードを導入することにより、同じ長さの別のサイクルを作ることができます

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

を同じ長さのサイクル - 1：

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

常に新しいノードを導入し、それを初期の十分な大きさのサイクルで他の2つのノードに接続することによって、

無限の数のノードがあれば、必要な最大サイクルから始めてください。

固定数のノードで作業する必要がある場合は、要求されたサイクルを構築するために使用するノードの数を最小限に抑えるように努力する必要があります。残りのノードは簡単に追加することができ、サイクルを形成しません。再び最大のサイクルで

スタート：任意のより多くのノードを追加しないことにより

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倍にすることはできません。私が知る限り、数字は1だけ増加します。

2. 新しいノードを追加しないことで、より少ないサイクルを構築します。

3. 必要なサイクルを構築していない場合：

   3.1。ノードが残っている場合は、それらを使用してください。

   3.2。ノードが残っていない場合は、出力no solutionを出力します。

4. サイクル構築行われた場合：

   4.1。ノードが残っている場合は、それらをリンク先リストとしてどこかに追加してください。

   4.2。ノードが残っていなければ、完了です。