グラフとは有効グラフ無効グラフとは

グラフ(graph)は節点(node)を辺(edge)で結んだものです。

グラフの図を例に挙げます。

このグラフでは、節点を辺で結んでいますが、
辺で結ばれた間は行き来する道があることを示しています。

隣接行列

先のようなグラフをデータとして表現するたの手法として、
隣接行列(adjacency matrix)があります。

先のグラフを隣接行列で表してみます。

	1	2	3	4	5	6	7	8
1	0	1	1	0	0	0	0	0
2	1	0	0	1	0	0	0	0
3	0	1	0	0	0	0	1	0
4	0	1	0	0	1	0	0	0
5	0	0	0	1	0	1	0	0
6	0	0	0	0	1	0	1	1
7	0	0	1	0	0	1	0	1
8	0	0	0	0	0	1	1	0

節点から節点へ辺がある場合には1でない場合は0で
表現しています。

無効グラフ

辺に向きのないものを無効グラフと言います。
先で示したグラフは無効グラフになります。

有効グラフ

辺に向きをもたせたものを有効グラフと言います。
有効グラフの辺には矢印をもたせます。

有向グラフでは、矢印が向いている方向に対してのみ道があります。

例をあげると、
先のグラフ図で、1 → 2と向いている場合
隣接行列で表現すると、

1 → 2は1になるが
2 → 1は0になります。