グラフの種類¶

グラフの種類には大きく分けて四つある.

無向グラフ: エッジに方向がない

有向グラフ: エッジに方向がある

重み付き無向グラフ: エッジに重みがあり, 方向がない

重み付き有向グラフ: エッジに重みがあり, 方向がある

無向グラフの例¶

友達関係をグラフに下例.

この例ではエッジに方向がない. 例えば, [友達の友達は友達としたたき, A 君を B 君は友達なの?] や [いくつかの友達グループがある?] など問題が考えられる.

物事の手順をグラフにした例.

朝起きてから学校に行くまでの簡単な手順を示しているが, このグラフから様々な要素が読み取れる. 例えば, 朝起きてから朝食を食べなくても学校へ行けるが, 着替えなげれば学校に行けないことがわかる.

起きて -> 着替えて -> 学校へ行く, というのがこの手順の最短路となる.

各ノードが市町を表し, エッジが市町を行き来するのにかかる時間を表している (架空のもの) あるからある町への最短路を求めたいなどの類の問題はよくある.

ここで取り上げたものは, ほんの例でしかない. [全ての問題はグラフで表せる] と言われるほど, グラフ構造は様々な問題で応用される.