有向および無向グラフ

グラフとは

グラフは "ノード" と "エッジ" の集合であり、関係を表します。

ノードはオブジェクトに対応する頂点です。
エッジはオブジェクト間の結合です。
グラフエッジは重みをもつ場合があります。重みは、ノード間の各結合の強度 (または他の属性) を示します。

これらは一般的な定義であり、グラフ内のノードとエッジの正確な意味は具体的用途に応じて異なります。たとえば、グラフを使用してソーシャルネットワークでの友人関係をモデル化したとします。グラフノードは人々であり、エッジは友人関係を表します。グラフは物理的なオブジェクトや状況に自然に対応するため、グラフを使用してさまざまなシステムをモデル化できます。以下に例を示します。

Web ページのリンク — グラフノードは Web ページで、エッジはページ間のハイパーリンクを表します。
空港 — グラフノードは空港で、エッジは空港間のフライトを表します。

MATLAB^® では、関数 graph と関数 digraph を使用して有向グラフと無向グラフを表すオブジェクトを作成します。

無向グラフのエッジには方向性がありません。エッジは "双方向" の関係を示します。つまり、各エッジでは両方向に行き来できます。次の図は、3 つのノードと 3 つのエッジから成る簡単な無向グラフを示しています。
有向グラフのエッジには方向性があります。エッジは "一方向" の関係を示します。つまり、各エッジは一方向にのみ通行できます。次の図は、3 つのノードと 2 つのエッジから成る簡単な有向グラフを示しています。

通常、グラフ図内にあるエッジの正確な位置、長さ、向きに意味はありません。つまり、基本となる構造が変わらない限り、同じグラフでもノードの再配置やエッジの変形によって、いくつかの異なる表示が可能となります。

自己ループと多重グラフ

graph と digraph を使用して作成されるグラフには、1 つ以上の "自己ループ" (ノードをそのノード自体に結合するエッジ) を含めることができます。また、同じソースノードとターゲットノードをもつ複数のエッジをグラフに含めることもでき、そのようなグラフを "多重グラフ" と呼びます。多重グラフには、自己ループが含まれている場合もそうでない場合もあります。

MATLAB のグラフアルゴリズム関数においては、単一の自己ループをもつノードが含まれているグラフは多重グラフではありません。ただし、"複数の" 自己ループをもつノードが含まれているグラフは多重グラフです。

たとえば、以下の図は、自己ループをもつ無向多重グラフを示しています。ノード A は 3 つ、ノード C は 1 つの自己ループをもっています。このグラフには次の 3 つの条件があり、いずれか 1 つだけでも多重グラフになります。

ノード A に 3 つの自己ループがある。
ノード A と B の間に 5 つのエッジがある。
ノード A と C の間に 2 つのエッジがある。

Plot showing a multigraph. There are multiple edges connecting node A to node B, and node A also has several self-loops.

特定のグラフが多重グラフかどうかを判定するには、関数 ismultigraph を使用します。

グラフの作成

グラフの主な作成方法には、隣接行列の使用やエッジリストの使用があります。

隣接行列

グラフ内の情報を表現する方法の 1 つは、正方の "隣接行列" を使用することです。隣接行列内の非ゼロの要素は 2 つのノード間のエッジを示し、要素の値はエッジの重みを示します。隣接行列の対角要素は通常ゼロですが、非ゼロの対角要素は "自己ループ"、すなわちエッジによってそれ自体に結合されているノードを示します。

graph を使用して無向グラフを作成する場合、隣接行列は対称でなければなりません。実際には、繰り返しを避けるために行列はしばしば三角行列となります。隣接行列の上三角部分または下三角部分のみを使って無向グラフを作成するには、graph(A,'upper') または graph(A,'lower') を使用します。
digraph を使用して有向グラフを作成する場合、隣接行列が対称である必要はありません。
大規模なグラフの場合、隣接行列には多くのゼロが含まれ、通常はスパース行列となります。
隣接行列から多重グラフを作成することはできません。

たとえば、次の無向グラフについて考えてみます。

Plot showing an undirected graph with three nodes and three edges. The edge AB has a weight of 1, AC a weight of 2, and BC a weight of 3.

グラフは次の隣接行列で表現できます。

$(\begin{matrix} 0 & 1 & 2 \\ 1 & 0 & 3 \\ 2 & 3 & 0 \end{matrix}) .$

MATLAB でグラフを作成するには、次を入力します。

A = [0 1 2; 1 0 3; 2 3 0];
node_names = {'A','B','C'};
G = graph(A,node_names)

G = 

  graph with properties:

    Edges: [3×2 table]
    Nodes: [3×1 table]

関数 graph または関数 digraph を使用して、隣接行列からグラフを作成できます。あるいは、関数 adjacency を使用して、既存のグラフに対して重みありまたは重みなしのスパース隣接行列を求めることができます。

エッジリスト

グラフ内の情報を表現するもう 1 つの方法は、すべてのエッジをリストすることです。

たとえば、前記と同じ無向グラフについて考えてみます。

Plot showing an undirected graph with three nodes and three edges. The edge AB has a weight of 1, AC a weight of 2, and BC a weight of 3.

ここで、グラフをエッジリストで表現します

$\begin{array}{l} Edge Weight \\ \begin{matrix} \begin{matrix} (A, B) \\ (A, C) \end{matrix} & \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} 1 \end{matrix} \end{matrix} \end{matrix} \\ \begin{matrix} \begin{matrix} \begin{matrix} 2 \end{matrix} \end{matrix} \end{matrix} \end{matrix} \\ (B, C) & \begin{matrix} \begin{matrix} \begin{matrix} 3 \end{matrix} \end{matrix} \end{matrix} \end{matrix} \end{array}$

エッジリストから、グラフには 3 つの一意のノード、A、B、C があり、それらはリストされている 3 つのエッジによって結合されていることが簡単にわかります。グラフ内に連結されていないノードがある場合、それらはエッジリストに含まれないため、別途指定する必要があります。

MATLAB では、エッジのリストは列によって "ソース" ノードと "ターゲット" ノードに分けられます。有向グラフではエッジの方向 (ソースからターゲットへ) が重要ですが、無向グラフでは、ソースとターゲットのノードは相互交換可能です。エッジリストを使用してこのグラフを作成する 1 つの方法は、ソースノード、ターゲットノードおよびエッジの重みについて別々の入力を使用することです。

source_nodes = {'A','A','B'};
target_nodes = {'B','C','C'};
edge_weights = [1 2 3];
G = graph(source_nodes, target_nodes, edge_weights);

graph と digraph の両方で、エッジリストから単純グラフまたは多重グラフを作成できます。グラフ G の作成後、コマンド G.Edges を使ってエッジ (およびそのプロパティ) を確認できます。G.Edges のエッジの順序はソースノード (最初の列) によって、また 2 次的にはターゲットノード (2 番目の列) によって並べ替えられます。無向グラフの場合、インデックスが小さいほうのノードがソースノード、インデックスが大きいほうのノードがターゲットノードとしてリストされます。

graph と digraph の基本的な実装はスパース行列に基づいているため、多くの場合インデックス処理に同等の時間がかかります。空のグラフを作成してノードとエッジを何度も追加していくよりも、前述のメソッドの 1 つを使用して 3 要素のペア (source,target,weight) から一度にグラフを作成するほうが簡単です。最善のパフォーマンスを得るには、graph、digraph、addedge、addnode、rmedge、および rmnode の呼び出し数を最小限にします。

グラフノード ID

既定では、graph または digraph を使用して作成されるグラフ内のすべてのノードは番号付きとなります。したがって、数値の "ノードインデックス" によってノードをいつでも参照できます。

ノード名をもつグラフの場合 (つまり、G.Nodes に変数 Name が含まれる場合)、グラフ内のノードを、その名前を使用して参照することもできます。したがって、グラフ内の名前付きノードはそのノードインデックスまたはノード名のいずれかで参照できます。たとえば、ノード 1 は 'A' と呼ぶこともできます。

"ノード ID" という用語には、ノードの識別における両方の側面が含まれています。ノード ID はノードインデックスとノード名の両方を指します。

MATLAB は便宜上、大多数のグラフ関数を呼び出す際にどちらのタイプのノード ID が使用されているかを記憶しています。したがって、ノードインデックスでグラフ内のノードを参照する場合は、ほとんどのグラフ関数が、インデックスでノードを参照する数値の応答を返します。

A = [0 1 1 0; 1 0 1 0; 1 1 0 1; 0 0 1 0];
G = graph(A,{'a','b','c','d'});
p = shortestpath(G,1,4)

p =

     1     3     4

一方、名前でノードを参照する場合は、ほとんどのグラフ関数が、(文字ベクトルの cell 配列または string 配列に格納された) 名前でノードを参照する応答を返します。

p1 = shortestpath(G,'a','d')

p1 =

  1×3 cell array

    {'a'}    {'c'}    {'d'}

特定のノード名の数値によるノード ID を求めるには findnode を使用します。逆に、特定の数値のノード ID に対応するノード名を確認するには G.Nodes.Name にインデックスを付けます。

既存のグラフの変更またはクエリ

graph オブジェクトや digraph オブジェクトを作成した後、さまざまな関数を使用してグラフ構造を変更したり、グラフのノード数やエッジ数を判定したりできます。次の表に、graph オブジェクトや digraph オブジェクトの変更またはクエリに使用できる関数の一部を示します。

`addedge`	グラフに 1 つ以上のエッジを追加
`rmedge`	グラフから 1 つ以上のエッジを削除
`addnode`	グラフに 1 つ以上のノードを追加
`rmnode`	グラフから 1 つ以上のノードを削除
`findnode`	グラフ内の特定のノードを検出
`findedge`	グラフ内の特定のエッジを検出
`numnodes`	グラフ内のノード数を検出
`numedges`	グラフ内のエッジ数を検出
`edgecount`	指定したノード間のエッジ数
`flipedge`	有向グラフのエッジの方向を反転
`reordernodes`	グラフ内のノードの順序を並べ替え
`subgraph`	部分グラフの抽出

一般的なグラフ変更のいくつかの例は、既存グラフのノードとエッジの変更を参照してください。

参考

graph | digraph