7

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

サイズ 3 の 2 サイクル
サイズ 5 の 1 サイクル

  • そのようなアルゴリズムはすでに存在しますか? そうでない場合、この問題を解決するためのあなたのアプローチは何ですか? 詳細には、次のパラメータが指定されています。

    1. 頂点の数 (例: 15)
    2. コンポーネントの数 (例: 2)
    3. グラフに含まれるサイクル (例: {3-cycle, 3-cycle, 5-cycle})

  • 既存のグラフのサイクルを検出できるいくつかのアルゴリズム (Tarjan など) しか見つかりませんでした。サイクル検出アルゴリズムを使用して、特定の量のサイクルでグラフを生成することも可能だと思いますか?

4

1 に答える 1

2

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

ある長さのサイクルがある場合、次のことに注意してください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'

これは、常に新しいノードを導入し、最初の十分に大きなサイクルで他の 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. ノードが残っていない場合は、完了です。

于 2016-02-08T18:18:14.440 に答える