問題タブ [graph-theory]

以下に説明する特定の状況を理解したと思いますが、証明を行うための理論的知識が不足しており、それについて言及しているソースを見つけることができませんでした。私の理解が正しければ、隣接行列の半分のスペースを節約できます。そうでなければ、かなり奇妙なバグが発生する可能性があります。ですから、私は確信したいと思います。より堅実な背景を持つ誰かが私の推論を見直していただければ幸いです.

n * n 隣接行列で n 個の頂点の DAG を表し、頂点から頂点へのエッジがある場合はエントリi,jが、そうでない場合はエントリがあるとします。グラフは有向で非巡回であるため、if 、thenに従います。_{i n}のノードのトポロジー レベルがi _n-1のノード以上になるようにマトリックス内のノードを並べ替えると、隣接マトリックスの半分には常にsのみが含まれるように思えます。、次の例のように:1ij0i,j = 1j,i = 00

たぶん私は正しいのですが、これを確認する正式な方法はありますか?

以下は、ハッシュ マップに保存したデータ セットです。2 つの値の間の最短パスを見つける必要があります。

ハッシュ マップのキー値は各行の最初の値で、残りは 9244 の想定される "友達" です (いずれの場合も同じ)。

私はこの形式でハッシュテーブルに保存しました: hashmap(key, array)、ここで:

• キーは例えば 9244 です
• 配列は[4322、4886、5989、8598、9979、1447、9657]を保持します

2 つのキー間の最短経路を見つける方法は?

二部グラフの場合、隣接行列をその二隣接行列と呼ばれるものに置き換えることができます。

部分が r 頂点と s 頂点を持つ 2 部グラフの隣接行列 A は、次の形式を持ちます。

ここで、B は r × s 行列、O はすべてゼロの行列です。明らかに、行列 B は二部グラフを一意に表し、一般にその二隣接行列と呼ばれます。

現在、DAG は 2 部グラフです。たとえば、トポロジー的に並べ替えて、セット U と V をそれぞれ奇数または偶数のトポロジー レベルにあるノードにすることができます。

^{これは、n 個のノードを持つ DAG の場合、 2}行列ではなく(n/2) ²行列 (平均)のみが必要であることを意味します。問題は、それを構築する方法がわからないことです。ヒントはありますか？

あるノードからの有向巡回グラフの最短経路の例が必要です (入力となるノードからグラフのすべてのノードに到達する必要があります)。

例があれば、C ++またはアルゴリズムで必要です。

書き直す必要がある KSPA のカスタム実装があります。現在の実装では、修正されたダイクストラのアルゴリズムが使用されています。その疑似コードは、以下で大まかに説明されています。これは一般に、エッジ削除戦略を使用した KSPA として知られていると思います。（私はグラフ理論の初心者です）。

アルゴリズムを理解しているように、k 番目の最短パスを取得するには、各ソースと宛先のペアの間に「k-1」SPT が見つかり、1 つの SPT からそれぞれ「k-1」エッジがすべての組み合わせで同時に削除されます。明らかに、このアルゴリズムには組み合わせの複雑さがあり、大きなグラフでサーバーを詰まらせます。人々はエプスタインのアルゴリズムを提案してくれました ( http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf )。しかし、このホワイト ペーパーでは「ダイグラフ」について言及していますが、それがダイグラフに対してのみ機能するという記述は見当たりませんでした。無向グラフでこのアルゴリズムを使用したことがある人はいますか?

そうでない場合、無向グラフに KSPA を実装するための (時間の複雑さに関して) 優れたアルゴリズムはありますか?

前もって感謝します、

私は幾何学的な無向平面グラフを持っています。これは、各ノードに位置があり、2 つのエッジが交差しないグラフであり、エッジが交差していないすべてのサイクルを見つけたいと考えています。

この問題に対する既知の適切な解決策はありますか?

私がやろうとしているのは、一種のA*ような解決策です:

• パスとして最小ヒープにすべてのエッジを挿入します
• すべてのオプションで最短経路を延長する
• 開始点以外にループバックするパスをカリングします (必要ない場合があります)。
• 指定されたエッジで ang を使用する 3 番目のパスをカリングします

誰もこれに問題があると思いますか? それは機能しますか？

与えられた：

• 有向グラフ
• ノードにはラベルがあります
• 同じラベルが複数回表示される場合があります
• エッジにラベルがありません

ノードのラベルを考慮に入れて等しい最大の（接続された）サブグラフのセットを見つけたいと思います。

グラフは巨大になる可能性があります（数百万のノード）誰かがこれに対する効率的な解決策を知っていますか？

私はアルゴリズムと理想的にはJavaの実装を探しています。

更新：この問題はおそらくNP完全であるため。また、近似解を生成するアルゴリズムにも興味があります。

これは少なくとも近いようです： 頻繁なサブグラフ

半順序を表す有向非巡回グラフ (DAG)をエンコードする XML ファイルがあります 。このようなグラフは、依存関係の指定やクリティカル パスの検索などに役立ちます。興味深いことに、私の現在のアプリケーションはビルド システムのコンポーネントの依存関係を指定することなので、頂点はコンポーネントであり、エッジはコンパイル時の依存関係を指定します。簡単な例を次に示します。

この DAG は次のように描画できます。

_{（出典：iparelan.com）}

半順序の最小要素に対応する頂点のみを含む別の XML ドキュメントを生成するXSLT スタイルシートを適用したいと考えています。つまり、着信エッジを持たない頂点です。サンプル グラフの最小頂点のセットは です。私のビルド依存関係アプリケーションでは、このセットを見つけることは価値があります。なぜなら、このセットのメンバーをビルドすると、プロジェクト内のすべてがビルドされることがわかっているからです。{A, B, F}

これが私の現在のスタイルシート ソリューションです (Apache Ant のxsltタスクを使用して、Java 上の Xalan でこれを実行しています)。重要な観察事項は、最小頂点はどのdirected-edge-to要素でも参照されないということです。

このスタイルシートを適用すると、次の出力が生成されます (これは正しいと思います)。

問題は、私はこのソリューションに完全に満足していないということです。のとのを XPath 構文と組み合わせる方法があるかどうか疑問に思っています。selectfor-eachtestif

私は次のようなものを書きたい：

current()しかし、関数は外側の//vertex式によって選択されたノードを参照しないため、それは私が望むことではありません。

これまでのところ、私のソリューションではXPath 1.0とXSLT 1.0の構文を使用していますが、XPath 2.0とXSLT 2.0の構文も受け入れています。

必要に応じて、Ant ビルド スクリプトを次に示します。

dotターゲットは、グラフをレンダリングするための Graphviz Dot 言語コードを生成し ます 。ここにあるxml-to-dot.xsl：

プレーンをセクションにスライスするノードとエッジを持つ平面グラフがあります。nes

およびとsの関数としての上限は何ですか？nee/n

使用しているコードで信頼できるメモリがどれだけ少ないかを見つけようとしています。

eそれはそれ以上ではないことを示すのは簡単ですn*(n-1)/2が、私はそれが小さな整数になるだろうと感じています。ノード位置が固定されているn ~= 10場合、制限を2倍過大評価します。