第 9 回 グラフの表現

本日の内容


このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

9-1. グラフ

プログラムで扱うデータ構造としてグラフを取り上げます。 グラフとは頂点とそれを結ぶからなるものです。

グラフの例

頂点は vertex、 節、 node などの呼び方があります、辺は edge、枝、 branch とも言います。 辺に向きがないグラフを無向グラフ、 辺に向きがあるグラフを有向グラフと言います。

有向グラフ

互いに接続している頂点の列を道(path)と言います。 無向グラフにおいて、全ての頂点の組合せについて道がある場合、そのグラフ は連結であると言います。

頂点に接続している辺の数をその頂点の次数degreearityと言います。 有向グラフにおいては出る辺の数を出次数out degree、入る辺の数を入次数in degreeと言 います。

グラフには様々な形があり、それについて名前が付けられています。 無向グラフにおいて、木とは、ループのない連結グラフのことを言います。 次数が 1 の頂点をleafと言います。

根付有向木とは、次の条件を満たす有向グラフのことです。

  1. 根と呼ばれる頂点が一つだけ存在し、有向辺は入りません。
  2. 他の頂点は必ず一本の有向辺が入ります。
  3. 全ての頂点に、根からただ一つの道が存在します。

根付有向木で接続している二つの頂点に対して、辺が出る頂点を、辺が入る頂点をと言います。 出次数が 0 (入次数が 1)の頂点をと言います。 根付有向木において、出る辺の数が高々 2 本の木を二分木二進木binary tree と言います。

二分木

演習9-1

頂点が 4 つの二分木は何種類あるか? 実際に作図して求めなさい。


ここでさらに左側の枝には必ず葉が接続する二分木を考えると次のような構造になり ます。 これを線形リストと呼びます。

線形リスト

すべての頂点の次数が 2 の連結グラフは リング になります。

また、すべての頂点間に辺がある無向グラフを完全グラフと言い ます。

頂点が二つのグループに分割でき、同じグループ同士には辺がないグラフを 二部グラフと言います。 特に、異なるグループのすべての頂点の組み合わせに辺がある無向二部グラフ を完全二部グラフと言います。

9-2. グラフの表現

コンピュータで情報処理をする際、情報をグラフの形で抽象化して処理するこ とがしばしばあります。 そこで、コンピュータでグラフを表現するしかたを考えます。

文字列

プログラムへの入出力のために、単純に文字列としてのやりとりを考えます。 まず、グラフの頂点にはすべて名前が付けられているとします。頂点の名前の 集合を V とします。 すると、辺は二つの頂点の組み合わせで表せます。 辺の集合を E とすると、 E には (a,b) など、頂点の名前のペアが含まれる ことになります。 なお、有向グラフでは辺は (出発点,終着点) で表すことにします。

グラフは頂点と辺からなりますので、頂点の集合の要素と辺の集合の要素をそ れぞれ列挙すればグラフを表現できることになります。 下のグラフを要素の列挙で表現すると次のようになります。

有向グラフ
V = { a , b , c , d }, E = {(a, c), (b, a), (b, c), (c, b), (d, c)}

行列

頂点の数が n 個の時、n × n の正方行列を考えます。 もし、 i 番目の頂点から j 番目の頂点へ辺がある場合 (i,j) 成分を 1 に、 なければ (i,j) 成分を 0 にしたものはグラフの構造を表すことができます。 このような行列を 隣接行列 と言います。 なお、無向グラフで i と j に辺がある場合、 (i,j) 成分と (j,i) 成分をと もに 1 にします。

有向グラフ
abcd
a0010
b1010
c0100
d0010

演習9-2

次のグラフの隣接行列を求めなさい。

グラフの例

この隣接行列を使ったサンプルプログラムを示します。 これは隣接行列から文字列の表現に変換するプログラムです。


#include <stdio.h>
#define MAX 10
int main(void){
  int n;
  int i,j,degree,kiten;
  int a[MAX][MAX];
  int comma;
  printf("頂点数を入れて下さい。\n");
  scanf_s("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      scanf_s("%d",&a[i][j]);
    }
  }
  printf("V={");
  comma=0;
  for(i=0;i<n;i++){
    if(comma){printf(",");}
    printf("%c",'a'+i);
    comma=1;
  }
  printf("},E={");
  comma=0;
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      if(a[i][j]){
	if(comma){printf(",");}
	printf("(%c,%c)",'a'+i,'a'+j);
	comma=1;
      }
    }
  }
  printf("}\n");
  return 0;
}

ポインタ

頂点を構造体とし、辺をポインタで表す方法でもグラフを表現できます。 構造体の中には、頂点の名前と、接続する頂点へのポインタの列を含めます。 もし、各頂点の出次数が制限されていれば構造体の中はポインタの配列になり ます。例えば出次数が 2 であれば次のような定義になります。


struct vertex {
  char *name;
  struct vertex *edge[2];
};

しかし、出次数に制限がない場合、線形リストを利用します。線形リストは次 回説明します。


struct edgelist {
  struct vertex * edge;
  struct edgelist *next;
};
struct vertex {
  char *name;
  struct edgelist *edges;
};

演習9-3

一筆書きができるグラフ(オイラーグラフ)である必要十分条件は、奇数の 次数を持つ頂点が 0 個か 2 個であることです。

  1. グラフの入力の仕様を考え、一筆書きができるかどうかを判定するプログラムを作りなさい。
  2. 次の図形が一筆書き可能かどうかを作成したプログラムで判定しなさい。
    1. 図1
    2. 図2
    3. 図3
  3. 一筆書きの必要十分条件を証明しなさい。

ヒント

隣接行列で入力するのが楽でしょう。 最初に行列のサイズを入れ、そのあと、隣接行列を入力するようにします。

C 言語では配列を使うのにあらかじめサイズを決めなければならないので、例 えば最大頂点数を 10 とか決めうちしても構いません。

発展問題

あたえられたグラフが連結グラフであるかどうか判定するプログラムを作りな さい。

隣接行列に対して and/or による行列の積を取ると、 k 乗が k 歩で行ける頂 点を表します。


坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科