まず最初に言葉の定義ですが、頭の中に絵を描いてください。
正方形の上に三角が載った家の形です。正方形の対角線を結んでバッテン(×)を描いてください。
この絵で点が5個あります。ちゃんと数えてくださいね。
辺の数はまんなかのバッテンを入れて8本です。
それから、グラフ理論で大事なのが点から出ている辺の数です。
2本の辺が出ている点が1つ、3本の辺が出ている点が2つ、4本の辺が出ている点が2つ。
辺の数は8本で、その端の数は倍ですので16個。
確認してみましょう。
2*1 + 3*2 + 4*2 = 2 + 6 + 8 = 16
用語ですが、グラフ理論では点をvertexと言います。
辺はedgeと呼び、点から出ている辺の数はdegreeと呼びます。
点をP、Q、R、S、Tとして、deg(P)=3、deg(Q)=4というような表記をします。
そして、いま頭の中に描いた家の形の図形をグラフと呼びます。
1.P、Qを結ぶ辺が2本以上ある場合、多重辺(multiple edges)と呼ぶ
2.PからPに戻る辺はループ(loop)と呼ぶ
3.多重辺もループもないグラフを単純グラフと呼ぶ
4.辺に向きがある場合、有向グラフ(directed graph、digraph)という
5.歩道(walk)とは連結した辺のこと
6.道(path)とはどの点も一度しか現れない歩道
7.閉路(cycle)とはQ->S->T->Qのような道
8.連結グラフ(connected graph)とはどの2つの点も道で結ばれている
9.非連結グラフ(disconnected graph)とは連結グラフでないグラフ
10.オイラー・グラフとは、すべての辺をちょうど1回ずつ通って出発点に戻る歩道を含むグラフのこと。
12.ハミルトン・グラフとは、すべての点をちょうど1回ずつ通って出発点に戻る歩道を含むグラフのこと。
13.木(tree)とは、どの2点の間にも道が1つしかない連結グラフ
