『Pythonで体験してわかるアルゴリズムとデータ構造』メモその10/そのグラフは同型か？ 隣接行列は何か

『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。

Pythonで体験してわかるアルゴリズムとデータ構造

第10章データ構造はなぜ重要か

この章からアルゴリズムからデータ構造の話となる。

この章のゴールは

• データ構造はなぜ重要、例を挙げて説明できるようになる。

この章では探索と木構造について説明しているが、その前にさらっと書いてあるグラフ理論について記載する。

グラフについて

そもそもグラフとはどいうものを指すのか。

グラフ理論におけるグラフ （Graph）とは、頂点(node)と辺(edge)により構成された図形のことである。 グラフ理論 - Wikipedia

つまりこんな感じ。

グラフには大きく分けて以下2つに分類される 。

• 無向グラフ (辺が向きを持たないグラフ)
• 有向グラフ (辺が向きを持つグラフ)

無向グラフは辺が向きを持たないとあるので、矢印のないパターン。

有向グラフは矢印のあるパターン。

また頂点（絵の図だとA～E）の集合をV、辺の集合をEと仮定して、あるグラフをあらわす公式が という。

この公式の考え方で、この2つを考えたとき同じなのかという話だと。同じ。

頂点の数がA～Eの5つで、辺は曲がりくねってても頂点同士をつないでいれば1と考えるので、辺の数は5。

頂点の数と、辺がどこにつながっているかを公式に当てはめると、
G = ({A,B,C,D,E}, {A-B, A-C, B-D, C-E, D-E}) となる。

じゃあ以下も同じかというと、同じではない。

頂点の数がA～Eの5つで、辺の数も5で同じなのにどうしてということだけど、頂点を通っている辺が違う。

公式に当てはめると、
G = ({A,B,C,D,E}, {A-B, A-C, B-D, C-D, D-E})
となる。

Cから通っている先がEなのか、Dなのかが違っている。

その図形が同じ形であるというのは、頂点の数も、頂点から辺に行く数とどの頂点を通っているのかも同じでないといけない。
これをグラフの同型という。

応用情報でよく出てくるどれが同型かという問題はこの考え方を理解できていると突破できる。

隣接行列

上で説明したものを数字だけで表したものを隣接行列という。 wikipediaのほうが詳しく載っている。 隣接行列 - Wikipedia

上でできている無向グラフを隣接行列に置き換えると以下のようになる。

|A|B|C|D|E
A|0|1|1|0|0
B|1|0|0|1|0
C|1|0|0|0|1
D|0|1|0|0|1
E|0|0|1|1|0

単純につながっていれば1、つながってなければ0というように表しているだけ。

上の有向グラフを隣接行列に置き換えると以下のようになる。

| A| B| C| D| E
A| 0| 1| 1| 0| 0
B|-1| 0| 0| 1| 0
C|-1| 0| 0| 1| 1
D| 0|-1|-1| 0|-1
E| 0| 0|-1|-1| 0

無向グラフに矢印の向き先を考慮させて図になる。
始点である場合1、終点である場合-1で表している。

これをプログラミングして実行したときに記憶容量（メモリ）を使用するのかという評価として領域計算量を考える。

上記のようなグラフの場合、領域計算量は、つまり縦と横の大きさによるということになる。
そりゃそうだよなって話だけども。

参考

http://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad11/ad11-09.pdf

https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/GraphTheory-2007-Note-all.pdf