グラフ理論

ぐらふりろん

点と線の物語。

概要

グラフを扱う理論であるが、ここで言うグラフは棒グラフや円グラフなどのグラフとは全く別物で、点と線で構成される概念である。

点が幾つあって、どの点とどの点が結ばれているか、という情報で構成される、図形と言うよりもっと抽象的なものであり、三角関係に似ている。例えば、キャラクターなどの相関図にする前の相関関係のようなものである。

ここでの点は節点や頂点やノードと呼ばれ、線は枝や辺やエッジと呼ばれる。

この線は、直線でも曲線でも折れ線でも、長くても短くても同じ線と見なされ、交差してても構わない。多角形のような角度も無い。つまりは「繋がっている」という事だけが問題となっており、この辺電気回路やトポロジーとも密接である。点も位置を問題としない。

線に方向が定義されている場合もあり、これを有向グラフ、そうでないものを無向グラフと言う。

主な種別

平面グラフ

スタンプ「生命宇宙万物の答え 42」by黒目白男

平面上で交差無しで表現できるグラフを平面グラフと言い、実際にそのように表現する事を埋め込み（Embedding）と言う。

平面グラフは多面体と密接で、多面体に双対多面体があるように、平面グラフには双対グラフが存在している。

平面グラフで無いものを非平面グラフと言う。

平面的グラフと呼ばれる事もあり、対して平面グラフを「埋め込まれた平面的グラフ」の意味とする事もある。同様に、非平面グラフも非平面的グラフと呼ばれる事がある。

完全グラフ

ネットワークby津由

全ての点同士が結ばれたグラフは完全グラフと呼ばれる。絵としては大抵、正多角形にその全ての星型多角形を頂点を共有する形で重ねたような図で表現される（その図形自体はなんて呼ぶのか不明）。

点が5つの場合の完全グラフは非平面グラフであり、極小な非平面グラフの一つである。

もう一つの極小な非平面グラフは3対3の完全2部グラフである（2部グラフというのは異性愛のみで構成される世界のようなものであり、完全2部グラフは全員が全ての異性と付き合ってるような状態である）。

ツリー

枝分かれ風船byyum

グラフ内の任意の点同士をただ一つの道筋（寄り道を除く）で行き来できる無向グラフをツリー或いは木と呼ぶ。これは「連結かつ閉路を持たない」とも表現される。対して閉路を持つものはリゾーム（根茎）と呼ばれる事がある。

植物の木は通常、特定の点が根元であり、そこから幹が生えて枝へと分かれて行き、各種系統樹やコンピュータのディレクトリ構造もそのようになっているが、グラフとしてのツリーはどの点を根元と見なす事もできる。

対して、どれか一つの点を根と決めた「根付き木」というものもある。

図以外での表現法

隣接行列

グラフは図ではなく行列で表現される事もある。

これは例えば、リーグ戦（総当たり戦）の表や、ポケモンなどの属性の相性の表の○や×を数値に置き換えたものである。

これを隣接行列と言う。

無向グラフの場合の隣接行列は対称行列で表現される。

有向グラフの場合、「1番目の点→2番目の点」という繋がりのみが存在している場合なら次のように表現されている。

0	1
0	0

隣接リスト

点を列挙し、それぞれがどの点と繋がってるかという情報で表現する。

辺リスト

線を列挙し、それぞれがどの点と繋がってるかという情報で表現する。エッジリストとも呼ばれ、これは英語名のカタカナでもある。

関連タグ

グラフ　電気回路　トポロジー　多面体

データ　構造　ネットワーク　図形　幾何学　数学

関連外部リンク

グラフ理論 - Wikipedia