トポロジカルソートと順序集合間の類似点
トポロジカルソートと順序集合は(ユニオンペディアに)共通で4ものを持っています: 二項関係、グラフ理論、全順序、有向非巡回グラフ。
二項関係
数学において、二項関係(にこうかんけい、binary relation)あるいは二変数関係 (dyadic relation, 2-place relation) は、集合 の元からなる順序対のあつまりである。別な言い方をすれば、直積集合 の部分集合を、集合 上の二項関係と呼ぶ。あるいはもっと一般に、二つの集合 に対して、 と との間の二項関係とは、直積 の部分集合のことをいう。 二項関係の一つの例は素数全体の成す集合 と整数全体の成す集合 の間の整除関係である。この整除関係では任意の素数 は、 の倍数である任意の整数 に関係を持ち、倍数でない整数には関係しないものとして扱われる。例えば、素数 が関係を持つ整数には などが含まれるが や は含まれない。同様に素数 が関係する整数として などが挙げられるが、 や はそうではない。 二項関係は数学のさまざまな分野で用いられ、不等関係、恒等関係、算術の整除関係、初等幾何学の合同関係、グラフ理論の隣接関係、線型代数学の直交関係などのさまざまな概念が二項関係として定式化することができる。また、写像の概念を特別な種類の二項関係として定義することもできる。二項関係は計算機科学においても重用される。 二項関係はn-項関係 (各 -番目の成分が関係の -番目の始集合 からとられているようなn-組からなる集合)で とした特別の場合である。 ある種の公理的集合論では(集合の一般化としての)類の上の関係を考えることができる。このような拡張は、集合論における元の帰属関係や包含関係の概念(に限った話ではないが)のモデル化を、ラッセルの逆理のような論理矛盾に陥らずに行うために必要である。.
グラフ理論
ラフ理論(グラフりろん、graph theory)は、ノード(節点・頂点)の集合とエッジ(枝・辺)の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.
グラフ理論とトポロジカルソート · グラフ理論と順序集合 ·
全順序
数学における線型順序(せんけいじゅんじょ、linear order)、全順序(ぜんじゅんじょ、total order)または単純順序(たんじゅんじゅんじょ、simple order)は、推移的、反対称かつ完全な二項関係を言う。集合と全順序を組にしたものは、全順序集合 (totally ordered set), 線型順序集合 (linearly ordered set), 単純順序集合 (simply ordered set) あるいは鎖 (chain) と呼ばれる。 即ち、集合 X が関係 ≤ によって全順序付けられるとき、X の任意の元 a, b, c に対して、以下の条件 が満足される。 反対称性によって a < b でも b < a でもあるような不確定な状態は排除される。完全性を持つ関係は、その集合の任意の二元がその関係でであることを意味する。これはまた、元を直線に並べた図式によってその集合が表せるということでもあり、それは「線型」順序の名の由来である。また完全性から反射性 (a ≤ a) が出るから、全順序は半順序の公理を満たす。半順序は(完全性の代わりに反射性のみが課されるという意味で)全順序よりも弱い条件である。与えられた半順序を拡張して全順序をえることは、半順序のと呼ばれる。.
有向非巡回グラフ
有向非巡回グラフ、有向非循環グラフ、有向無閉路グラフ(ゆうこうひじゅんかいグラフ、Directed acyclic graph, DAG)とは、グラフ理論における閉路のない有向グラフの事。有向グラフは頂点と有向辺(方向を示す矢印付きの辺)からなり、辺は頂点同士をつなぐが、ある頂点 v から出発し、辺をたどり、頂点 v に戻ってこないのが有向非巡回グラフである。 有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は半順序を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回グラフで表現できる。トポロジカルソートを使うと、妥当な順序を手に入れることが出来る。加えて、有向非巡回グラフは一部が重なるシーケンスの集合を表現する際の空間効率の良い表現として利用できる。また、有向非巡回グラフはイベント間の因果関係を表現することにも使える。さらに、有向非巡回グラフはデータの流れが一定方向のネットワークを表現することにも使える。 無向グラフにおける対応する概念は森で、森は閉路のない無向グラフである。森から方向を選ぶと polytree と呼ばれる特殊な有向非巡回グラフを作ることが出来る。しかしながら、無向非巡回グラフ(森)に方向付けする方法では作れない有向非巡回グラフがあり、全ての無向グラフは acyclic orientation があるため、辺に方向付けると有向非巡回グラフになる。この理由から、directed acyclic graph と呼ぶよりも acyclic directed graph と呼ぶ方が正確である。 なお、有向非巡回グラフをプロトコルとした仮想通貨に、BYTEBALL、IOTAがある。.
上記のリストは以下の質問に答えます
- 何トポロジカルソートと順序集合ことは共通しています
- 何がトポロジカルソートと順序集合間の類似点があります
トポロジカルソートと順序集合の間の比較
順序集合が56を有しているトポロジカルソートは、16の関係を有しています。 彼らは一般的な4で持っているように、ジャカード指数は5.56%です = 4 / (16 + 56)。
参考文献
この記事では、トポロジカルソートと順序集合との関係を示しています。情報が抽出された各記事にアクセスするには、次のURLをご覧ください: