1. 概要
このチュートリアルでは、グラフ理論におけるスパースグラフとデンスグラフの違いを学習します。
まず、グラフのサイズと順序の概念について説明し、そこからグラフ密度の定義を導き出します。
次に、グラフの密度に関連して、疎グラフと密グラフの2つのカテゴリを定義します。
このチュートリアルの最後では、グラフの密度の概念に精通し、メモリストレージの観点からの密度の意味も理解します。
2. グラフの密度
2.1. グラフ密度の一般的な考え方
グラフ理論の紹介記事では、この分野の基本的な概念について説明しました。 頂点やエッジなどのアイデアの意味についてのリフレッシュが必要な場合は、この記事を読みながら参照できます。
この記事では、代わりに、グラフのサイズと順序に関連するグラフ密度の概念について説明します。 グラフ密度の概念が何を意味するかを直感的に理解するために、5つの頂点と4つのエッジを含むサンプル無向グラフを使用できます。
このグラフでは、またはなど、多くの頂点が接続されていないことがわかります。 これにより、頂点の数を変更せずにエッジを追加すると、グラフがやや「密度が高く」なることが想像できます。
また、グラフが最大に密集している2つの極端なケースが存在することも想像できます。
または、逆に、最小限の密度：
これらのグラフを比較することにより、グラフ密度に関する次の一般的な概念を導き出すことができます。 密度は、グラフが持つエッジの数と頂点の数の観点から、グラフがどれだけ「完全」であるかを示すメトリックです。
これにより、グラフの密度がどうあるべきかについていくつかの期待値を定式化できます。本質的に連続的であり、エッジの数とエッジの最大数の関係を次の関数として表す密度メトリックが必要です。頂点の数。 最後に、このメトリックをある程度標準化し、頂点の数が異なるグラフを比較できるようにする必要もあります。
これは、の形式のグラフの密度の測定値を探していることを意味します。 この測定値は、完全にまばらなグラフを表すとと、完全に密なグラフを表すとの間で変化する必要があります。 それを計算する方法をすぐに見ていきます。 ただし、最初に、グラフでサイズと順序を定義する必要があります。
2.2. グラフのサイズと順序
密度を決定するには、グラフのエッジの最大数を知る必要があると述べました。 それを計算するには、グラフのサイズと次数という2つの追加のメジャーを使用する必要があります。
グラフのサイズは、単にグラフに含まれるエッジの数です。 の場合、エッジのセットは空であるため、グラフ自体も空であると言えます。
代わりに、グラフの順序は、グラフに含まれる頂点の数です。 フォームのグラフはグラフではないので、次のように言うことができます。 2つのグラフがである場合、2つのグラフは空で同等です。 結果として、密度は同じであると予想されます。
この考慮事項を、2つの空のグラフの順序が同じでない場合に拡張できます。 この点に関して、2つの空のグラフと異なる次数のグラフ、したがって、を使用したグラフも同様に密集していると言えます。
これにより、空のグラフの密度をゼロにする必要があることを示すことができます。ただし、グラフのサイズがnullでない場合、同じサイズのグラフは必ずしも同じ密度であるとは限りません。
これは、密度がグラフのサイズに比例するだけでなく、その次数の関数にも反比例することを意味します。
2.3. エッジの最大数
密度に反比例する次数の関数はエッジの最大数であり、これは次数に依存しますが、グラフのサイズには依存しません。 無向グラフの順序に関連するエッジの最大数は、次のように定義できます。
これまでのところ、グラフは無向であると想定していることに注意してください。 ただし、この式を有向グラフに拡張することはできます。
有向グラフと無向グラフの比較に関する記事で説明したように、後者は常に対称隣接行列を持っていますが、前者は必ずしもそうではありません。 有向グラフは、この条件を満たさないため、可能なエッジの数が2倍になります。 結果として、エッジの最大数を次のように計算できます。
これで、グラフの密度を正式に定義するために必要なすべての要素が揃いました。
3. グラフの密度
3.1. 密度の正式な定義
使用するグラフの密度の式は、上記で提供したサイズ、順序、およびエッジの最大数の定義を利用しています。 無向グラフの場合、密度は次のとおりです。
同様に、有向グラフの密度測定値を定義することもできます。 上記のように、グラフが有向の場合、エッジの最大数は、対応する無向グラフに対して計算した数の2倍になります。 結果として、有向グラフの場合、それらの密度を対応する無向グラフの半分として計算できます。
予想どおり、両方の密度が区間にどのように含まれているかにも注意してください。 さらに、空のグラフを示し、完全に接続されたグラフを示す方法に注意してください。 この方法で密度を定義した後、密度に関連するスパースグラフとデンスグラフの定義を行うことができます。
3.2. スパースグラフとデンスグラフ
スパースグラフは、密度が密度の終域のより低い範囲にあるグラフです。 同様に、密グラフは、密度が終域のより高い範囲にあるグラフです。 スパースグラフまたはデンスグラフとして無差別に扱うことができるグラフですが、どちらとも見なさないことをお勧めします。
これで、 type に関連して、グラフの密度のいくつかの一般的な特性を表すことができます。
- 次数のグラフの密度は、代数的な理由と、完全に疎または完全に密であると見なすことができるため、直感的には定義されていません。
- 空のグラフはすべて密度が0であるため、まばらです。
- すべての完全グラフの密度は1であるため、密度が高くなります。
- 無向トレーサブルグラフは少なくともの密度を持っているので、
- 有向追跡可能なグラフが密であることが保証されることはありません
- トーナメントの密度は、その順序に関係なく、
3.3. グラフの密度の例
グラフの密度を計算する方法がわかったので、実際の演習に適用できます。 このチュートリアルで最初に遭遇したグラフを例として取り上げます。
このグラフの形式は、ここで、およびです。 したがって、最初の2つの特性はとです。 グラフは無向であるため、エッジの最大数を次のように計算できます。
これから、グラフの密度を次のように計算できます。
なぜなら、それはまばらなグラフであると結論付けることができます。
代わりに、グラフに2つの余分なエッジしかない場合。 と言うと、次のようになります。
また、関連する計算は次のように変更されます。
これにより、拡張グラフが密グラフになります。
4. グラフの密度とメモリストレージ
この記事の結論として、プログラミングにおけるグラフの密度が重要である実際的な理由を指摘することができます。 これは、グラフをメモリに保存することと関係があります。 グラフは非常に大きくなる傾向がありデータ構造、知識表現などの一部のアプリケーションでは、予防策を講じない限り処理できない可能性があります。
そのような予防策の1つは、密度に関連して、より効率的な形式でグラフを保存することです。 どのグラフも、次の2つの方法でデータ構造として表すことができます。
- エッジのリストとして
- または、隣接行列として
これらのオブジェクトは、メモリ使用量とアクセスに関して大幅に異なる方法で実行されます。 ただし、原則として、作業しているグラフの密度によって、保存に適した方法が決まります。
- グラフがまばらな場合は、エッジのリストとして保存する必要があります
- または、グラフが密集している場合は、隣接行列として保存する必要があります
5. 結論
この記事では、グラフの密度の定義を、そのサイズ、順序、およびエッジの最大数に関連して調べました。
次に、密度の観点から、いくつかの特殊なタイプのグラフの特性について説明しました。
結論として、グラフを表すために使用する必要があるデータ構造の決定において、グラフの密度が果たす役割についても検討しました。
