グラフの密度

1. 概要

このチュートリアルでは、グラフの密度について説明します。 さまざまなグラフの密度を計算する方法を例を挙げて説明します。

2. 密度とは何ですか？

グラフ密度は、グラフに存在するエッジと、グラフに含めることができるエッジの最大数との比率を表します。概念的には、エッジの接続性に関してグラフの密度を示します。

これは、広大なネットワークがあり、ネットワークに新しいエッジを追加したい場合に特に便利です。 さらに、グラフの密度から、ネットワークに追加できるエッジの数がわかります。

ここで、グラフ密度の式を導出する前に、単純な有向および無向グラフのエッジの最大数を計算する方法について説明しましょう。 単純な無向グラフを見てみましょう：

ここで、グラフにはノードとエッジが含まれています。 含めることができるエッジの最大数を知ることに関心があります。 それでもエッジを追加できますか？ どれどれ：

グラフにエッジを追加しました。 したがって、グラフにはノードとエッジが含まれるようになりました。 これ以上エッジを追加することはできません。 ここで、標準式を導出して、単純な無向グラフのエッジの最大数を計算します。

次の式を確認してみましょう：

同様に、各無向エッジを有向グラフの2つの双方向エッジに置き換えることができます。したがって、エッジの最大数は、同様の式を使用して計算できます。

これで、グラフ密度の式を定義できます。 グラフに存在するエッジは、グラフに含めることができるエッジの最大数で除算されます。 単純な無向グラフの式を見てみましょう：

同様に、有向グラフの以前の密度式を書き直すことができます：

3. プロパティ

完全な有向グラフまたは無向グラフの場合、密度は常に です。したがって、定義を思い出せば、このプロパティを簡単に確認できます。 密度は、グラフに存在するエッジを可能な最大エッジで割った比率です。 完全な有向グラフまたは無向グラフの場合、すでに最大数のエッジがあり、これ以上エッジを追加することはできません。 したがって、密度はになります。 さらに、グラフが完全に密集していることも示します。

すべての孤立した頂点を持つグラフの密度はです。さらに、グラフにエッジがなく、グラフに追加できるエッジの数は次のようになります。エッジの最大数。

4. 例

このセクションでは、有向グラフと無向グラフの密度を計算します。 最初に有向グラフを見てみましょう：

有向グラフには頂点とエッジがあります。 しかし、密度を計算するには、まず、次の場所で可能なエッジの最大数を計算する必要があります。

最後に、密度を計算するために、に存在するエッジの数を最大エッジ数で除算します。

同様に、無向グラフを見てみましょう：

無向グラフには頂点とエッジがあります。 まず、次のエッジの最大数を計算します。

最後に、密度を計算するために、に存在するエッジの数を最大エッジ数で除算します。

5. 結論

このチュートリアルでは、グラフ密度について詳しく説明しました。 まず、グラフ密度の式を導き出しました。 また、有向グラフと無向グラフを使用した計算についても説明しました。