グラフ理論の基礎

グラフ理論の「グラフ」とは？？

一般的に「グラフ」と言われれば思い浮かぶのは「棒グラフ」とか「円グラフ」みたいなデータの整理に使うグラフだと思います。
が。ここでいうグラフというのは、つぎの２つの構成要素からなる「図形」です。

1)点(vertex)…その名の通り点。
2)辺(edge)…点と点を繋ぐ奴。

点と点は繋がっている前提みたいな書き方をしましたが、別に点がどこの点ともつながらずに自分の殻に閉じこもっていても構いません。
このような点の事を孤立点(isolated vertex)といい、孤立点があるようなグラフの事を非連結グラフ(disconnected graph)と言います。反義語は連結グラフ(connected graph)ですね。

また、ある点から生え出てる辺の数を次数(degree)と言います。下のグラフで考えてみましょう。

例えば(a)のグラフについて点Bの次数は3で

と表記します。ちなみに孤立点の次数は0です。

さて、ここでグラフという概念で重要な概念として「同形性」があります。
実は上の２つの(a)(b)というグラフは―"見た目"が全然違うにも関わらず―グラフ理論という体系の中では「ある種同じもの」として考えられるのです。

グラフの行列による表記

グラフは次の２つの行列にその情報を対応付けることができます。

1)隣接行列…ij成分に「点iと点jを結んでいる辺の数」を入れたもの。
2)接続行列…ij成分に「点iから辺jが生えているならば１、そうでないなら０」を入れたもの。

上にグラフの隣接行列を、接続行列をとすると（ただし、点A⇒点1、点B⇒点2と読む）

さて、これらの行列は(a)も(b)も全く同じであります。
つまり、点同士のつながり方も、点と辺の繋がり方も一緒であれば、それらは「位相的同形」であるといえるわけです。

隣接行列について、上では対角成分がすべて0になっていますが「点iから出て点iに入るような辺」っていうのも考えることができます。このような辺を自分に帰ってきているという意味でループと言います。
また対角行列について、すべて成分は1以下となっていますが、別に２つや３つの辺で点同士が繋がっていても構いません。このような辺を多重辺といいます。
これらの特殊な要素（多重辺およびループ）を含まないようなグラフの事を単純グラフ(simple graph)といいます。

グラフが平面であるとは？？

たとえ同形であっても、色々な書き方があるというのは上の例でみたとおりです。
ここで(a)のように辺同士が交差しているに対して、(b)のように辺同士のクロスがないグラフを平面グラフと言います。

今までは点と辺だけで考えてきたので、隣接行列や接続行列で完全にその特徴を記述できました。しかし、次のような概念もグラフ理論においては重要です。

• 面(face)・・・辺で分割された１つの領域

これは明らかに、上の例で言う(a)と(b)ではこの数に差があることが分かります。

さて。そこで、連結で且つ平面グラフであるようなグラフについてだけ、面の数f、点の数n、辺の数mについて次のような性質が成り立ちます。

このような関係式をオイラーの関係式と言います。

javascript plugin Error : このプラグインで利用できない命令または文字列が入っています。