問題タブ [graph-theory]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - 次数が隣の頂点よりも小さいグラフ内のすべての頂点を見つける
グラフ内のすべての頂点のセットを、隣接する頂点よりも小さい次数で見つけるアルゴリズムを作成しようとしています。私の最初のアプローチは、各頂点の次数を見つけてから、リストを調べて、各頂点の次数をその近傍の次数と比較することです。残念ながら、これには非常に時間がかかるようです。このセットを見つけるより効率的な方法はありますか?
algorithm - 関数型言語 (Haskell) の高速要素検索
グラフをトラバースしていて、ノードが以前に見られたかどうかをすばやく判断したいとします。いくつかの前提条件が設定されています。
- ノードは整数値 1..N でマークされています
- グラフは、隣接リストを持つノードで実装されます
- 1..N のすべての整数値がグラフに出現し、サイズは N です。
純粋に機能的な方法でこれを行うためのアイデアはありますか?(ハッシュテーブルまたは配列は許可されていません)。
2 つの関数が動作するデータ構造が必要です。add (遭遇した整数を追加) および lookup (整数が追加されたかどうかをチェック)。どちらも、N回の繰り返しで償却されるO(n)時間かかることが望ましいです。
これは可能ですか？
algorithm - グラフの最小パスとは?
グラフ理論では、最小距離 (ダイクストラのアルゴリズムが検出する) と最小パス (それが何であるかはわかりません) の違いは何ですか?
algorithm - 優先パートナーを 3 つのグループに一致させるアルゴリズム
この問題を解決するための良いアルゴリズムは何ですか?
グループ A、グループ B、グループ C の 3 つのグループがあります。各グループの人数は同じです。彼らはそれぞれ、喜んで協力してくれる他のグループのメンバーのリストを持っています。私はこれらすべての人々を 3 つのグループ (A から 1 人、B から 1 人、C から 1 人) にグループ化し、グループ内の全員がグループ内の他の人々と協力したいと思うようにしたいと考えています。
これらのグループをすばやく見つけるにはどうすればよいですか? 全員を幸せにする方法がない場合、アルゴリズムは、最初に、互いに協力したい 3 人を含むグループをできるだけ多く作成し、次に、他のグループのできるだけ多くの人を幸せにする必要があります。
最後のポイント: 人々は誰と一緒に働きたいかについて合意します (もし x が y と働きたいのなら、y も x と働きたいと思うでしょう)。また、アルゴリズムの実行時間の大きな O を与えることができれば、それは素晴らしいことです!
graph-theory - トーナメント グラフの質問
トーナメントグラフは有向完全グラフと同じですか? また、トーナメント グラフのすべての頂点の辺の数は同じですか?
networking - グラフの画像/グラフィックの生成
ネットワーク全体の最短パス アルゴリズムに取り組んでいるときに、ネットワークの全体像を生成したいと考えています。ノード (円)、リンク (線)、リンクを通過するコスト (リンク線の中央の数字)、およびリンクの容量 (それが表すノードの横のリンク線の数字) を表現したいと思います。写真の中の。この画像の作成を自動化するのに役立つライブラリ/ソフトウェアはありますか?
これは、Visio または描画アプリケーションで手動で行うことができますが、ネットワークを変更/微調整するときにコードから生成したいと考えています。
graph-theory - トーナメント グラフの支配的なセット
トーナメント グラフの支配的なセットを見つけるアルゴリズムを作成しています。有向グラフの最小全域木は、グラフの支配集合と同等ですか? 言い換えれば、トーナメント グラフの最小の MST を (すべての頂点を反復することによって) 見つけた場合、これはグラフの支配的なセットと同等であると言えますか?
algorithm - 少なくとも 2 つの要素を共有するセットをマージするアルゴリズム
セットのリストが与えられた場合:
- S_1 : [ 1, 2, 3, 4 ]
- S_2 : [ 3, 4, 5, 6, 7 ]
- S_3 : [ 8, 9, 10, 11 ]
- S_4 : [ 1, 8, 12, 13 ]
- S_5 : [ 6, 7, 14, 15, 16, 17 ]
少なくとも 2 つの要素を共有するすべてのセットをマージする最も効率的な方法は? これは連結成分の問題に似ていると思います。したがって、結果は次のようになります。
- [ 1, 2, 3, 4, 5, 6, 7, 14, 15, 16, 17] (S_1 ユニオン S_2 ユニオン S_5)
- [ 8, 9, 10, 11 ]
- [ 1, 8, 12, 13 ] (S_4 は S_1 と 1 を共有し、S_3 と 8 を共有しますが、それぞれで 1 つの要素しか共有しないため、マージされません)
単純な実装は O(N^2) です。ここで、N はセットの数であり、これは私たちには機能しません。これは、何百万ものセットに対して効率的である必要があります。
resources - グラフ構造のリソース?
グラフに関連する問題があります。私はコンピューターサイエンスの卒業生ではないため、グラフとは何かについての簡単な紹介が必要でした.グラフについて読んだり、c ++または一般的にグラフ関連の問題を解決する方法を読んだりできますか.
mysql - SQLでベイジアンネットワーク、またはより一般的には有向加重グラフをモデル化する方法は？
SQLでさまざまな種類のグラフ（特にDAG）をモデル化する方法の例を提供する記事をオンラインでいくつか見つけましたが、モデル化するものが比較的単純であることを考えると、それらはすべて非常に複雑に見えました。
これを行うための最良/標準的な方法はありますか？私の現在の考え方は次のようなものです。
何か問題がありますか？より良い（おそらくより堅牢な）方法を知っている人はいますか？