d-正則グラフで単純なサイクルの長さを見つけるためのアルゴリズムの設計
突然変異アルゴリズム
私は一般的に質問を理解していますが、質問のアルゴリズムを設計および分析する方法がわかりません。深さ優先/幅優先検索のようなグラフ検索アルゴリズムを適用することを考えていました。
更新：これは私が試したもので、グラフの任意のノード（Nと呼びます）から始めて、そのノードのd個の隣接ノードのそれぞれにアクセスします。さて、Nの最後の隣人（それをLと呼びます）は、NではないLの他の隣人を訪問しますか？
voidengine
他の人はすでにコメントで可能な解決策をほのめかしています、詳しく説明しましょう。の場合d<=1、解決策は即時です（そして、サイクルの正確な定義に依存します）ので、私は仮定しd>1ます。
そのようなアルゴリズムの1つは次のとおりです。
- 任意の頂点から始まるパスを作成します
V。パスの長さが長くなるまで、dすでにアクセスした頂点を許可しないでください。 - パスが
d頂点の長さになったら、パスに頂点を追加し続けますが、パスの最後のd頂点とは異なる頂点のみを許可するようになりました。 - パスですでに使用されている頂点を追加したら、停止します。その頂点で開始および終了するパスのセグメントから結果のサイクルを作成します。
（1）と（2）の両方で、そのような頂点の存在は、Gがd-regularであるという事実によって保証されます。追加する頂点を検索するときは、最後のd頂点、つまり最後の頂点（U）とその前の頂点のみを除外しd-1ます。Uにはdネイバーがあるため、少なくとも1つは使用可能である必要があります。
条件（3）とGが有限であるという事実のために、アルゴリズムは停止します。
（2）ですでにアクセスした頂点を優先することは理にかなっていますが、最悪の場合の複雑さは変わりません。
これにより、最悪の場合の複雑さn*dが得られます。頂点ごとに1回アクセスして、そのすべてのエッジをチェックする必要がある場合があるためです。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
編集
関連記事
Related 関連記事
- 1
非規則的な2D形状の最長の完全に内部の線を見つけるためのアルゴリズム？
- 2
加重2Dマトリックスの指定されたソースと宛先の場所の間の最適なパスを見つけるために、フラッディングアルゴスリムを適用する方法
- 3
無向グラフで最長のサイクルの長さを見つけるための効率的なアルゴリズムはありますか？
- 4
2D曲線の双接を見つけるためのアルゴリズム
- 5
2D配列のピークを見つけるアルゴリズム
- 6
Pythonの単純な2Dクラスタリングアルゴリズム
- 7
同じ長さの1dnumpy配列で関数の1d配列を評価するための効率的なアルゴリズム
- 8
2D軌道のパスの単純化と平滑化のためのアルゴリズム
- 9
次数10 ^ 5の完全グラフのEMSTを見つけるための最も単純で最も簡単なアルゴリズムは何ですか
- 10
正しい最適化アルゴリズムC ++を使用して3D空間内のポイント間の距離を見つける
- 11
アルゴリズムの問題：有向グラフで最長の基本サイクルを見つける
- 12
閉じた不規則な三角形の3Dサーフェスとデカルトの長方形の3Dグリッドとの交点を見つける
- 13
アルゴリズムはカタツムリの2D配列で番号の位置を見つけます
- 14
同じ長さの1dnumpy配列で関数の1d配列を評価するための並列化アルゴリズム
- 15
2Dグリッドゲームボードの移動攻撃エリア内のターゲットを攻撃するスペースを見つけるためのアルゴリズム
- 16
3Dカールを計算するための最速のアルゴリズム
- 17
3Dリスト内の一意の要素の最小インデックスを取得するための効率的なアルゴリズム
- 18
シミュレートされた3D空間での単純な三辺測量アルゴリズム
- 19
単純な HTML ページで d3js グラフのサイズを自動調整する
- 20
正の整数値を持つサイズMxNの2D行列が与えられた場合、最大の合計を持つ閉ループを見つけます
- 21
2Dベクトルから最小サイズのベクトル要素を見つけるためのより良い方法
- 22
グラフの直径を見つけるための近似アルゴリズム
- 23
アルゴリズム-n * n2D行列でk * kセットのすべての最大値を見つける
- 24
アルゴリズム設計：C ++で境界桁を使用して2Dグリッドを表現する最良の方法は？
- 25
2D座標マッピングを最小化するための高速アルゴリズム
- 26
D3.jsスタックからグループ化された棒グラフの例で、変更されたLeeByronのテストアルゴリズムジェネレーターを介してCSVを渡す
- 27
グラフ重心を見つけるための効率的なアルゴリズムとは何ですか？
- 28
d3の異なるグループでグループ化されたカテゴリ棒グラフ？
- 29
'a'と 'b'の値を見つけるための最適なアルゴリズムを設計する
コメントを追加