基礎理論~グラフ理論~
こんにちは。Twitterでは鬱真っ最中のこなちゃんです。
テーマ
これは、実際にPythonを使用して解説をしたQiitaのサイトもありますが、プログラミング寄りの記事で、FE,APにおける趣旨とは異なってしまうため、プログラムでどう書く?っていう話はしません。
グラフ理論とは
「グラフ」と聞いて、通常は棒グラフや円グラフ、折れ線グラフを想像しますよね。
ですが、情報学で言うグラフ理論の グラフ は別名 ネットワーク とも称され、「点と点を結んだ線」の集合を分析するものになります。
グラフ理論の例
例えば、日本地図の各県庁所在地に点を置き、隣県の点を結びます。
するともちろん、47の点と、隣り合う都道府県への辺が現れます。
それを見て、
「おっ、長野県が一番隣県多いじゃん」
と分析できます。
このように「点と辺の集まりから分析するもの」がグラフ理論です。
以下、グラフというのは「点と辺の集まり」だということを前提に進めていきます。
グラフの種類
無向グラフ
これが一般的なグラフです。
先程の都道府県の例の見たまんま、辺に「向き」なんて存在しないです。
敢えて、「無向グラフ」というからには対になるものがあります。次。
有向グラフ
一般的なグラフ(無向グラフ)と異なり、「方向」が付与されたものです。
?向き??
そうです、向きです。
先程の都道府県庁を結んだグラフに於いて「さて、日本一周しよう!」としたときに、
出発はここで、次はここで、と番号を振ったり、矢印を引いたりしますね。
この矢印が辺の「向き」です。
つまり、各点や辺に順番のような無向グラフ+αの意味が付与されたものでした。
途中だよ
元気ないしこれから仕事なので一旦休憩。
また書きます。