総合科目II(第2回) part II

part Iに引き続き、後半ではグラフ理論をやっていきます。

グラフ理論

いくつかの頂点と、それを結ぶ辺からなる図形をグラフといいます。

このような図形は、５つの頂点と５つの辺からなるグラフとなります。
平面上に書いたときに、辺同士が交わってもかまいません。
ただし、必ず辺は２つの頂点(同じでもよい)を結ぶものでないといけません。

グラフ理論を始めるにあたり、いくつかの定義があるので紹介します。

次数：頂点から出る辺の数。通常、頂点に従って変わる。
完全グラフ：任意の異なる頂点に対して、ただ一つのみ辺が定まっているもの。
特に、各頂点の次数は等しく $n-1$。ここで、$n$ は頂点の数。このとき、$K_n$ と書く。
正則グラフ：各頂点で次数が等しくなるグラフのこと。特に完全グラフは正則グラフになる。
二部グラフ：頂点の集合 $V$ が2つ集合 $A$ と $B$ からなっており(つまり、 $V=A\cup B$ のような２つの集合の和集合となっており、$A\cap B=\emptyset$ を満たし、辺は必ず、$A$ の頂点と $B$ の頂点を結ぶ。例として以下のグラフがある。

完全二部グラフ：$A$ と $B$ の頂点の個数をそれぞれ、$n,m$ とすると、$A$ の各点は辺によって、必ず、$B$ のすべての頂点とただ一つの辺にのみ結ばれるもの。$K_{n,m}$ と書く。
歩道：$v_1,v_2,\cdots, v_n$ をいくつかの頂点とし、$v_i$ と $v_{i+1}$ がある辺によって、結ばれているとき、この頂点と辺の和集合を歩道という。
多重辺：ある２つの頂点に対して、それらを結ぶ辺が２個以上あるとき、その辺のこと。
ループ：一つの頂点から出発して、同じ頂点に戻ってくる辺のこと。
サイクル：歩道のうち、最初と最後の頂点が一致しているもの。
内周：すべてのループのうち、最短のサイクルのこと。
同型なグラフ：２つのグラフ $G_1, G_2$ が同型であるとは、頂点の集合を $V_1,V_2$ とすると、$V_1$ と $V_2$ の間に一対一対応 $f$ (全単射)があり、$v,w\in V_1$ が結ばれていることと、$f(v),f(w)\in V_2$ が結ばれていることは同値であるものをいう。
平面グラフ：平面上に、辺の交わりなく描くことができるグラフ。

グラフ理論の公式
ここで、グラフ理論における簡単な公式を紹介しておきます。

正則グラフの公式
長点数 $n$, 次数 $d$ 辺の数 $m$ のグラフは

$nd=2m$

を満たす。完全グラフならば、$m=\frac{n(n-1)}{2}$ である。

オイラーの公式

$G$ を平面グラフとし、$G$ を平面に描いたときにできる図形

の頂点の数を $v$ 辺の数を $e$ 領域の数を $f$ としたとき、

$v-e+f=2$

が成り立つ。

例えば、

のような平面グラフであるとすると、頂点数が5で、辺の数が7で、領域の数が4

となります。

ここで、領域とは、このグラフの外部の部分も含めます。

このとき、

5-7+4=2

となり、確かに成り立っています。

プラトングラフとは、正多面体の頂点と辺の関係からなるグラフですが、

これは平面グラフです。

レポートにその理由をかけという問題を出しました。

多くの学生は、上のオイラーの公式を満たしているから平面グラフと書いていましたがそうではないです。

上の公式は、平面グラフであるならば、オイラーの公式を満たすといったのみです。

平面グラフであるための十分条件を与えたわけではありません。

そもそも平面グラフであるかどうかわからないのに領域の数はわかりません。

正しい答えは、以下のようになります。

正多面体を風船のように膨らませてやると、一般に、球上に描かれた頂点と辺からなる

プラントングラフが得られる。この風船の一点を取り除き、平面に

押し付けてやることで、プラトングラフを平面に描くことができる。

よってプラトングラフは平面グラフであることがわかる。

となります。

平面グラフかどうかは実際描いて見せないといけません。

また、最後の一点を取りのぞいて平面に押し付けるという操作は

立体射影と呼ばれておりここ(リンク)を見てみてください。

ここで、完全グラフ $K_5$ が平面グラフでないことを示したいと思います。

この証明ではオイラーの公式を用います。

定理

$K_5$ は平面グラフではない。

(証明)

もしグラフを平面に描いたとき、その領域の数を $f$ とすると、

$f=n_1+n_2+n_3+n_4+\cdots$

となります。ここで、$n_r$ は、グラフを平面に置いたとき分割されて得られる

平面上の $r$ 角形の数とします。

ここで、$r$ 角形とは、長さ $r$ のサイクルで、平面においてその内部に

頂点も辺も含まないものをいいます。

今、完全グラフ $K_5$ を描いたとします。

そうすると、多重辺やループは存在しないので、$n_1=n_2=0$ 

となります。よって、上の式は、

$f=n_3+n_4+\cdots$

となります。

また、各 $r$ 角形の辺の総数を数えると、辺の数の２倍になっているので

$3n_3+4n_4+5n_5+\cdots=2m$

が成り立ちます。ここで、

$3n_3+4n_4+5n_5+\cdots\ge 3(n_3+n_4+n_5\cdots)=3f$

という不等式を用いると、

$2m\ge 3f$

が得られます。しかし、

今、$K_5$ は、オイラーの公式から、$m=10$ かつ $f=7$ であるから、

矛盾します。

つまり、$K_5$ は平面的ではないということになります。

おなじように、$K_{3,3}$ が平面的ではないことを示す問題を出しました。

この場合、２部グラフであるので、もし平面に描けるとして

描いたとき、3角形も存在しません。

なので、$2m\ge 4f$ が成り立ちます。

今、$m=9$ であり、オイラーの公式から、$f=2-6+9=5$ ですから、これも

矛盾します。

ムーアグラフ

ムーアグラフは、去年の数学外書輪講で扱いましたので

そのページをリンク(ここ)しておきます。

定義をします。

定義

頂点数 $n$ 次数 $d$ 内周 $2g+1$ の正則グラフをムーアグラフという。

内周は必ず奇数をとります。

ムーアグラフは、

$n=1+\sum_{i=1}^gd(d-1)^i$   $(\ast)$ 

を満たします。

この式は、上のように、一つの頂点 $v$ から始めて、その点から延びる $d$ 個の

辺の先の頂点 $v_0,v_1\cdots v_{d-1}$ を考えます。

$g\ge 1$ であれば、この $d+1$ 個の頂点は

条件から同じものはありません。

$g=1$ の場合は、この頂点を結んで得られるグラフがムーアグラフになります。

頂点数は $1+d$ です。

$g\ge 2$ とすると、$v_i$ から辺がそれぞれ、$d-1$ 本延びており、その先の頂点を

$v_{ij}$ とすると、内周が5以上ですから、これらはすべて異なる頂点になります。

もちろん、$v_i$ や $v$ とも異なる頂点です。

$g=2$ のムーアグラフは、この $v_{ij}$ たちを適切に結んでできるグラフです。

頂点数は、$1+d+d(d-1)$ となります。

このようにして、ムーアグラフは辺を枝のように伸ばしていくことで得られます。

これを式にしたのが、$(\ast)$ ということになります。

$g=1$ の場合を見ると、$d=2, d=3,d=4$とすると、下のようになります。

同じように、$d=5$ 以上も増やしていくことが出来ます。

この絵で観察できるように、$d\le 3$ では辺どうしがぶつからない絵を描くこと

はできますが、$n=5$ になると、辺同士の頂点が生じています。

実際、$d\ge 4$ において、必ずこのような交点が生じてしまいます。

つまり、平面グラフであるのは、$d=2,3$  の時のみです。

これを証明せよという問題もレポートで出しました。

手法は上の方法と同じです。

次に、$g=2$ の場合を考えます。

頂点数は　$n=d^2+1$ となります。

このとき、次のことが知られています。

定理

内周が5、次数が $d$ のムーアグラフが存在するとすると、$d=2,3,7,57$ のみである。

この証明はMatousek(33-miniatures)の本に書いてありますが、

昨年の外書輪講のリンク(ここ)を張っておきます。

証明は線形代数を使います。

$d=2$ と $d=3$ の場合は、

のグラフが構成できます。

左は５角形ですが、右の方は、ピーターセングラフといいます。

$d=7$ のものを構成します。これは、ホフマンシングルトングラフといいます。

このグラフの構成がこの２回の講義の終着地点です。

まず、頂点 $v$ を一つ選び、7本の辺を伸ばします。

その先の頂点を $v_0,v_1,v_2,v_3,v_4,v_5,v_6$ とします。

さらに、$v_i$ からそれぞれ 6本ずつ辺を伸ばして、$v_{ij}$ を作ります。

ここで、$j=1,\cdots 6$ です。

このとき、$v_{0j}$を $v_{ij}$ と結びます。

左下の頂点を $v_{0i}$ とし、右下の頂点を $v_{ij}$ とします。

これは、内周が5より小さくならないようにに同じ頂点に行かないように

結んでいます。また、今のところ各 $i$ に対して 

$v_{ij}$ は $j$ に個性はありませんので、

素直に、順番通りに結んでいるだけです。

こうして、$v_{0i}$ についてはすべて結び終わりました

のこりは、$v_{1j}$ から $v_{6j}$ までの36個の頂点を結ぶことが出来れば

グラフが構成できます。

下の絵は、 $v_i$ と $v_j$ から６個の辺がそれぞれ伸びている様子です。

$v_{ik}$ を $v_{jm}$ のどれかと結びます。

もし、 $v_{ik}$ と $v_{il}$  がもし同じ $v_{jm}$ と結ぶとすると、

内周が４以下になってしまいます。

なので、$v_{ik}$ と $v_{il}$ は異なる　$v_{j1},\cdots v_{j6}$ のどれかに行かなければ

なりません。

つまり、どちらも同数ずつあるので、これは全単射です。

よって、この $v_i$ と $v_j$ を選ぶごとに、何か、$S_6$ の元を対応させることに

なります。

つまり、

$(i,j)\mapsto f((i,j))$ 

ですがこの写像こそ、前回最後にやった、外部自己同型です。

$n=6$ のときのみ、外部自己同型が使えたのです。

どうしてここで外部自己同型が出てきたのかという疑問が残ります。

いくつかうまくいっている部分を確かめる必要が

あるのですが、一つだけコメントしておきます。

この外部自己同型は、互換を互換の３つの積に写していました。

実は、$f(i,j)$ の先は、どうしてもすべての数字を動かさなければなりません。

どうしてかというと、$v_{ik}$ が $v_{jk}$ にグラフで結ばれたとすると、

実は、$v_{0k}$ は、$v_{ik}$ と $v_{jk}$ と既に結んでいましたから、

このとき、内周は３以下になってしまいます。

なので、$v_{i1},\cdots, v_{i6}$ と $v_{j1},\cdots v_{j6}$ を辺で結ぶ場合、

必ず、違う数字どうし結ぶ必要があります。

このように$S_6$ の外部自己同型を用いることで $n=50$, $d=7$, 内周5 の

グラフが作られました。

残すのは、$d=57$ の場合（$n=3250$,  内周5） のみですが、

$S_{56}$ には外部自己同型が存在しないから、

ムーアグラフも存在しないと結論づけるのは早計です。

外部自己同型ではない、別のアイデアでグラフが構成できるかもしれないからです。

というわけで、今のところ、内周 5, 次数 57, 頂点数 2350のグラフが存在するかどうかは未解決です。