[場所1E503（月曜日5限）]
HPに行く
現在外書輪講では、Matousekの33-Miniaturesをみんなで読んでいます。
今回は、Miniature 13, 14をやりました。
その前に、12で出されている下の主張を詳しく証明してもらいました。
Miniature 12
R を平面上の長方形とする。
その互いに垂直な2辺の長さを a,b とする。
{\mathbb R} を {\mathbb Q} 上のベクトル空間とする。
このとき、 f を線形写像 {\mathbb R}\to {\mathbb R} とする。
平面上の長方形から {\mathbb R} への写像 v を、
v(R)=f(a)f(b) として定義する。
R の1辺に平行な直線で R を二分したとき、できる長方形を R_1, R_2 とする。
このとき、f の線型性により、v(R)=v(R_1)+v(R_2) が成り立ちます。
一般に、R がいくつかの長方形 R_1,R_2,\cdots, R_n によって
タイリングされているとします。
タイリングとは、R_i と R_j に対して、i\neq j となるなら、
R_i\cap R_j は、R_i,R_j の境界のある線分に含まれることをいいます。
主張
このとき、v(R)=\sum_{i=1}^nv(R_i) となります。
これは、v(R)=v(R_1)+v(R_2) の性質だけを使って
証明をすることができます。
証明は授業中にした通りですので、ここでは省略します。
ヒントは、長方形の各辺と平行な直線を使って区切られた長方形の
網目 R=R_{11}\cup\cdots \cup R_{1n}\cup R_{21}\cup\cdots R_{m1}\cup\cdots \cup R_{mn}
によって R がタイリングされている場合について証明することです。
Miniature 13
をやりました。これはスペクトラルグラフ理論の話です。
グラフの隣接行列を使って、グラフの性質を引き出します。
グラフ G に対してその頂点を v_1,v_2,\cdots,v_n とするとき、
隣接行列 A=(a_{ij}) とは、
v_i,v_j が辺で結ばれているとき、a_{ij}=1
となり、そうでなければ、a_{ij}=0 である
として定義される行列です。
また、隣接行列は、自然に実対称行列であって、その主要な性質は、
以下となります。
ここでの話は、頂点数が 10 のグラフの話です。
前回(リンク) に基礎的な用語については書きました。
K_{10} は、頂点数が 10 の完全グラフです。
ペテルセングラフというのは、頂点数が10で、各辺からは、
3つの辺が存在する(次数が3という)正則グラフです。
また、内周は5です。証明してもらったのは、以下の定理です。
定理
K_{10} を頂点数 10 の完全グラフとします。
ペテルセングラフと同型な3つ部分グラフによって K_{10}
を覆うことができない。
覆うの意味については、前回の外書輪講のページを見てください。
このペテルセングラフの隣接行列は、A^2+A=J_{10}+2I_{10}
を満たすことがわかるのですが、その理由は次のMiniature 14を読むとわかります。
J_{10} はすべての成分が 1 のサイズが 10 の正方行列です。
注意したいのは、この関係式から、A の固有値がわかるということです。
\lambda を A の固有値とし、その固有ベクトルを {\bf v} とすると、
A が次数が3の正則グラフであることから、直ちに、\lambda=3 となることが
できて、その固有ベクトルは、{\bf 1}=(1,1,\cdots,1)^T となります。
また、この固有ベクトルと独立な固有ベクトルは、{\bf 1} に直交し、
{\bf 1}\cdot {\bf v}=0 となります。
とくに、J_{10}{\bf v}={\bf 0} となります。
そのような固有値は、(\lambda^2+\lambda ){\bf v}=2{\bf v} であり、{\bf v}\neq {\bf 0} であるので、\lambda^2+\lambda-2=0 が成り立ちます。
よって、固有値3の固有空間は1次元で、{\bf 1} がその基底となります。
それ以外の固有値は 1 か -2 となります。
固有値の重複度込みの和は、隣接行列のトレースと言われ、隣接行列の場合
いつもゼロです。
m_1,m_{-2} を 固有値 1,-2 のそれぞれの重複度とすると、
3 の重複度は 1 であるから、m_1-2m_{-2}+3=0 であり、
m_1+m_{-2}=9 がなりたち、この方程式から、m_1=5 と m_{-2}=4 がわかります。
というわけで、次の補題が証明されます。
補題
ペテルセングラフの隣接行列 A は、1 を固有値にもち、
その固有空間の次元は 5 であり、-3 を固有値にもたない。
また、完全グラフが3つの部分グラフで覆われる時、
J_{10}-I_{10}=A_P+A_Q+Q_R となるペテルセングラフと同型なグラフの隣接行列A_P,A_Q,A_R がでます。
ここで、J_{10}-I_{10} が K_{10} の隣接行列です。
A_P,A_Q,A_R の固有値 3 の固有空間は、 {\bf 1} から生成され、
そのほかの固有空間は、{\bf 1}と直交する９次元部分空間です。
A_P とA_Q の固有値 1 の固有空間は、5次元ずつあるので、
9次元の中で、それぞれの固有値1 の固有空間になっている
ゼロでないベクトル {\bf w} が存在することになります。
A_P{\bf w}={\bf w} かつ、A_Q{\bf w}={\bf w}
です。このベクトルを使って、
A_R{\bf w}=(J_{10}-I_{10}-A_P-A_Q){\bf w}=-{\bf w}-{\bf w}-{\bf w}=-3{\bf w}
となります。よって上に書いたことから矛盾となります。
Miniature 14
は、Miniature 13 からのつづきのグラフの話です。
内周が g=2k+1 最小次数(頂点に関して最小の次数)が r のグラフで、
頂点数が 1+r+r(r-1)+\cdots+r(r-1)^{k-1}=\frac{r(r-1)^k-2}{r-2} となるグラフを
Moore グラフといいます。
内周 2k+1 で、最小次数が r のグラフの頂点数は、\frac{r(r-1)^k-2}{r-2}
を下回ることはありません。
つまり、そのようなグラフの頂点はこの値以上となるのです。
それについては、マトウセク
また、この数がちょうど頂点数となるグラフが存在するかどうかは
難しい問題となります。
また、上からのboundを求めることもグラフ理論での興味深い問題の1つですが、
その決定も難しいです。
Miniature 13で出てくるペテルセングラフは、内周が 5 で、最小次数が3の
Mooreグラフとなります。これは、各次数が全て3となる正則グラフにもなっています。
現在外書輪講では、Matousekの33-Miniaturesをみんなで読んでいます。
今回は、Miniature 13, 14をやりました。
その前に、12で出されている下の主張を詳しく証明してもらいました。
Miniature 12
R を平面上の長方形とする。
その互いに垂直な2辺の長さを a,b とする。
{\mathbb R} を {\mathbb Q} 上のベクトル空間とする。
このとき、 f を線形写像 {\mathbb R}\to {\mathbb R} とする。
平面上の長方形から {\mathbb R} への写像 v を、
v(R)=f(a)f(b) として定義する。
R の1辺に平行な直線で R を二分したとき、できる長方形を R_1, R_2 とする。
このとき、f の線型性により、v(R)=v(R_1)+v(R_2) が成り立ちます。
一般に、R がいくつかの長方形 R_1,R_2,\cdots, R_n によって
タイリングされているとします。
タイリングとは、R_i と R_j に対して、i\neq j となるなら、
R_i\cap R_j は、R_i,R_j の境界のある線分に含まれることをいいます。
主張
このとき、v(R)=\sum_{i=1}^nv(R_i) となります。
これは、v(R)=v(R_1)+v(R_2) の性質だけを使って
証明をすることができます。
証明は授業中にした通りですので、ここでは省略します。
ヒントは、長方形の各辺と平行な直線を使って区切られた長方形の
網目 R=R_{11}\cup\cdots \cup R_{1n}\cup R_{21}\cup\cdots R_{m1}\cup\cdots \cup R_{mn}
によって R がタイリングされている場合について証明することです。
Miniature 13
をやりました。これはスペクトラルグラフ理論の話です。
グラフの隣接行列を使って、グラフの性質を引き出します。
グラフ G に対してその頂点を v_1,v_2,\cdots,v_n とするとき、
隣接行列 A=(a_{ij}) とは、
v_i,v_j が辺で結ばれているとき、a_{ij}=1
となり、そうでなければ、a_{ij}=0 である
として定義される行列です。
また、隣接行列は、自然に実対称行列であって、その主要な性質は、
以下となります。
- 固有値は全て実数
- 対角化可能
- 相異なる固有空間は互いに直交
- トレース(対角成分の和)はゼロ
ここでの話は、頂点数が 10 のグラフの話です。
前回(リンク) に基礎的な用語については書きました。
K_{10} は、頂点数が 10 の完全グラフです。
ペテルセングラフというのは、頂点数が10で、各辺からは、
3つの辺が存在する(次数が3という)正則グラフです。
また、内周は5です。証明してもらったのは、以下の定理です。
定理
K_{10} を頂点数 10 の完全グラフとします。
ペテルセングラフと同型な3つ部分グラフによって K_{10}
を覆うことができない。
覆うの意味については、前回の外書輪講のページを見てください。
このペテルセングラフの隣接行列は、A^2+A=J_{10}+2I_{10}
を満たすことがわかるのですが、その理由は次のMiniature 14を読むとわかります。
J_{10} はすべての成分が 1 のサイズが 10 の正方行列です。
注意したいのは、この関係式から、A の固有値がわかるということです。
\lambda を A の固有値とし、その固有ベクトルを {\bf v} とすると、
A が次数が3の正則グラフであることから、直ちに、\lambda=3 となることが
できて、その固有ベクトルは、{\bf 1}=(1,1,\cdots,1)^T となります。
また、この固有ベクトルと独立な固有ベクトルは、{\bf 1} に直交し、
{\bf 1}\cdot {\bf v}=0 となります。
とくに、J_{10}{\bf v}={\bf 0} となります。
そのような固有値は、(\lambda^2+\lambda ){\bf v}=2{\bf v} であり、{\bf v}\neq {\bf 0} であるので、\lambda^2+\lambda-2=0 が成り立ちます。
よって、固有値3の固有空間は1次元で、{\bf 1} がその基底となります。
それ以外の固有値は 1 か -2 となります。
固有値の重複度込みの和は、隣接行列のトレースと言われ、隣接行列の場合
いつもゼロです。
m_1,m_{-2} を 固有値 1,-2 のそれぞれの重複度とすると、
3 の重複度は 1 であるから、m_1-2m_{-2}+3=0 であり、
m_1+m_{-2}=9 がなりたち、この方程式から、m_1=5 と m_{-2}=4 がわかります。
というわけで、次の補題が証明されます。
補題
ペテルセングラフの隣接行列 A は、1 を固有値にもち、
その固有空間の次元は 5 であり、-3 を固有値にもたない。
また、完全グラフが3つの部分グラフで覆われる時、
J_{10}-I_{10}=A_P+A_Q+Q_R となるペテルセングラフと同型なグラフの隣接行列A_P,A_Q,A_R がでます。
ここで、J_{10}-I_{10} が K_{10} の隣接行列です。
A_P,A_Q,A_R の固有値 3 の固有空間は、 {\bf 1} から生成され、
そのほかの固有空間は、{\bf 1}と直交する９次元部分空間です。
A_P とA_Q の固有値 1 の固有空間は、5次元ずつあるので、
9次元の中で、それぞれの固有値1 の固有空間になっている
ゼロでないベクトル {\bf w} が存在することになります。
A_P{\bf w}={\bf w} かつ、A_Q{\bf w}={\bf w}
です。このベクトルを使って、
A_R{\bf w}=(J_{10}-I_{10}-A_P-A_Q){\bf w}=-{\bf w}-{\bf w}-{\bf w}=-3{\bf w}
となります。よって上に書いたことから矛盾となります。
Miniature 14
は、Miniature 13 からのつづきのグラフの話です。
内周が g=2k+1 最小次数(頂点に関して最小の次数)が r のグラフで、
頂点数が 1+r+r(r-1)+\cdots+r(r-1)^{k-1}=\frac{r(r-1)^k-2}{r-2} となるグラフを
Moore グラフといいます。
内周 2k+1 で、最小次数が r のグラフの頂点数は、\frac{r(r-1)^k-2}{r-2}
を下回ることはありません。
つまり、そのようなグラフの頂点はこの値以上となるのです。
それについては、マトウセク
また、この数がちょうど頂点数となるグラフが存在するかどうかは
難しい問題となります。
また、上からのboundを求めることもグラフ理論での興味深い問題の1つですが、
その決定も難しいです。
Miniature 13で出てくるペテルセングラフは、内周が 5 で、最小次数が3の
Mooreグラフとなります。これは、各次数が全て3となる正則グラフにもなっています。
0 件のコメント:
コメントを投稿