道グラフ(path graph)とは、$n\ge1$ に対し頂点 $1,\dots,n$ を一列に並べ、$i$ と $i+1$ だけを辺で結んだグラフ $P_n$、およびそれと同型なグラフのことである。$n\ge2$ の有限グラフとしては、次数が $2$ 以下の木であること、葉がちょうど $2$ 個の木であること、連結で直径が $n-1$ であることで特徴づけられる。隣接行列の固有値は $2\cos(k\pi/(n+1))$($k=1,\dots,n$)で、$2I$ から隣接行列を引いた行列は $A_n$ 型の Cartan 行列である。グラフの中の経路である道とは区別する。
$n$ 個の点を一列に並べ、隣どうしだけを線で結んだグラフが道グラフ $P_n$ である。形は単純だが、木の中で最も細長いものであり、固有値が三角関数で書け、区間の上の 2 階微分の離散版でもある。A 型の Dynkin図形もこのグラフである。
道グラフは、グラフの用語の「道」とは別の言葉である。
| 言葉 | 何のことか | 条件 |
|---|---|---|
| 歩道 | グラフ $G$ の中の頂点の列 | 隣り合う頂点が辺で結ばれている |
| 小道 | $G$ の中の歩道 | 辺が相異なる |
| 道 | $G$ の中の歩道 | 頂点が相異なる |
| 道グラフ | グラフそのもの | 全体が一列につながっている |
$G$ の長さ $\ell$ の道(道(グラフ))の定める部分グラフは、$\ell+1$ 頂点の道グラフ $P_{\ell+1}$ と同型である(道(グラフ) の記事の定義「部分グラフとしての道」)。つまり、道は $G$ の中に現れる場所であり、道グラフはその形の名前である。
この記事では、道グラフの基本的な量をまとめ、次数・木・直径による特徴づけ(thm-pg-char)を証明し、固有値(thm-pg-spectrum)を求め、Laplacian行列と Cartan 行列との関係を述べる。
$n\ge1$ とする。頂点の集合を $\{1,2,\dots,n\}$ とし、辺を $\{i,i+1\}$($1\le i\le n-1$)とするグラフを道グラフ(path graph)といい、$P_n$ と書く。これと同型なグラフも道グラフという。頂点 $1,n$ を $P_n$ の端点、ほかの頂点を内点という。
$P_1$ は頂点 1 個で辺のないグラフ、$P_2$ は $K_2$ である。$n\ge2$ のとき、$P_n$ の端点は次数 $1$ の頂点、すなわち葉である。
添字の読み方には注意が要る。この記事の $P_n$ の $n$ は頂点の数で、BH12 §1.4.4 と同じである。Die25 §1.3 の $P^k$ は長さ(辺の数)が $k$ の道で、$k+1$ 頂点である。
| 量 | 値 | 根拠 |
|---|---|---|
| 頂点数・辺数 | $n$、$n-1$ | 定義 |
| 次数 | 端点が $1$、内点が $2$($n\ge2$) | 定義 |
| 直径・半径 | $n-1$、$\lceil(n-1)/2\rceil$ | 距離(グラフ) の例「道グラフの距離」 |
| 連結度 | $1$($n\ge2$) | 連結度(グラフ) の例「道グラフ」 |
| 彩色数 | $2$($n\ge2$) | 番号の偶奇で塗る |
| 独立数・最大マッチングの大きさ | $\lceil n/2\rceil$、$\lfloor n/2\rfloor$ | prop-pg-count |
| 全域木の個数 | $1$ | $P_n$ は木である |
| 自己同型群の位数 | $2$($n\ge2$) | prop-pg-aut |
補グラフと同型になる道グラフは $P_1$ と $P_4$ だけである。$\overline{P_n}$ の辺の本数は $\binom n2-(n-1)=(n-1)(n-2)/2$ で、これが $n-1$ に等しいのは $n=1$ または $n=4$ のときに限るからである。
$5$ 頂点の木は同型を除いて次の 3 個である。道グラフと星グラフが両端にある。
| 木 | 次数の列 | 葉の数 | 直径 |
|---|---|---|---|
| 道グラフ $P_5$ | $2,2,2,1,1$ | $2$ | $4$ |
| $P_4$ の内点に葉を 1 つ足した木 | $3,2,1,1,1$ | $3$ | $3$ |
| 星グラフ $K_{1,4}$ | $4,1,1,1,1$ | $4$ | $2$ |
$G$ を $n\ge2$ 頂点の有限グラフとする。次は同値である。
1 ⇒ 2 と 1 ⇒ 5 は上の表による。
2 ⇒ 3:$G$ に閉路 $Z$ があるとする。$Z$ の各頂点は $Z$ の中で次数 $2$ で、$G$ の次数も $2$ 以下なので、$Z$ の頂点に接続する辺はすべて $Z$ の辺である。$G$ は連結なので $G=Z$ となり、すべての頂点の次数が $2$ で、次数 $1$ の頂点があることに反する。よって $G$ は連結で閉路をもたず、木である。
3 ⇔ 4:$n\ge2$ の木では次数は $1$ 以上で、辺が $n-1$ 本なので $\sum_v(2-d_v)=2n-2(n-1)=2$ である。3 が成り立つとき、$2-d_v$ は $0$ か $1$ で、値 $1$ の頂点、すなわち葉がちょうど $2$ 個ある。4 が成り立つとき、葉の項の和が $2$ なので、残りの頂点について $\sum(2-d_v)=0$ で、それらの次数は $2$ 以上だからすべて $2$ である。
3 ⇒ 1:葉 $v_1$ をとり、$v_2$ をその隣接頂点とする。$v_1,\dots,v_i$ まで決めたとき、$v_i$ の次数が $2$ なら、$v_{i-1}$ でない隣接頂点を $v_{i+1}$ とする。$G$ に閉路がないので $v_{i+1}$ は $v_1,\dots,v_i$ のどれでもない。$G$ は有限なので、ある $v_m$ で次数が $1$ になって止まる。$v_1,\dots,v_m$ に接続する辺は $v_iv_{i+1}$ だけなので、$G$ の連結性からこれがすべての頂点である。よって $m=n$ で $G\cong P_n$ である。
5 ⇒ 1:距離が $n-1$ の 2 頂点を結ぶ最短の道 $v_1,\dots,v_n$ は $n$ 個の相異なる頂点を通るので、$G$ のすべての頂点を通る。$v_iv_j$($j\ge i+2$)が辺なら、この道を短くできて最短性に反する。よって $G$ の辺は $v_iv_{i+1}$ だけで、$G\cong P_n$ である。$\square$
同値 1 ⇔ 5 は、頂点数を固定すると、連結グラフの直径は $n-1$ 以下で、等号が成り立つのは $P_n$ だけであることを言っている。とくに、$n$ 頂点の木の中で直径が最大なのは $P_n$ だけである。同じ議論から、連結グラフ $G$ の直径が $d$ なら、距離 $d$ の 2 頂点を結ぶ最短の道は $P_{d+1}$ と同型な誘導部分グラフを与える。
条件は次のように外せない。どの行も 1 つの条件だけを外している。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 2 の「連結」 | $P_2$ と三角形の非交和 | 次数が $2$ 以下で次数 $1$ の頂点をもてば道グラフ |
| 2 の「次数 $1$ の頂点をもつ」 | 閉路グラフ | 連結で次数が $2$ 以下なら道グラフ |
| 3 の「次数が $2$ 以下」 | $K_{1,3}$ | 木なら道グラフ |
| 頂点の有限性 | $\mathbb{N}$ の上で $i$ と $i+1$ を結ぶグラフ | 次数が $2$ 以下の木ならある $P_n$ と同型 |
1 行目の例は、次数の列 $2,2,2,1,1$ が $P_5$ と等しい。次数の列だけでは道グラフは判定できず、連結性が要る。
すべての頂点を通る道を Hamilton 路という。$n$ 頂点のグラフ $G$ が Hamilton 路をもつことは、$P_n$ と同型な全域部分グラフをもつことと同じである。$K_3$ は Hamilton 路 $1,2,3$ をもつが、辺 $\{1,3\}$ があるので $P_3$ ではない。満たす性質:Hamilton 路をもつ。満たさない性質:道グラフである。成り立たない含意は「Hamilton 路をもつ $\Rightarrow$ 道グラフ」である。ただし、$G$ が木なら、全域部分グラフ $P_n$ の $n-1$ 本の辺が $G$ のすべての辺なので、$G\cong P_n$ である。Hamilton 路は Hamilton 閉路の弱い形で、$P_n$ 自身が Hamilton 路をもち Hamilton閉路 をもたない例である(Hamilton閉路 の記事の例「反例:道グラフ」)。
$n\ge2$ のとき、$P_n$ の自己同型は恒等写像と反転 $i\mapsto n+1-i$ の $2$ 個である。
反転が自己同型であることは定義から分かる。$\pi$ を自己同型とする。次数を保つので $\pi(1)$ は端点である。$\pi$ は距離を保つので $d(\pi(1),\pi(i))=i-1$ である。$\pi(1)=1$ なら、頂点 $1$ から距離 $i-1$ の頂点は $i$ だけなので $\pi(i)=i$ である。$\pi(1)=n$ なら同様に $\pi(i)=n+1-i$ である。$\square$
グラフ同型 の定理「同型なグラフの個数」により、$n$ 個の名前付きの頂点の上の、$P_n$ と同型なグラフは $n!/2$ 個ある($n\ge2$)。$n=4$ では $12$ 個で、$4$ 頂点の名前付きの木 $16$ 個のうち、残りの $4$ 個は星グラフである。
$F_1=F_2=1$、$F_{m+2}=F_{m+1}+F_m$ を Fibonacci数 とする。$n\ge1$ について次が成り立つ。
1:個数を $a_n$ とする。$a_1=2=F_3$、$a_2=3=F_4$ である。$n\ge3$ のとき、頂点 $n$ を含まないものは $a_{n-1}$ 個、含むものは $n-1$ を含まないので $a_{n-2}$ 個である。よって $a_n=F_{n+2}$ である。頂点を $\{1,2\},\{3,4\},\dots$ と 2 個ずつ組にすると($n$ が奇数なら最後は 1 個)、独立集合は各組から高々 1 個しか含まないので大きさは $\lceil n/2\rceil$ 以下である。$\{1,3,5,\dots\}$ が等号を与える。
2:マッチングは線グラフ $L(P_n)\cong P_{n-1}$ の独立集合である。$n\ge2$ なら 1 により $F_{n+1}$ 個で、$n=1$ では空のものだけで $1=F_2$ 個である。最大の大きさは $\lceil(n-1)/2\rceil=\lfloor n/2\rfloor$ である。完全マッチングでは、葉 $1$ は辺 $\{1,2\}$ で覆うしかない。これを除くと $P_{n-2}$ が残るので、帰納法により完全マッチングは $n$ が偶数のときだけ存在し、ただ 1 つである。
3:頂点 $1$ の色が $k$ 通り、以後の頂点の色は 1 つ前の色以外の $k-1$ 通りである。$\square$
$n\ge1$ とする。$P_n$ の隣接行列の固有値は、相異なる $n$ 個の値
$$2\cos\frac{k\pi}{n+1}\qquad(k=1,2,\dots,n)$$
であり、固有値 $2\cos\frac{k\pi}{n+1}$ の固有ベクトルは $x^{(k)}:=\bigl(\sin\frac{jk\pi}{n+1}\bigr)_{1\le j\le n}$ である。
$\theta=\frac{k\pi}{n+1}$ とおき、$x_j:=\sin j\theta$($0\le j\le n+1$)とする。$x_0=0$ で、$x_{n+1}=\sin k\pi=0$ である。隣接行列 $A$ は $(Ax)_j=x_{j-1}+x_{j+1}$($1\le j\le n$)と書ける。ただし端では $x_0=x_{n+1}=0$ なので、$j=1,n$ でも隣接頂点の値の和に等しい。加法定理により
$$\sin(j-1)\theta+\sin(j+1)\theta=2\cos\theta\,\sin j\theta$$
なので、$Ax=2\cos\theta\cdot x$ である。$0< \theta< \pi$ なので $x_1=\sin\theta\ne0$ で、$x\ne0$ である。$\cos$ は $(0,\pi)$ で単射だから、$k=1,\dots,n$ の値は相異なる。$n$ 次の行列の相異なる固有値が $n$ 個見つかったので、これがすべてである。$\square$
| $n$ | スペクトル |
|---|---|
| $1$ | $0$ |
| $2$ | $1,\ -1$ |
| $3$ | $\sqrt2,\ 0,\ -\sqrt2$ |
| $4$ | $\frac{1+\sqrt5}2,\ \frac{\sqrt5-1}2,\ \frac{1-\sqrt5}2,\ \frac{-1-\sqrt5}2$ |
$k$ を $n+1-k$ に替えると符号が変わるので、スペクトルは $0$ に関して対称である($P_n$ は二部グラフである)。固有値 $0$ をもつのは $n$ が奇数のときに限る。最大の固有値は $2\cos\frac{\pi}{n+1}$ で、$2$ より小さく、$n\to\infty$ で $2$ に近づく。BH12 Theorem 3.1.3 によると、最大固有値が $2$ より小さい連結グラフは、$A_n=P_n$ と $D_n$、$E_6$、$E_7$、$E_8$ の形のものに限る(Smith の結果。この記事では証明しない)。これらは Dynkin図形で辺がすべて 1 本のものである。
特性多項式 $\varphi_n(x)=\det(xI-A)$ は、最後の行で展開すると $\varphi_n=x\varphi_{n-1}-\varphi_{n-2}$、$\varphi_0=1$、$\varphi_1=x$ を満たす。$\varphi_n(2\cos\theta)=\frac{\sin(n+1)\theta}{\sin\theta}$ も同じ漸化式を満たすので、$U_n(\cos\theta)=\frac{\sin(n+1)\theta}{\sin\theta}$ で定まる第 2 種 Chebyshev 多項式 $U_n$ を使って、$\varphi_n(x)=U_n(x/2)$ と書ける。$x=0$ を代入すると、$\det A$ は $n$ が奇数なら $0$、偶数なら $(-1)^{n/2}$ である。行列式が $0$ でないことは、完全マッチングがただ 1 つであること(prop-pg-count の 2)と対応する。
固有ベクトルの大きさは、$\sum_{j=1}^n\sin^2\frac{jk\pi}{n+1}=\frac{n+1}2$ である($2$ 倍角の公式で $\cos$ の和にすれば、$1$ の冪根の和として計算できる)。したがって次の式が得られる。
$P_n$ の頂点 $i$ から $j$ への長さ $\ell$ の歩道の個数は
$$(A^\ell)_{ij}=\frac{2}{n+1}\sum_{k=1}^n\sin\frac{ik\pi}{n+1}\sin\frac{jk\pi}{n+1}\Bigl(2\cos\frac{k\pi}{n+1}\Bigr)^\ell$$
である。$n=3$、$i=j=2$、$\ell=2$ なら、$\frac{2}{4}(1\cdot2+0+1\cdot2)=2$ で、$2\to1\to2$ と $2\to3\to2$ の $2$ 個に合う。これは、$0$ と $n+1$ に吸収壁のあるランダムウォークの、吸収されずに進む経路の数でもある。
$P_n$ の固有値の計算は、区間の上の 2 階微分の離散版である。
$n\ge1$ とし、$M_n:=2I-A$ とおく($A$ は $P_n$ の隣接行列)。
1 は $A$ の式から従う。2 は thm-pg-spectrum と $2-2\cos\theta=4\sin^2(\theta/2)$ による。固有値がすべて正の実対称行列なので正定値である。3:$D_n:=\det M_n$ は最後の行で展開すると $D_n=2D_{n-1}-D_{n-2}$ を満たし、$D_0=1$、$D_1=2$ なので $D_n=n+1$ である。$\square$
$M_n$ は $A_n$ 型の Cartan行列である。$\det M_n=n+1$ は、$A_n$ 型のルート系のウェイト格子の中でのルート格子の指数である(Cartan行列 の命題「Cartan 行列は単純ルートを基本ウェイトで表す」)。
また、$h:=\frac1{n+1}$ として区間 $[0,1]$ を幅 $h$ に刻むと、$h^{-2}M_n$ は、両端で $0$ の関数に対する $-\frac{d^2}{dx^2}$ の差分近似である。固有ベクトル $\sin(k\pi jh)$ は、連続の固有関数 $\sin k\pi x$ の値をそのまま取ったもので、固有値 $h^{-2}\cdot4\sin^2\frac{k\pi h}{2}$ は $h\to0$ で $(k\pi)^2$ に近づく。
Laplacian行列 $L=D-A$ は、端の条件だけが違う。
$n\ge1$ のとき、$P_n$ の Laplacian 行列の固有値は $2-2\cos\frac{k\pi}{n}$($k=0,1,\dots,n-1$)で、固有ベクトルは $y^{(k)}:=\bigl(\cos\frac{(2j-1)k\pi}{2n}\bigr)_{1\le j\le n}$ である。
$\theta=\frac{k\pi}{n}$、$y_j:=\cos(j-\frac12)\theta$($0\le j\le n+1$)とする。$y_0=\cos\frac\theta2=y_1$ で、$(n+\frac12)\theta=k\pi+\frac\theta2$、$(n-\frac12)\theta=k\pi-\frac\theta2$ より $y_{n+1}=y_n$ である。$1\le j\le n$ で $(Ly)_j=2y_j-y_{j-1}-y_{j+1}$ が成り立つ(端では $y_0=y_1$、$y_{n+1}=y_n$ により、次数 $1$ の頂点の式に一致する)。加法定理により $y_{j-1}+y_{j+1}=2\cos\theta\,y_j$ なので、$Ly=(2-2\cos\theta)y$ である。$y_1=\cos\frac{k\pi}{2n}\ne0$($0\le k\le n-1$)で、値は相異なるので、これがすべてである。$\square$
隣接行列の式が両端で値 $0$ の条件に対応するのに対し、Laplacian 行列の式は両端で傾き $0$ の条件に対応する。行列木定理から全域木の個数は $\frac1n\prod_{k=1}^{n-1}\bigl(2-2\cos\frac{k\pi}{n}\bigr)$ で、$P_n$ の全域木は自分自身の $1$ 個だけなので、$\prod_{k=1}^{n-1}2\sin\frac{k\pi}{2n}=\sqrt n$ という式が得られる。
長方形の格子グラフは $P_m$ と $P_n$ の直積であり、隣接行列は $A(P_m)\otimes I+I\otimes A(P_n)$ なので、固有値は $2\cos\frac{i\pi}{m+1}+2\cos\frac{j\pi}{n+1}$($1\le i\le m$、$1\le j\le n$)である。
スペクトルは BH12 §1.4.4(p. 9)にある。そこでは、$P_n$ の固有ベクトルを、頂点数 $2n+2$ の閉路グラフの固有ベクトルの差から作っている。$\zeta^{2n+2}=1$、$\zeta\ne\pm1$ として $(\zeta^j-\zeta^{-j})$ は頂点 $0$ と $n+1$ で値 $0$ をとるので、$1,\dots,n$ の部分が $P_n$ の固有ベクトルになる。これは上の $\sin j\theta$ と同じものである。Laplacian 行列の固有値も同書 §1.4.4 にある。
Die25 §1.3 では path をグラフそのものとして定義し、$G$ の path はその形の部分グラフである。道(グラフ) の記事は列として定義し、部分グラフとしての読み方を別に述べている。どちらの流儀でも、この記事の道グラフはその path を単独のグラフとして見たものである。
$P_4$ と同型な誘導部分グラフをもたないグラフの構造は、誘導部分グラフ で扱う。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する