wikipediaから引用
グラフ理論（グラフりろん、英: graph theory）は、ノード（節点[英 1]・頂点[英 2]）の集合とエッジ（枝・辺[英 3]）の集合で構成されるグラフ[英 4]に関する数学の理論である。グラフ (データ構造) などの応用がある。
下図のまる数字がノード、直線がエッジです。
グラフの考えを用いることで様々なものの関連性を表すことができます。例えば、以前紹介したRegexperの正規表現の表現です。
これは分岐、ループ、グループ、特殊文字、複数候補、のようなものを区切りにノードを作っています。ソースコードもif、for、while、関数などを目印にノードとすることでグラフによって表すことができます。ソースコードからできあがったグラフの複雑さを目安にコードレビューを行うこともできます。また、データ構造でもグラフ理論は使われており、特に階層的なデータ構造は木構造として知られています。ファイルシステム、HTMLなどはよく見るところにある木構造のデータ構造を持つシステムです。データ構造から想像できる木が非常に複雑であったり、歪であったりすると大体可読性がまずいことになっています。
通信ネットワーク、交通網の様な複雑にならざるをえないものもグラフ構造ならば秩序だって考えることができます。複雑すぎるものは隣接行列を用いて考えたりします。下が最初のグラフを表す隣接行列です。
0ならば隣接しておらず、1ならば隣接していることを示します。この行列は隣接行列と名がついていますがノード間の接続を表す行列と考えた方が思い浮かべやすいです。というのも(1,2)=1,(2,1)=0のようにすると一方通行を表すことができ、01のみならず任意の値で多重路や距離の様な重みを設定することもできるからです。隣接行列の操作によってグラフの様々な情報を得ることができます。例えば、01で表されたn乗された隣接行列の(i,j)成分はiからjへの長さnの経路の数になります。
