グラフ王におれはなる！とん！

グラフ（graph）とは、頂点（vertex）と辺（edge）からなる。例えば、こんなものだ。

これは頂点数（order）が５個で任意の頂点間に辺を引いている。このようなグラフを５の完全グラフ（complete graph）といい、K₅と表記する。一般にK_nを定義することは容易だろう。具体的にK₃とK₄を演習としてノートに書いてみよう！

頂点のことをノード（node）とも呼ぶ。ノードはネットワークの用語で頂点は幾何の用語だ。頂点に名前をつけてもいい。この名前をその頂点のラベル（label）という。

頂点から出る辺の数をその頂点の次数（degree）という。上の例では頂点４の次数は３で頂点１の次数は２だ。では、頂点５の次数は？また各点の次数うち最大のものをそのグラフの次数という。K_nの次数は？各点の次数を足し上げていくと、辺の数を２回ずつ重複して数えることになる。

ある頂点から別の頂点まで隣接する頂点を経由して何回の移動（ホップ、hop）で行けるか、というのを考えてみよう。上のグラフの例だと、頂点６から頂点１までは３回の移動で行くことができる。６ー４ー５ー１という経路がある。一方で６−４−３−２−１という経路も考えられる。この場合は４回の移動が必要だ。ここで移動に要する最小の回数をその２点の距離（distance）あるいはホップ数（hop count）という。つまり頂点６から頂点１の距離は３である、と。では、頂点５と頂点３の距離はどうなるだろうか？あるいは頂点１と２の距離は？ 任意の２点間の距離の内、最大のものをそのグラフの直径（diameter）という。上のグラフの直径は３である。具体的に手を動かして確かめてみてほしい。また完全グラフK_nの直径はどうなるだろうか？

グラフに含まれる最小のループの長さを、そのグラフのガース（内周、girth）という。完全グラフK_nのガースは３である。

ピーターセングラフ（Petersen Graph）と呼ばれる美しいグラフを紹介しよう。

これは頂点数10、各点の次数が３、直径２、ガース５のグラフである。直径とガースを確かめるのは演習とする。