第 10 回 グラフの表現

本日の内容

• 10-1. グラフ
• 10-2. グラフの表現

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

10-1. グラフ

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

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

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

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

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

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

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

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

演習10-1

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

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

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

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

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

10-2. グラフの表現

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

文字列

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

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

行列

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

演習10-2

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

ポインタ

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

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

しかし、出次数に制限がなければ辺を表す頂点へのポインタを値として持つ線 形リストへのポインタになります。

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

演習10-3

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

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

ヒント

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

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

C++ を使う場合、容量の制限のない(二次元)配列は次のようすれば使えます。

#include <iostream>
#include <vector>

main(){
  int size;
  vector<int> vmatrix; //制限のない配列宣言
  cin >> size;
  vmatrix.resize(size*size); //配列の容量を調整
  for(int i=0; i<size; i++){
    for(int j=0; j<size; j++){
      cin >> vmatrix[i*size+j]; //一次元しか使えないので変換
    }
  }
  for(int i=0; i<size; i++){
    for(int j=0; j<size; j++){
      cout << vmatrix[i*size+j] << " ";
    }
    cout << endl;
  }
}