有向グラフと無向グラフの違いは何ですか
1. 概要
このチュートリアルでは、有向グラフと無向グラフの違いを学習します。 また、どちらか一方を使用する方がよい場合についても学習します。
最初に、グラフとネットワーク理論の関係、およびグラフと情報理論の関係について説明します。 そうすることで、有向グラフと無向グラフを比較できるグラフのエントロピーの定義を学習します。
2. グラフ、エッジ、および関係
2.1. グラフまたはネットワーク？
プログラマーはネットワークについて頻繁に話しますが、議論がグラフに移ると混乱することがよくあります。 常識的なグラフは、関数の比喩的な表現です。
与えられた関係によってリンクされている、またはリンクされていないノードのセットで構成されるネットワークがあると想像してみましょう。
インターネットまたはLANはネットワークとしてモデル化でき、各要素はコンピューターであり、各リンクは接続です。 このネットワークは、要素が相互に作用し、そのコンポーネントの集合的な動作に還元できないことが多い、緊急の動作を引き起こすシステムと見なすことができます。
相互に関連する要素のネットワークは、自然界、社会システム、および情報学に見られ、ネットワーク理論と呼ばれる分野の研究の対象となっています。
ネットワーク理論の数学的な対応物であるグラフ理論では、ネットワークはグラフと呼ばれ、そのノードは頂点と呼ばれ、リンクのセットはエッジと呼ばれます。 この記事の残りの部分では、グラフ理論の用語を使用しますが、これはネットワーク理論に関連する用語に完全に対応していることに注意してください。
2.2. 情報理論のグラフ
グラフは、コンピュータサイエンスにおいて重要なデータ構造です。グラフを使用すると、オブジェクトの値だけでなく、オブジェクト間に存在する関係も処理できるからです。 コンピュータサイエンスにおけるグラフのいくつかの典型的なアプリケーションには、知識表現、シンボリック推論、マルチエージェントシミュレーション、および動的システムのモデリングが含まれます。
グラフは、情報理論の観点から十分に研究されているため、重要です。 この記事では、有向グラフと無向グラフの違いについて説明しているため、グラフの1つの重要な特性であるエントロピーの測定に関心があります。
後で説明するように、エントロピーの観点から代償を払わずに、有向グラフと無向グラフを等しいかのように扱うことはできません。
2.3. グラフとエントロピー
グラフのエントロピーの一般的な定義の1つは、いわゆる隣接行列です。 グラフの隣接行列は、すべての行と列がそのグラフに属する頂点のセットを表す行列です。
隣接行列では、すべての行が潜在的なエッジのテールまたは開始を示し、列がそのエッジのヘッドまたはターゲットを示します。
隣接行列のセルは、2つの頂点の間にエッジが存在するかどうかに応じて、それぞれ1または0の値を持つことができます。
基になるグラフに要素がある場合、関連する隣接行列には要素があります。 この方法で隣接行列を定義すると、ランダムに分散されたバイナリ変数のシャノンの式を使用して、エントロピーの測定値を計算できます。
そのためには、最初に隣接行列を確率変数に変換する必要があります。 これを行うには、隣接行列を平坦化します。 平坦化とは、インデックスを使用して各要素にランダムに分散された変数内の一意の位置を割り当てることを意味します。
次に、この変数を上記の式に挿入して、特定のグラフのエントロピーの一意の値を計算できます。
グラフのエントロピーの概念は重要です。 これが、後で説明するように、有向グラフを無向グラフとして扱うことができない主な理由です。
3. 有向グラフ
3.1. 有向グラフの定義
有向グラフは、頂点間に確立されたエッジの対称性または相反性を想定しないグラフのクラスです。 有向グラフでは、とがエッジで接続された2つの頂点である場合、これは必ずしもエッジ接続も存在することを意味するわけではありません。
有向エッジは通常、始点の頂点または矢印の尾から離れて、終点の頂点または矢印の頭に向かう矢印として表されます。 有向グラフは、エッジによってモデル化された関係に対称性の制限的な仮定を課さないため、最も一般的な種類のグラフです。
3.2. 有向グラフの一般的な使用法
このタイプのグラフは、特定の種類の実世界の構造のモデリングでも一般的です。 最も一般的な有向グラフは、おそらく、子孫とその親の間の関係をマップする系統樹または系統樹です。
家系図では、各頂点は同時に異なる関係の親と子孫になることができますが、同じ関係では同時にできません。
ある個人が同時に別の個人の親と子になることは意味がありません。 結果として、家系図を表すグラフは、必然的に有向グラフでなければなりません。
4. 無向グラフ
4.1. 無向グラフの定義
無向グラフはより具体的です。 それらの場合、エッジで接続された頂点のペア間の関係の相互関係に関する追加の仮定があります。 2つの頂点との間にエッジが存在する場合、エッジは次のようにも存在します。
無向グラフは、ある意味で、階層的な性質を持つ関係のモデリングを許可しないため、有向グラフよりも制限が厳しくなります。 ただし、これらは実際には非常に一般的であり、多くの実際の関係は無向グラフによって最もよくモデル化されます。 これは通常、エッジの両方の頂点がその関係の対象になる可能性がある場合に当てはまります。
たとえば、「の友達」という関係は、典型的な対称関係です。 これは、「マークがジョンの友達である」とすれば、「ジョンはマークの友達である」ということも事実であると推測できるからです。 前述の「の親である」関係では、これが当てはまらなかったことに注意してください。
4.2. 無向グラフの一般的な使用法
コンピュータサイエンスで最も人気のある無向グラフの1つは、コンピュータネットワークの接続のトポロジです。 あるデバイスが別のデバイスに接続されている場合、2番目のデバイスも最初のデバイスに接続されていると想定できるため、グラフは無向です。
無向グラフの他の一般的な例には、デジタルソーシャルネットワークのトポロジが含まれます。ここで、誰かの各友人はその誰かの友人です。 だけでなく、歩行者の経路もあります。この場合、経路の任意の2つの交差点間の移動が両方向に可能です。
4.3. 対称有向グラフは無向グラフです
これで、無向グラフの別の定義を与えることができます。 この定義は、有向グラフの定義に基づいて作成され、それに依存しています。 隣接行列が主対角線に沿って対称である場合、グラフは無向です。
この定義を使用すると、任意の有向グラフに対応する単一の無向グラフを見つけることができます。 これにより、2つのクラスのグラフを情報理論の用語で比較できるため、これは重要です。
複数の有向グラフが同じ無向グラフに対応する可能性があるという意味で、反対は必ずしも真実ではないことに注意してください。
私たちの定義では、2つの隣接行列と、それぞれ有向グラフと無向グラフのは、との場合に互いに対応し、また、を意味するすべての場合に対応します。
2つの行列がこの条件を満たす場合、シャノンのエントロピーの尺度を使用して2つのグラフを比較できます。
5. 有向グラフと無向グラフのエントロピー
5.1. どのような条件下でそれらを比較できますか？
上で定義され、このセクションで従う条件は非常に制限されています。 これは、比較している2つのグラフ、有向グラフと無向グラフに同じ頂点が含まれていることを意味します。
ただし、必ずしも同じエッジが含まれているとは限りません。 簡単に言うと、無向グラフには、任意の2つのノード間に2つの有向エッジがあり、有向グラフでは、少なくとも1つの有向エッジがあります。
この条件は少し制限がありますが、2つのグラフのエントロピーを一般的に比較することができます。 これは次の方法で実行できます。
5.2. 有向グラフと無向グラフのエントロピーの比較
それが有向グラフの有向エッジの数であると仮定しましょう。 対応する無向グラフには、対称の場合は、と、反対方向の2つのエッジがない場合は、の間で変化するエッジの数があります。
有向グラフの隣接行列に関連付けられたランダムバイナリ変数を呼び出しましょう。 隣接行列に関連付けられたランダムなバイナリ変数。
可能な合計のうちのエッジが存在する場合、のエントロピーは次のようになります。
のエントロピーは、が対称である場合に等しくなります。 ただし、反対側のエッジがない場合は、次のようになります。
これらの2つのケースは、可能なグラフ構造の分布の極値と見なすことができます。 ここで、エントロピーの2つの測定値が、頂点を持つ参照グラフでどのように比較されるかを見てみましょう。
上の図は、とを除いて、一般的にを示しています。 つまり、原則として、有向グラフを無向グラフとして扱うことはできません。その逆も同様です。 私たちがそうする場合、私たちは通常、彼らの情報内容に関して代償を払います。
6. どちらを選択するか
最後に、有向グラフと無向グラフについて学んだことを要約できます。 使用するタイプを選択する方法に関するいくつかの指示があります。
- ネットワークがまばらな場合、有向グラフは対応する無向グラフよりも有益です。 これは、まばらな有向グラフを無向として扱うと、おそらく情報が失われることを意味します
- 有向グラフは、方向性があり、本質的に逆数ではないモデル関係に適しています。 良い例は、「の子である」という関係であり、その上に家系図を構築します
- 無向グラフは、存在するかどうかが重要であるが、本質的に推移的ではない関係にうまく適用されます。 たとえば、歩行者の経路を双方向に移動できる場合は、経路を無向グラフとしてモデル化できます。
- 同じシステムを、ある状況では有向グラフとして、他の状況では無向グラフとしてモデル化できます。 たとえば、子孫の研究に興味がある場合は、家族を有向グラフとして表すことができます。 ただし、クランの所属を調査している場合は、無向グラフとして表すことができます。
有向グラフと無向グラフは、それ自体、実世界の現象を数学的に抽象化したものです。 結果として、プログラマーは問題に適用するものを慎重に選択する必要があります。 グラフは、モデル化する関係のタイプに対応する必要があります。逆数の場合は無向、それ以外の場合は無向です。
7. 結論
この記事では、有向グラフと無向グラフの違いについて説明しました。 有向グラフには、方向性があり、必ずしも逆数ではないエッジがあります。 有向グラフの頂点が別の頂点に接続されている場合、それは必ずしも2番目の頂点が最初の頂点にも接続されていることを意味するわけではありません。
無向グラフは、より制限的な種類のグラフです。
一方のタイプのグラフを使用して、もう一方のタイプを概算できる場合があります。 ただし、そうする場合、情報コンテンツの観点から支払うコストがかかることがよくあります。
