隣接行列とは

この記事では、隣接行列とその表現について説明します。

プロローグ言語

隣接行列の定義

グラフ理論では、隣接行列は有限グラフ構造を記述する高密度の方法です。これは、グラフノード間の関連性をマッピングするために使用される 2D マトリックスです。

グラフに n 頂点の数の場合、そのグラフの隣接行列は次のようになります。 n×n 、行列の各エントリは、ある頂点から別の頂点までのエッジの数を表します。

隣接行列は次のように呼ばれることもあります。 接続マトリックス 。と呼ばれることもあります 頂点行列 。

隣接行列表現

無向グラフ G が n 個の頂点で構成される場合、グラフの隣接行列は n x n 行列 A = [aij] となり、次のように定義されます。

ある_ij= 1 {V からのパスが存在する場合_私Vへ_j}

ある_ij= 0 {そうでない場合}

隣接行列に関する重要な点をいくつか見てみましょう。

頂点 V の間にエッジが存在する場合_私とV_jここで、i は行、j は列であり、a の値_ij= 1。
頂点 V の間にエッジがない場合_私とV_j、次に a の値_ij= 0。
単純なグラフに自己ループがない場合、頂点行列 (または隣接行列) の対角には 0 が含まれている必要があります。
隣接行列は、無向グラフでは対称です。 i の値が^番目行とj^番目列は j の値と等しい^番目I列^番目
隣接行列がそれ自体で乗算され、i にゼロ以外の値が存在する場合^番目行とj^番目列にVからのルートがあります_私Vへ_j隣接行列のゼロ以外の値は、個別のパスの数が存在することを表します。

注: 隣接行列では、0 は 2 つのノード間に関連性が存在しないことを表し、1 は 2 つのノード間に関連性が存在することを表します。

隣接行列を作成するにはどうすればよいですか?

グラフがあるとします g と n 頂点の数を指定すると、頂点行列 (または隣接行列) は次の式で与えられます -

A = a_十一ある₁₂。。。。。ある_1nある₂₁ある₂₂。。。。。ある_2n。。。。。。。。。ある_n1ある_n2。。。。。ある_ん

個別の SQL をカウントする

どこに、_ij頂点 i から j までのエッジの数に等しい。上で述べたように、隣接行列は無向グラフでは対称であるため、無向グラフの場合、_ij= a_へー。

グラフが単純で、エッジまたは複数のエッジに重みがない場合、隣接行列のエントリは 0 と 1 になります。自己ループがない場合、隣接行列の対角エントリは 0 になります。

次に、無向グラフと有向グラフの隣接行列を見てみましょう。

無向グラフの隣接行列

無向グラフでは、エッジはそれらの方向に関連付けられません。無向グラフでは、頂点 A と頂点 B の間にエッジが存在する場合、頂点を A から B に転送することも、B から A に転送することもできます。

以下の無向グラフを考えて、その隣接行列を構築してみます。

このグラフでは、自己ループがないことがわかります。そのため、隣接する行列の対角要素は 0 になります。上記のグラフの隣接行列は、次のようになります。

サルマン・カーンの年齢

有向グラフの隣接行列

有向グラフでは、エッジは順序付きペアを形成します。エッジは、ある頂点 A から別の頂点 B への特定のパスを表します。ノード A は初期ノードと呼ばれ、ノード B は終端ノードと呼ばれます。

以下の有向グラフを考えて、その隣接行列を構築してみましょう。

上のグラフでは、自己ループがないことがわかります。そのため、隣接する行列の対角要素は 0 になります。上のグラフの隣接行列は、次のようになります。

隣接行列のプロパティ

隣接行列のプロパティの一部を以下に示します。

隣接行列は、(V の位置に数値 0 と 1 を含む単純なラベル付きグラフを表すために使用される行と列を含む行列) です。_私、で_j)、2 つの V かどうかの条件に従って_私とV_j隣接している。
有向グラフの場合、頂点 i または V の間にエッジが存在する場合_私頂点 j または V へ_j、次に A[V の値_私][で_j] = 1、それ以外の場合、値は 0 になります。
無向グラフの場合、頂点 i または V の間にエッジが存在する場合_私頂点 j または V へ_j、次に A[V の値_私][で_j] = 1 および A[V_j][で_私] = 1、それ以外の場合、値は 0 になります。

隣接行列に関するいくつかの質問を見てみましょう。以下の質問は、重み付けされた無向グラフと有向グラフに関するものです。

注: 各エッジにエッジの重みと呼ばれる正の数値が割り当てられている場合、グラフは重み付きグラフであると言われます。

質問1 - 以下の無向重み付きグラフの隣接行列は何になるでしょうか?

解決 - 与えられた質問には自己ループがないため、上のグラフの隣接する行列の対角要素が 0 になることは明らかです。上のグラフは重み付き無向グラフです。グラフのエッジの重みは、隣接行列のエントリとして表されます。

上のグラフの隣接行列は次のようになります -

質問2 - 以下の有向重み付きグラフの隣接行列は何になるでしょうか?

解決 - 与えられた質問には自己ループがないため、上のグラフの隣接する行列の対角要素が 0 になることは明らかです。上のグラフは重み付き有向グラフです。グラフのエッジの重みは、隣接行列のエントリとして表されます。

上のグラフの隣接行列は次のようになります -

この記事が隣接マトリックスについて理解するのに役立つことを願っています。ここでは、隣接行列とその作成およびプロパティについて説明しました。また、重み付けの有無にかかわらず、有向グラフまたは無向グラフでの隣接行列の形成についても説明しました。

メソッドJavaに等しい

TechCodeview