こなさんち

しがないフリーランスエンジニアの備忘録。

基礎理論~グラフ理論~

こんにちは。Twitterでは鬱真っ最中のこなちゃんです。

テーマ

グラフ理論

これは、実際にPythonを使用して解説をしたQiitaのサイトもありますが、プログラミング寄りの記事で、FE,APにおける趣旨とは異なってしまうため、プログラムでどう書く?っていう話はしません。

グラフ理論とは

「グラフ」と聞いて、通常は棒グラフや円グラフ、折れ線グラフを想像しますよね。

ですが、情報学で言うグラフ理論 グラフ は別名 ネットワーク とも称され、「点と点を結んだ線」の集合を分析するものになります。

グラフ理論の例

例えば、日本地図の各県庁所在地に点を置き、隣県の点を結びます。

するともちろん、47の点と、隣り合う都道府県への辺が現れます。

それを見て、

「おっ、長野県が一番隣県多いじゃん」

と分析できます。

このように「点と辺の集まりから分析するもの」がグラフ理論です。

以下、グラフというのは「点と辺の集まり」だということを前提に進めていきます。

グラフの種類

無向グラフ

これが一般的なグラフです。

先程の都道府県の例の見たまんま、辺に「向き」なんて存在しないです。

敢えて、「無向グラフ」というからには対になるものがあります。次。

有向グラフ

一般的なグラフ(無向グラフ)と異なり、「方向」が付与されたものです。

?向き??

そうです、向きです。

先程の都道府県庁を結んだグラフに於いて「さて、日本一周しよう!」としたときに、

出発はここで、次はここで、と番号を振ったり、矢印を引いたりしますね。

この矢印が辺の「向き」です。

つまり、各点や辺に順番のような無向グラフ+αの意味が付与されたものでした。

途中だよ

元気ないしこれから仕事なので一旦休憩。

また書きます。