グラフの隣接性と発生率

1. 序章

このチュートリアルでは、グラフの隣接性と発生率について説明します。また、それらを使用してグラフを表す方法も示します。

コンピュータサイエンスでは、グラフは頂点とエッジのセットで構成されるデータ構造です。エッジは頂点のペアです。ここで、。たとえば、次の図は、頂点とエッジのあるグラフを示しています。

グラフ内の2つの頂点がエッジで接続されている場合、頂点は隣接していると言えます。グラフの例では、頂点には2つの隣接する頂点とがあります。このプロパティに基づいて、隣接行列または隣接リストを使用してグラフを表すことができます。

頂点を含むグラフがあるとすると、正方行列を使用して、これらの頂点間の隣接関係を表すことができます。たとえば、サンプルグラフの隣接行列は次のとおりです。

この行列では、数字は対応する2つの頂点が隣接していることを意味します。それ以外の場合、エントリ値はです。エントリがあるため、隣接行列の空間の複雑さはです。

隣接行列を作成するには、すべてのエッジを調べて、対応する頂点-頂点エントリに1を設定します。したがって、この行列を作成するための時間計算量は、です。ここで、はグラフのエッジの数です。

隣接リストを使用してグラフを表すこともできます。たとえば、サンプルグラフの隣接リストは次のとおりです。

このテーブルの各行には、現在の頂点に隣接する頂点のリストが含まれています。各ペアは、グラフのエッジを表します。したがって、隣接リストのスペースの複雑さはです。同様に、隣接リストを作成するための時間が必要です。

エッジの数がのオーダーである密グラフの場合、隣接行列と隣接リストは同じ時間と空間の複雑さを持ちます。ただし、グラフがまばらな場合は、グラフを表すために必要なスペースが少なくて済みます。したがって、スパースグラフで作業する場合、隣接リストは隣接行列よりもスペース効率が高くなります。

ただし、隣接行列をより効率的に使用できるグラフ操作がいくつかあります。たとえば、グラフにエッジが存在するかどうかを確認する場合、隣接行列を一定時間で検索するだけで結果を得ることができます。隣接リストを使用すると、確認に時間がかかります。

もう1つの例は、グラフからエッジを削除することです。隣接行列では、対応するエントリを一定時間で設定できます。ただし、隣接リストから頂点を削除するには時間が必要です。

グラフで、2つのエッジが共通の頂点を共有している場合、それらは入射します。たとえば、エッジとエッジは同じ頂点を共有しているため、入射します。

また、頂点上の発生率を定義できます。頂点がエッジが接続する2つの頂点のいずれかである場合、頂点はエッジへの入射です。したがって、入射は、が頂点であり、がに入射するエッジであるペアです。

このプロパティに基づいて、接続行列を使用してグラフを表すことができます。たとえば、サンプルグラフの接続行列は次のとおりです。

このマトリックスでは、行は頂点を表し、列はエッジを表します。したがって、接続行列の空間の複雑さはです。接続行列を作成するには、すべてのエッジを調べて、対応する頂点エッジエントリに1を設定します。したがって、この行列を作成するための時間計算量はです。

グラフの接続行列と隣接行列の関係は、単位行列です。

接続行列は、他のグラフ表現よりも空間が複雑です。通常、理論グラフ領域で使用します。例：グラフのインシデントカラーリング。

この記事は、グラフ理論における隣接と発生率の定義を提供しました。また、隣接と発生率を使用してグラフを表すさまざまな方法を示しました。