または、一意のグラフごとにアルゴリズムを開発する必要がありますか？ユーザーには一種のグラフが与えられ、ユーザーはインターフェースを使用してノードとエッジを最初のグラフに追加することになっています。次に、グラフを送信すると、アルゴリズムはユーザーのグラフが指定されたグラフと一致するかどうかを確認することになっています。
アルゴリズムは、各ノードの隣接ノードだけでなく、各ノードと各エッジが正しい値を持っていることも確認する必要があります。初期グラフには常にルートノードがあり、そこからアルゴリズムを開始できます。
一般的な意味でそのようなアルゴリズムのロジックを開発できるのか、それとも実際に一意のグラフごとに一意のアルゴリズムをコーディングする必要があるのでしょうか。後者の場合、私は約20の固有のグラフしかないので、大したことではありません。
ありがとう。はっきりしていたと思います。
グラフ同型問題は難しくないかもしれません。しかし、この問題が難しくないことを証明するのは非常に困難です。
この問題には 3 つの可能性があります。
1. グラフ同型問題はNP 困難です。
2. グラフ同型問題には多項式時間解があります。
3. グラフ同型問題は NP 困難でも P でもありません。
2 つのグラフが同型である場合、この同型の順列が存在します。この順列を証明として取り、この 2 つのグラフが多項式時間で互いに同形であることを証明できます。したがって、グラフ同型は NP 集合の領域にあります。しかし、この問題が NP 困難であるか P であるかを誰も証明できなかったのは 30 年以上も前のことです。したがって、この問題は単純な問題記述にもかかわらず、本質的に困難です。
私が質問を正しく理解していれば、いくつかの参照グラフの1つを入力として受け入れることで機能する1つの単一アルゴリズムを持つことができます（参照グラフとの同形性が主張される未知のグラフの入力に加えて）。
グラフが特定の操作または特性のセットに対して同形であるかどうかを主張するのではなく、特定のグラフが別のグラフと完全に同一であるかどうかを主張しようとしているようです。これは、グラフが他の方法で異なる場合でも、どちらのグラフにもループがないかどうか、または両方のグラフが完全に接続されているかどうかなどの一連の「抽象的な」ルールを処理するのではなく、特定の参照グラフをアルゴリズムに提供することを意味します。
Edit、次の確認:
ええ、アルゴリズムには参照グラフ (これが答えです) が提供され、ユーザーのグラフをチェックして、参照と同形 (エッジとノードの値を含む) かどうかを確認します。
その場合、はい、これら 2 つのグラフの同型性を主張する比較的単純なアルゴリズムを開発することは十分に可能です。他の発言や回答で言及されている考慮事項、および問題がNP 困難である可能性があるという事実に関連する考慮事項 は、単純なアルゴリズム [またはその問題に関する任意のアルゴリズム] が合理的な量で問題を解決するのに十分ではない可能性があることを単に示していることに注意してください。サイズと複雑さが大きすぎるグラフの時間。ただし、比較的小さなグラフを想定し、エッジとノードの重みも一致する必要があるという要件を (!)利用すると、次のアルゴリズムが一般的に適用されます。
一般的な考え方:
グラフの残りの部分から切断されている各サブグラフについて、参照グラフの特定のノードと一致する必要があるユーザー グラフ内の 1 つ (または複数) のノードを識別します。このノードからのパスをたどることによって [順序どおりに、これについては以下で詳しく説明します]、他のノードの同一性を主張し、および/または一致できないいくつかのノードがあることを決定します (したがって、2 つの構造は同型ではありません)。
大まかな疑似コード:
1. 参照グラフとユーザー提供グラフの両方について、 接続コンポーネントのリスト、つまり、グラフの残りの部分から切り離されたサブグラフのリストを作成します。これらの接続されたコンポーネントを見つけるには、特定のノードから始まる幅優先パスまたは深さ優先パスをたどり、そのパス上のすべてのノードを任意の [通常はインクリメンタル] 要素 ID 番号で「マーク」します。特定のパスが完全に訪問されたら、他のマークされていないノードから操作を繰り返し、マークされていないノードがなくなるまで繰り返します。
2.各グラフの特徴の「データベース」を構築する. これは、一致する候補を特定したり、早期に非同型のインスタンスを特定したりするのに役立ちます。各「データベース」には、ノードとエッジの 2 種類の「レコード」があり、それぞれ次のフィールドがあります。入力エッジの重み。ノード - edge_id、Connected_element_Id、エッジの重み、node_id_of_start、node_id_of_end、weight_of_start_node、weight_of_end_node
3.各グラフの Connected 要素のデータベースを
構築します。
各レコードには次のフィールドが必要です: Connected_element_id、ノードの数、エッジの数、ノードの重みの合計、エッジの重みの合計。
4. [オプション]非同型の簡単なケースをディスパッチします:
4.a 接続された要素の数の
不一致 4.b 接続された要素の数の不一致、id (ノード数、エッジ数、ノードの合計) 以外のすべてのフィールドでグループ化重み、辺の重みの合計)
5. 参照グラフ内の各接続要素について
5.1 ユーザー提供グラフ内の一致する接続要素の候補を識別します。候補は、同じ接続要素の特性 (ノード数、エッジ数、ノードの重みの合計、エッジの重みの合計) を持ち、id 以外のすべての特性でグループ化してカウントされたノードとエッジの同じリストを含む必要があります。
5.2 各候補について、参照グラフ内の対応する接続要素に関連する同形グラフとしてその確認を確定します。これは、ノード一致の候補、つまり両方のグラフでまったく同じ特性を持つ一意である可能性が高いノードから開始することによって行われます。そのようなノードが存在しない場合、同形性が確認できるまで (またはすべての候補が尽きるまで)、可能な候補をそれぞれ不適格にする必要があります。候補ノードの一致については、エッジの方向と重み、およびノードの重みに基づいて、たとえば幅優先で、他のノードの一致を見つけることによって、グラフをウォークします。
このアルゴリズムの主な秘訣は、候補を適切に考慮し (上位レベルの候補接続要素か、下位レベルの候補ノードか)、その他の識別されたアイテムを記憶してマークする (場合によってはマークを解除する) ことです。どういうわけか、仮想候補は最終的に実現不可能であることが証明されます.)
上記は正式なアルゴリズムの説明には及ばないことは承知していますが、何が必要で、おそらく出発点のアイデアが得られるはずです。それを実装することにしますか.
ノードとエッジの重みを一致させるという要件は、同型性を主張するための追加の難しさのように見える場合があることに注意してください。アルゴリズムを効果的に単純化するのは、基礎となるノード/エッジの特性がこれらをより一意にレンダリングし、アルゴリズムが a)一意のノード候補を見つける、および b) パス上の他の候補をすばやく見つける、および/または非同形性をすばやくアサートする。