第 9 回グラフの表現

本日の内容

9-1. グラフ
9-2. グラフの表現

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

9-1. グラフ

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

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

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

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

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

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

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

根付有向木で接続している二つの頂点に対して、辺が出る頂点を親、辺が入る頂点を子と言います。出次数が 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 にします。

	a	b	c
a	0	0	1
b	1	0	1
c	0	1	0
d	0	0	1

演習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 個であることです。

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

ヒント

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

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

発展問題

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

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

坂本直志 <[email protected]>
東京電機大学工学部情報通信工学科

第 9 回 グラフの表現