[場所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 件のコメント:
コメントを投稿