fc2ブログ



グラフの種類

2006.04.19 18:09  グラフ

グラフの種類には大きく分けて4つあります。

名前 特徴
無向グラフ エッジに方向がない
有向グラフ エッジに方向がある
重みつき無向グラフ エッジに重みがあり、方向がない
重みつき有向グラフ エッジに重みがあり、方向がある


無向グラフの例

友達関係をグラフにした例です。この例ではエッジに方向をもたせていません。例えば、「友達の友達は友達としたとき、A君とB君は友達ですか?」や「いくつの友達グループがありますか?」などの問題が考えられます。

graphExample1.gif

有向グラフの例

物事の手順をグラフにした例です。朝起きてから学校に行くまでの簡単な手順を示していますが、このグラフから様々な要素が読み取れます。例えば、朝起きてから朝食を食べなくても学校へ行けますが、着替えなければ学校には行けないことが分かります。起きて→着替えて→学校へ行く、というのがこの手順の最短経路となります。

graphExample2.gif

重みつき無向グラフの例

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

graphExample3.gif


ここで取り上げたものは、ほんの例でしかありません。「すべての問題はグラフで表せる」と言われるほど、グラフ構造は様々な問題で応用されます。
スポンサーサイト



| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ