2

まず第一に、私はグラフ理論に精通しておらず、数学の知識も非常に乏しいと言わなければなりません。とにかく、分析にはグラフの概念を使用しています。

基本的に、無向グラフ (たとえば G) をサイクル (閉じたグラフ) に分解しています。私のサイクルの特徴は、それらが 2 つの頂点間を移動できる最短のサイクルであることです (サイクルであるため、開始と終了は同じですが)。私の例のグラフによると、私のサイクルは (1,4,5,1)(1,2,3,4,1)(7,9,8,7) です (長さが 3 未満のサイクルは無視します) .

編集:深さ優先検索を使用してサイクルを取得し、次に最小のサイクルを取得しました。

後で、これらのサイクルを有向パスにさらにブレーキングします。ここでは、新しいパス グラフの開始ノードと終了ノードを挿入するために、エッジ (図の赤い線) を介してサイクルを分割しました。したがって、サイクル (7,9,8,7) => 新しい有向パスは (a,9,c)(d,8,7,b) です。新しいベクターを挿入して要素を更新するだけです。グラフ理論に関連するアルゴリズムはここには含まれません。

次に、データを分析します。

上記のことをすべて行いました。だから、私の問題は、数学的な表記法で物事全体をどのように説明するかです（私が言ったような例はありません）。私は基本さえ持っていないので、これは私にとって非常に難しいです。

私はグーグルで検索しようとしましたが、自分がしたことを説明する方法をまだ見つけることができません。私がしたことはあなたには明らかだと思います。

それで、私を助けてくれませんか、どのように説明するか

  1. 無向グラフをサイクル (最短サイクル) に分解する
  2. エッジ経由のサイクル ブレークと有向パス グラフの作成 (図に示すように)

数学表記あり（グラフ理論による）

多くの著者がグラフとそのサブグラフを定義するためにさまざまな表記法と記号を使用しているのを見てきましたが、私の場合、基本が貧弱すぎて定義できません。ですから、これらのことを形式的で数学的な方法で言うのを手伝ってください。前もって感謝します。

また、アイデアを得るためにサンプル図を挿入しました。 ここに画像の説明を入力

注: 多くのコンピュータ サイエンティストがグラフ理論を使用しており、回答を得たいと考えているため、c++ タグを追加しました。

4

1 に答える 1

1

演算を数学的な記述に入れようとして最初に遭遇する可能性のある問題は、「最短サイクル」の定義です。サイクルは通常、最初の頂点が最後の頂点でもあるエッジで接続された頂点のシーケンスとして定義されます。

数学のクラッシュコース

数学では、グラフは通常、2つのセットV（頂点のような）とE（エッジのような）によって記述されます。セットEは、それぞれが頂点である2つの要素を持つセットで構成されます。そのような

  • V = {v1、v2、....、vn}

  • E = {...、{vi、vk}、...}

Eのすべてのセットは、グラフの1つのエッジに対応します。

そのため、（接続された）パスは通常次のように定義されます。

頂点のシーケンスv1、....、vnは、シーケンスviおよびvi + 1の 2つの連続する頂点ごとに、集合{vi、vi+1}が集合Eの要素であるというプロパティを持ちます。

（実際には、頂点viから頂点vi + iへのエッジがあります）

サイクルは通常、次のプロパティを持つパスとして定義されます。v1 = vn（したがって、最初の頂点は最後の頂点でもあります）

この定義はすでにあなたの例ですが、シーケンス：1、4、1は（数学的な意味で）サイクルを形成します

そのため、グラフのすべてのエッジは「最短」サイクルとしてカウントされますが、与えられた例は間違いなく長くなります。

あなたはあなたに言った

...長さが3未満のサイクルを無視します

これは、説明の開始点としては悪くないように見えます。残念ながら、私はあなたが実行したい次のステップを完全には理解していませんでした。

助言

私のアドバイス、または少なくとも私が問題に取り組む方法は、タスクを実行しようとする方法を正確に洗練しながら、かなり長い説明をある種の短いアルゴリズムの説明に変換することです。このようにして、最終的な説明にたどり着くのはそれほど難しいことではありません。特に、アルゴリズムへの入力が正確に何であるかを伝えることを忘れないでください。それでもあなたの説明からはあまり明確ではないようです。

  • すでに知られている「最短」サイクルのセットから始めていますか？
  • または、入力としてグラフが与えられ、「最短」サイクルを自分で決定する必要がありますか？
  • あなたがそれらを自分で検出した場合、これはどのように正確に行われますか？それがあなたの問題にとって最も重要なものの1つであるように思われるので、それが当てはまる場合は特に、物語のこの部分について話すことを忘れないでください。
于 2013-03-03T00:17:10.943 に答える