問題タブ [subgraph]

2 つのラベル付きグラフ G と T があり、アルゴリズムは、G が T のサブグラフであり、メイン グラフ T とサブグラフ G の対応する頂点が同じラベルを持つべきかどうかを判断すると仮定します。

私はメイン グラフと別の小さなグラフを持っています。小さなグラフは類似度のあるサブグラフとしてメイン グラフで繰り返すことができると仮定します (必ずしも同じ小さなグラフではありません)。それらを見つけるための優れたアルゴリズム (または Java ライブラリ) は何ですか?全て？

これは、生成されたグラフが現在表示されているもの です。これのコードは次のとおりです。

2本の赤い線を削除すると、希望どおりに整列します。

どうすればこのように並べて、2本の赤い線を同時に持つことができますか？

有向グラフで指定されたパターンに対応するセクションを検索するためのツール/アルゴリズムを見つけようとしています。

A->B->C または A<->B->C

私の検索の方向性を教えてください。

パターンマッチングのことです。指定されたパターンに一致するノードとエッジのすべてのグループを見つける必要があります

特定の頂点を介して P 頂点で可能なすべてのサブグラフのリストを作成するアルゴリズムがあります。完璧ではありませんが、問題なく動作するはずです。問題は、その時間の複雑さを計算しようとすると迷子になることです。

のようなものを思いついT(p) = 2^d + 2^d * (n * T(p-1) )たd=Δ(G), p=#vertices required, n=|V|。本当にただの推測です。誰でもこれで私を助けることができますか？

使用される powerSet() アルゴリズムはO(2^d)またはである必要がありますO(d*2^d)。

テキストの壁で申し訳ありませんが、それは私ができる限り簡潔です!

私は 1 つの非常に大きな有向グラフ G と、G 内からの頂点のサブセット S を持っています。私がやりたいことは、S によって誘導される G の部分グラフを見つけることです。 p と G の頂点 q で、誘導されたサブグラフのこれら 2 つの頂点の間にエッジが存在すること。これが重要です。通常の誘導されたサブグラフの問題よりも少し複雑です（私はそう思います）。

問題を解決するために私が考えることができる最も基本的な方法は次のとおりです（おそらく最も効率的ではないことを認識しています。実装するのに複雑すぎない他の提案があれば教えてください）：S内の頂点のすべてのペアについて、G でそれらの間のパスの存在をテストします。そのようなパスが存在する場合、誘導された部分グラフの p と q の間にエッジを挿入します。私の目的では、n^2 時間はそれほど悪くありません。

したがって、2 つの質問があると思います。1) 2 つの頂点間にパスが存在するかどうかを判断する最速の方法は何ですか? パスが存在するかどうかだけで、パスを知る必要はありません。さらに、この計算を高速化するためにグラフ全体に対して実行できる前処理がある場合、頂点の各ペア間でこの計算を実行する必要があるため、それは何でしょうか?

2）私が説明した誘導サブグラフのタイプを見つけるために私が提案した方法よりも速い方法はありますか？

助けてくれてどうもありがとう！

グラフを次のようにしたいと思います。

しかし、私はこれしか得られません：

問題は、でrankdir 動作しないことですsubgraph。では、それをエミュレートする方法は？

コード：

と の 2 つの頂点リストがVありSます。

V可能なすべての有向グラフをandから生成したいと思いますS。各頂点にVは 1 つのアウト エッジと 1 つのイン エッジしかなく、各頂点にSは任意の数のイン エッジとアウト エッジを含めることができます。V結果の各グラフには、と からのすべての頂点が正確に含まれている必要がありますS。結果には、接続されたグラフと切断されたグラフの両方を含めることができます。

最初は powerset 関連の問題だと思っていましたが、powerset には 1 つの要素だけを含む可能性のある他の多くのセットがあります (それらは必要ありません)。

私の現在の戦略は次のとおりです。

• から頂点間のすべてのペアを見つけV、に追加しPairsます。
• から頂点間のすべてのペアを見つけS、に追加しPairsます。
• Vとからの頂点間のすべてのペアを見つけS、 に追加しPairsます。
• V各サブセットがv最初の位置に頂点のインスタンスを 1 つだけ持ち、2 番目の位置に頂点のインスタンスを 1 つ持ち、任意の位置からv任意の頂点の任意の数のインスタンスを持つような方法で、以上のサイズのペアのサブセットを生成する.sS

これが正しいかどうか確信が持てないので、アイデアについて知りたいです。

たぶん、完全に接続されたグラフを作成しG、VそれからS何らかの方法でサブグラフを抽出できますか? (おそらく digraph:utils の助けを借りて)

PS私はこれをErlangで解決しようとしています.Erlangは私が使用していて、現在積極的に学んでいる言語だからです. しかし、Java、Ruby、または疑似コードが回答に含まれていることを嬉しく思います。

次の問題を解決しようとしています。

連結グラフ G = (V, E) と頂点 t ∈ V が与えられた場合、t ∈ V' である部分グラフ G'= (V', E ') を見つける必要があります。G' は、いくつかの目的関数を最大化し、それに含まれる頂点の数を最小化する必要があります。

この多目的最適化問題では、頂点の数を最小化することよりも、f (G') を最大化することが重要です。

同様の問題で実際の状況を確認してみましょう。

クライアント デバイスが固定された場所にあり、有線ネットワークに接続されている AP が 1 つしかない建物内に、アドホック ワイヤレス ネットワークを設計する必要があるとします。最初に、すべての部屋に AP を配置し、伝播モデルを使用して、接続できる AP と、それらがカバレッジを提供するクライアント デバイスを計算します。この最初の配布では、おそらく複数の AP が同じクライアント デバイスにカバレッジを提供するため、最適化する必要があります。

図 1. 赤い点は有線ネットワークに接続された AP を表し、黒い点は残りの AP を表します。AP 間の実線は、それらがどのように接続されているかを示しています。

図 1 の AP の接続を形成するグラフは、問題の接続グラフ G を表し、有線ネットワークに接続されている AP はノード t です。この初期ネットワーク設計を表すグラフを最適化すると、有線ネットワークに接続された AP を含むサブグラフを見つけ、対象となるクライアント デバイスの割合 (最大 f(G') ) を最大化し、AP の数を最小化します (最小 |V'| ）。問題のように、対象となるクライアント デバイスの割合を最大化することが主な目標です。

図 2. 考えられる解決策。

ブルートフォースアルゴリズムを使用すると、NP完全性の問題のように見えます。最適な解を見つけるには、すべての潜在的なサブグラフ (すべてノード t を含む) を調べ、可能な解も証明する必要があります。についてどう思いますか？