コンピューターサイエンスでも扱われるグラフ理論がどんなものなのかと、それの基礎的な知識を解説することが目的です。
少し特殊な数学なのでなれるまで少し時間がかかるかもです。
グラフと聞くとy=f(x)のグラフなどを思い浮かべるかもしれませんが、ここで紹介するグラフは”いくつかの点と、２つの点を繋ぐ線からなるもの”をいいます。
超ざっくりしたいいことをすれば、物同士の繋がり方を表した物で、グラフ理論は物同士がどのように繋がっているかを重要視します。
超基礎知識
グラフに使われている点のことを頂点(Node)といい、２つの点を繋ぐ線のことを辺(edge)と呼びます。
繋がり方に方向があるグラフを有向グラフ、方向がないグラフを無向グラフといいます。
空港と飛行機を例に考えてみます
リアルタイムでの飛行機と飛び立った空港と目的地に着目して図を考えてみてください。羽田から関空に行く飛行機の場合の向きは羽田→関空になります。それに対して、空港だけをつないでそこに直行便の有無をグラフにまとめる場合は両方の空港を行き来する便があることが前提になるので向きの情報が不必要になり無向グラフでことが足りるようになります。
少し理解を深めよう
ここでグラフに関して少し理解を深めてもらいたいなと思います。
上と下の有効グラフものは同じものでしょうか？
上のグラフの構成要素は
頂点={1,2,3,4,5}
辺={0→1,1→2,2→3,3→4,4→5,5→1,4→2}
です。
結論からいうと二つとも同じグラフです。なぜならグラフ理論は頂点同士がどのように繋がっているかを問題にしている学問で、２つの頂点が繋がっているかいないかのみが重要になります。すなわち繋がり方が同じであれば描写の違いは問題ではないのです。
ちなみに、上２つの図はプログラミングを使って書いているのですが、構成要素の記述のコードを書く順番を少し変えたらこの違いになりました。
繋がりの表し方
繋がり方の表し方は僕の自作で分かりやすくしたもので、もう少し数学的になおかつコンピューターにも理解してもらえる行列を使った表現の方法を説明したいと思います。
行列を習ったことがない人でも全然理解できます。
頂点同士の繋がりにフォーカス＝隣接行列
どの頂点からどの辺が伸びているか＝接続行列
この２つの行列は有向グラフか無向グラフかでも行列の中身も変わってきます。
下に自分が見つけた外部のリソースがあるので参考にしてみてください。
http://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad11/ad11-09.pdf
もう少しコンピューターサイエンスチックな話として、接続リストがあります。
接続リストは、頂点からどの辺を移動することができるかをまとめたものです。
プログラミング的にはリストで集めてもいいですし、連結リストで実装してみてもいいと思います。
上のスライドは少し連結リストチックでした。
連結リストを詳しく知りたい方はこちらへどうぞ。
重り付きのグラフ
次に重り付きグラフを紹介したいと思います。
辺の中に入っている数字が重りの数です。重りは英語でweightといいます。
上のグラフまででは２つの頂点が繋がっているか、矢印はありか無しかをみてきましたが、重り付きグラフはどの程度の関係性があるのかを表します。
例えば飛路であれば空港と空港間の距離かもしれませんし、空港と空港間の移動にかかる値段かもしれません。
グラフは何を目的にするからで頂点と辺、重りは変わってきます。
他のグラフ理論の記事
Gale Shapleyのアルゴリズムという、一対一のマッチングに使われる手法です。グラフ理論でマッチングというと意外な気がしますが、実はマッチングはグラフ理論でよく出てくるトピックの１つです。
Spanning treeと呼ばれるグラフの全ての頂点をできる限り辺を少なくして網羅するグラフの書き方のアルゴリズムを解説した記事です。
