閉路グラフ

同義語:cycle graphサイクルグラフ

概要

閉路グラフ(cycle graph)とは、$n\ge3$ に対し $\mathbb{Z}/n\mathbb{Z}$ を頂点の集合とし $i$ と $i+1$ を辺で結んだグラフ $C_n$、およびそれと同型なグラフのことで、$n$ 個の点を輪に並べた形をしている。有限グラフとしては連結で全頂点の次数が $2$ であることで特徴づけられ、自己同型群は位数 $2n$ の二面体群、隣接行列の固有値は $2\cos(2\pi k/n)$($k=0,\dots,n-1$)、彩色数は $n$ が偶数なら $2$、奇数なら $3$ である。グラフ全体の名前であり、あるグラフの中の経路である閉路とは区別する。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: グラフ, 閉路, 隣接行列

$n$ 個の点を輪の形に並べ、隣どうしを線で結ぶと、$n$ 角形の形のグラフができる。これが閉路グラフ $C_n$ である。どの頂点から見ても同じ形をしているので、次数・距離・色の塗り方・固有値など、グラフの基本的な量がほとんどすべて式で書ける。そのため、新しい概念や定理を試す最初の例としてよく使われる。
閉路グラフとグラフの閉路は別の言葉である。閉路グラフは、グラフ全体の名前である。閉路は、あるグラフの中の、出発点に戻る道筋である。$K_4$ は長さ $4$ の閉路をもつが、閉路グラフではない。あるグラフ $G$ が長さ $n$ の閉路をもつことは、$G$ が $C_n$ と同型な部分グラフをもつことと同じである(閉路 の記事の定義「閉路・内周・森」の 2)。
この記事では、閉路グラフの基本的な量を表にまとめ、スペクトル(thm-cycg-spectrum)、$k$ 色の塗り方の数(thm-cycg-colorings)、独立集合の個数(prop-cycg-independent)を証明する。また、巡回群の Cayleyグラフ としての見方を述べ、線グラフが自分自身と同型になる有限グラフが、閉路グラフの非交和に限ることを示す(thm-cycg-line)。

定義

閉路グラフ

$n\ge3$ とする。頂点の集合を $\mathbb{Z}/n\mathbb{Z}$ とし、$i$ と $i+1$ を結ぶ辺 $\{i,i+1\}$($i\in\mathbb{Z}/n\mathbb{Z}$)をもつグラフを閉路グラフ(cycle graph)といい、$C_n$ と書く。これと同型なグラフも閉路グラフという。$n$ を $C_n$ の長さという。

$C_n$ は、グラフ の記事の例「道グラフと閉路グラフ」の、頂点 $1,\dots,n$ の道グラフに辺 $\{n,1\}$ を足したものと同型である($i\bmod n$ を対応させる)。平面の上では、$1$ の $n$ 乗根を頂点とし、隣り合う根を結んだ正 $n$ 角形として描ける。
条件 $n\ge3$ は必要である。上の式で $n=2$ とすると、辺 $\{0,1\}$ と $\{1,0\}$ は同じ辺で、$K_2$ になる。$n=1$ では $\{0,1\}$ は 1 元の集合なので、単純グラフの辺にならない。多重グラフやループを許す場合に、平行な 2 本の辺を $C_2$、ループを $C_1$ とよぶ流儀はある。
次数による特徴づけは 閉路 の記事の命題「連結で次数がすべて 2 のグラフ」にある。頂点をもつ有限グラフが閉路グラフと同型であることは、連結で、すべての頂点の次数が $2$ であることと同値である。

基本の量

$n\ge3$ のとき、次の表のとおりである。

量値根拠
頂点数・辺数$n$、$n$定義
次数すべて $2$定義
直径・半径$\lfloor n/2\rfloor$距離(グラフ) の例「閉路グラフの距離」
内周$n$辺を 1 本除くと木になる
連結度・辺連結度$2$連結度(グラフ) の例「閉路グラフ」、下の注意
彩色数・辺彩色数$n$ が偶数なら $2$、奇数なら $3$cor-cycg-chi
独立数・最大マッチングの大きさ$\lfloor n/2\rfloor$prop-cycg-independent
最大クリークの大きさ$n=3$ で $3$、$n\ge4$ で $2$$C_n$ は $n\ge4$ で三角形をもたない
全域木の個数$n$下の注意
自己同型群位数 $2n$ の二面体群グラフ同型 の定理「閉路グラフの自己同型群」

辺を 1 本除くと、$n$ 頂点の道、すなわち木になる。したがって $C_n$ の閉路は全体の 1 個だけで、内周は $n$ であり、どの辺も橋ではないので辺連結度は $2$ 以上である(次数が $2$ なので $2$ に等しい)。全域木は $n-1$ 本の辺をもつので、1 本の辺を除いたものにほかならず、$n$ 個ある。

例

小さい場合
  • $C_3$ は完全グラフ $K_3$、すなわち三角形である。
  • $C_4$ は完全二部グラフ $K_{2,2}$ であり、正方形の頂点と辺でもある。
  • $C_5$ は補グラフと同型である(自己補グラフ の記事の例「5 角形 $C_5$ は自己補グラフ」)。
  • $C_6$ の補グラフは三角柱である(補グラフ の記事の例「道 $P_4$ と閉路 $C_6$」)。

補グラフと同型になる閉路グラフは $C_5$ だけである。$\overline{C_n}$ の辺の本数は $\binom n2-n$ で、これが $n$ に等しいのは $n-1=4$ のときに限るからである。

$K_5$ の辺の 2 色の塗り分け

$K_5$ の頂点を $\mathbb{Z}/5\mathbb{Z}$ とする。差が $\pm1$ の辺を赤、差が $\pm2$ の辺を青に塗る。赤の辺は $C_5$ をなし、青の辺は $i\mapsto2i$ で赤に写るのでやはり $C_5$ をなす。$C_5$ は三角形をもたないので、同じ色の三角形はない。これは Ramseyの定理 の $R(3,3)=6$ で、$5$ 頂点では足りないことを示す例である。

固有値

$C_n$ の隣接行列 $A$ は、添字を $\mathbb{Z}/n\mathbb{Z}$ として、$(Ax)_j=x_{j-1}+x_{j+1}$ で作用する。これは巡回行列であり、離散Fourier変換で対角化される。

閉路グラフのスペクトル

$n\ge3$ とし、$\omega=e^{2\pi i/n}$ とおく。$C_n$ の隣接行列の固有値は
$$2\cos\frac{2\pi k}{n}\qquad(k=0,1,\dots,n-1)$$
である(重複度を込めて)。固有ベクトルは $x^{(k)}:=(\omega^{jk})_{j\in\mathbb{Z}/n\mathbb{Z}}$ である。異なる値としては、$2$ は重複度 $1$、$n$ が偶数のとき $-2$ は重複度 $1$、それ以外の値はすべて重複度 $2$ である。

$(Ax^{(k)})_j=\omega^{(j-1)k}+\omega^{(j+1)k}=(\omega^{k}+\omega^{-k})\omega^{jk}=2\cos\frac{2\pi k}{n}\,x^{(k)}_j$ である。$k\ne k'$ なら $\sum_j\omega^{j(k-k')}=0$ なので、$x^{(0)},\dots,x^{(n-1)}$ は互いに直交する $n$ 個のベクトルで、$\mathbb{C}^n$ の基底をなす。よって固有値は重複度を込めてこの $n$ 個である(隣接行列 の例「閉路グラフ」と同じ計算である)。
重複度を調べる。$\cos$ は $[0,\pi]$ で単射で、$\cos\frac{2\pi k}{n}=\cos\frac{2\pi(n-k)}{n}$ であるから、$0\le k,k'\le n-1$ について値が等しいのは $k'=k$ または $k'\equiv-k\pmod n$ のときに限る。$k\equiv-k$ となるのは $k=0$ と、$n$ が偶数のときの $k=n/2$ だけで、これらが値 $2$ と $-2$ を与える。ほかの値は $\{k,n-k\}$ の 2 つから得られる。$\square$

$n$スペクトル
$3$$2,\ -1,\ -1$
$4$$2,\ 0,\ 0,\ -2$
$5$$2,\ \frac{\sqrt5-1}2,\ \frac{\sqrt5-1}2,\ \frac{-\sqrt5-1}2,\ \frac{-\sqrt5-1}2$
$6$$2,\ 1,\ 1,\ -1,\ -1,\ -2$

固有値 $-2$ をもつのは $n$ が偶数のときに限り、これは $C_n$ が二部グラフである条件と一致する。次数が $2$ の正則グラフなので、Laplacian行列 $2I-A$ の固有値は $2-2\cos\frac{2\pi k}{n}=\lvert1-\omega^k\rvert^2$ である。行列木定理から、連結グラフの全域木の個数は Laplacian 行列の $0$ でない固有値の積の $1/n$ 倍である。$\prod_{k=1}^{n-1}(1-\omega^k)$ は $\frac{x^n-1}{x-1}=1+x+\dots+x^{n-1}$ の $x=1$ での値 $n$ に等しいので、積は $n^2$ で、全域木の個数は $n$ になる。これは上の数え方と合う。

閉じた歩道の数

頂点 $0$ から出て長さ $\ell$ で $0$ に戻る歩道の個数を $w_\ell$ とする。$+1$ に進む回数を $j$ とすると $-1$ に進む回数は $\ell-j$ で、$0$ に戻る条件は $2j-\ell\equiv0\pmod n$ である。よって
$$w_\ell=\sum_{\substack{0\le j\le\ell\\2j\equiv\ell\ (\mathrm{mod}\ n)}}\binom{\ell}{j}$$
である。一方、頂点の間の対称性からすべての頂点で同じ個数なので、$w_\ell=\frac1n\operatorname{tr}A^\ell=\frac1n\sum_{k=0}^{n-1}\bigl(2\cos\frac{2\pi k}{n}\bigr)^\ell$ である。たとえば $C_4$、$\ell=4$ では、左は $j=0,2,4$ で $1+6+1=8$、右は $\frac14(16+0+16+0)=8$ である。

色の塗り方

$k$ 色で隣り合う頂点を違う色に塗る方法の数は、完全グラフの閉じた歩道の数として求められる。

閉路グラフの色の塗り方の数

$n\ge3$、$k\ge1$ とする。$C_n$ の頂点を $k$ 色で、隣り合う頂点が違う色になるように塗る方法の数は
$$(k-1)^n+(-1)^n(k-1)$$
である。

色の集合を $K_k$ の頂点の集合とする。塗り方 $c\colon\mathbb{Z}/n\mathbb{Z}\to\{1,\dots,k\}$ に列 $c(0),c(1),\dots,c(n-1),c(0)$ を対応させる。隣り合う頂点の色が違うという条件は、この列の隣り合う項が違うこと、すなわち列が $K_k$ の長さ $n$ の閉歩道であることと同じである。よって塗り方の数は、$K_k$ の始点付きの長さ $n$ の閉歩道の個数、すなわち隣接行列の $n$ 乗のトレースに等しい。$K_k$ の隣接行列の固有値は $k-1$(重複度 $1$)と $-1$(重複度 $k-1$)なので(隣接行列 の例「完全グラフと完全二部グラフ」)、トレースは $(k-1)^n+(k-1)(-1)^n$ である。$\square$

これは 彩色多項式 の記事の例の式と同じものを、別の方法で導いたものである。

閉路グラフの彩色数

$C_n$ の彩色数は、$n$ が偶数なら $2$、奇数なら $3$ である。辺彩色数も同じである。

$k=1$ の値は $0$ である。$k=2$ の値は $1+(-1)^n$ で、$n$ が偶数なら $2$、奇数なら $0$ である。$k=3$ の値は $2^n+2(-1)^n>0$ である。これで彩色数が分かる。辺を塗ることは線グラフ $L(C_n)\cong C_n$ の頂点を塗ることと同じなので、辺彩色数も同じ値である。$\square$

$n\ge5$ が奇数のとき、$C_n$ は三角形をもたないが彩色数は $3$ である。つまり、彩色数は最大クリークの大きさより大きくなることがある。$C_5$ はその例である(誘導部分グラフ)。

独立集合とマッチング

Fibonacci数を $F_1=F_2=1$、$F_{m+2}=F_{m+1}+F_m$ とし、Lucas 数を $L_1=1$、$L_2=3$、$L_{m+2}=L_{m+1}+L_m$ とする。

独立集合とマッチングの個数

$n\ge3$ とする。

  1. $C_n$ の独立集合の最大の大きさと、マッチングの最大の大きさは、どちらも $\lfloor n/2\rfloor$ である。
  2. $C_n$ の独立集合の個数(空集合を含む)と、マッチングの個数(空のものを含む)は、どちらも Lucas 数 $L_n$ である。

1:独立集合 $I$ の各頂点は 2 本の辺に接続し、$I$ の相異なる頂点は辺を共有しないので $2\lvert I\rvert\le n$ である。$\{0,2,\dots,2\lfloor n/2\rfloor-2\}$ は大きさ $\lfloor n/2\rfloor$ の独立集合である。マッチング $M$ の辺は頂点を共有しないので $2\lvert M\rvert\le n$ で、$\{0,1\},\{2,3\},\dots$ から $\lfloor n/2\rfloor$ 本がとれる。
2:頂点が $m$ 個一列に並び、隣どうしだけが辺で結ばれたグラフ($m=0$ なら空)の独立集合の個数を $a_m$ とする。$a_0=1=F_2$、$a_1=2=F_3$ で、最後の頂点を含まないものが $a_{m-1}$ 個、含むものが $a_{m-2}$ 個なので $a_m=a_{m-1}+a_{m-2}$($m\ge2$)、すなわち $a_m=F_{m+2}$ である。
$C_n$ の独立集合のうち、頂点 $0$ を含まないものは、残りの $n-1$ 個の頂点の列の独立集合なので $a_{n-1}$ 個、$0$ を含むものは、$\pm1$ を除いた $n-3$ 個の頂点の列の独立集合なので $a_{n-3}$ 個ある。合計は $F_{n+1}+F_{n-1}$ である。$b_m:=F_{m+1}+F_{m-1}$($m\ge2$)とすると $b_2=F_3+F_1=3$、$b_3=F_4+F_2=4$ で、$b$ は同じ漸化式を満たすから、$L_2=3$、$L_3=4$ と合わせて $b_m=L_m$ である。
マッチングは線グラフの独立集合と同じものであり、$L(C_n)\cong C_n$ だから、個数は同じである。$\square$

$n=3,4,5,6$ のとき個数は $4,7,11,18$ である。$C_4$ の独立集合は、空集合、$1$ 点が $4$ 個、対角の $2$ 点が $2$ 個の $7$ 個である。

巡回群の Cayley グラフとして見る

$C_n$ の定義は、巡回群 $\mathbb{Z}/n\mathbb{Z}$ の生成元 $1$ と $-1$ で隣を決めている。つまり $C_n=\operatorname{Cay}(\mathbb{Z}/n\mathbb{Z},\{1,-1\})$ である(Cayleyグラフ)。生成元を取り替えても同じ形が現れ、生成元でない元をとると輪が分かれる。

巡回群の 2 元 $\pm u$ が定める輪

$n\ge3$ とし、$u\in\mathbb{Z}/n\mathbb{Z}$ は $u\ne0$、$2u\ne0$ を満たすとする。$u$ の代表の整数と $n$ の最大公約数を $g$、$m:=n/g$ とする。このとき $\operatorname{Cay}(\mathbb{Z}/n\mathbb{Z},\{u,-u\})$ は $g$ 個の $C_m$ の非交和である。とくに、これが連結であることと $g=1$ は同値で、そのとき $C_n$ と同型である。

$H$ を $u$ の生成する部分群とすると、$H$ の位数は $m$ である。$u\ne0$、$2u\ne0$ より $m\ne1,2$ なので $m\ge3$ である。$x$ と $x\pm u$ は同じ剰余類に属するので、辺は各剰余類の中を結ぶ。剰余類は $g$ 個ある。剰余類 $x+H$ について、$j\mapsto x+ju$ は $\mathbb{Z}/m\mathbb{Z}$ から $x+H$ への全単射で、$j$ と $j\pm1$ の隣接を $x+ju$ と $x+ju\pm u$ の隣接に写す。よって各剰余類の上のグラフは $C_m$ である。$\square$

$u\ne0$ かつ $2u=0$ のときは、$\{u,-u\}$ は 1 元の集合で、次数は $1$ になる。また、同じ閉路グラフが別の群の Cayley グラフとして現れることもある。

二面体群の 2 つの鏡映

$D$ を、位数 $2$ の相異なる 2 元 $s,t$ で生成される位数 $2m$($m\ge2$)の二面体群とする。$\operatorname{Cay}(D,\{s,t\})$ は連結で、すべての頂点の次数が $2$ である有限グラフなので、$C_{2m}$ と同型である。輪は $1,s,st,sts,\dots$ と $s,t$ を交互に掛けてたどれる。$C_{2m}$ は巡回群 $\mathbb{Z}/2m\mathbb{Z}$ の Cayley グラフでもあるので、Cayley グラフは群を決めない。$m=2$ では $D$ は $\mathbb{Z}/2\mathbb{Z}$ の 2 個の直積で、$\mathbb{Z}/4\mathbb{Z}$ と同型でないが、どちらからも $C_4$ が得られる。

自己同型群については、グラフ同型 の定理「閉路グラフの自己同型群」の証明が示すとおり、自己同型は $0$ と $1$ の行き先で決まる。$0$ の行き先は $n$ 通り、$1$ の行き先はその 2 つの隣のどちらかで、そのすべてが実現される。したがって、自己同型群は、隣り合う頂点の順序対($2n$ 個ある)の上に単純推移的に作用する。正 $n$ 角形の対称性の群を見ているのと同じことである。

線グラフと同型な有限グラフ

線グラフ $L(G)$ は、$G$ の辺を頂点とし、端点を共有する 2 辺を結んだグラフである。辺を巡回的に並べると $L(C_n)\cong C_n$ が分かる。有限グラフでは、この性質が 2-正則グラフを特徴づける。

線グラフと同型な有限グラフ

$G$ を頂点を 1 個以上もつ有限グラフとする。$L(G)\cong G$ であることと、$G$ のすべての頂点の次数が $2$ であることは同値である。このとき $G$ は閉路グラフの非交和であり、$G$ が連結なら閉路グラフである。

すべての頂点の次数が $2$ とする。閉路 の記事の命題「連結で次数がすべて 2 のグラフ」により $G$ は閉路グラフの非交和で、線グラフは成分ごとに作れるので $L(G)\cong G$ である。
逆に $L(G)\cong G$ とし、$G$ の頂点数を $n$、次数を $d_v$ とする。$L(G)$ の頂点数は $G$ の辺数に等しいので、辺数も $n$ である。よって $\sum_vd_v=2n$ である。単純グラフでは端点を共有する 2 辺の共有点は 1 個だけなので、$L(G)$ の辺数は $\sum_v\binom{d_v}{2}$ であり、これが $G$ の辺数 $n$ に等しいので、$\sum_vd_v^2=2n+\sum_vd_v=4n$ である。すると
$$\sum_v(d_v-2)^2=\sum_vd_v^2-4\sum_vd_v+4n=4n-8n+4n=0$$
なので、すべての $v$ で $d_v=2$ である。$\square$

反例

閉路グラフの特徴づけの条件を 1 つずつ外すと、次のようになる。

外す条件反例成り立たなくなること
連結性2 つの三角形の非交和次数がすべて $2$ なら閉路グラフ
次数がすべて $2$頂点 $3$ 個の道連結なら閉路グラフ
頂点の有限性$\mathbb{Z}$ の上で $i$ と $i+1$ を結ぶグラフ連結で次数がすべて $2$ なら閉路グラフ
thm-cycg-line の有限性$\mathbb{N}$ の上で $i$ と $i+1$ を結ぶグラフ$L(G)\cong G$ なら次数がすべて $2$
prop-cycg-cayley の $g=1$$\mathbb{Z}/6\mathbb{Z}$、$u=2$(2 つの三角形)$\operatorname{Cay}(\mathbb{Z}/n\mathbb{Z},\{u,-u\})$ が連結

1 行目のグラフと $C_6$ は頂点数も次数の多重集合も等しいが、同型でない(グラフ同型 の表)。4 行目では、辺 $e_i=\{i,i+1\}$ を $i$ に写すと $L(G)\cong G$ であるが、頂点 $0$ の次数は $1$ である。

反例:閉路をもつだけでは閉路グラフでない

$K_4$ は、$4$ 頂点すべてを通る長さ $4$ の閉路をもつので、$C_4$ と同型な全域部分グラフをもつ。しかし次数が $3$ なので $K_4$ は閉路グラフでない。満たす性質:長さが頂点数に等しい閉路をもつ(Hamilton閉路をもつ)。満たさない性質:閉路グラフである。成り立たない含意は「Hamilton閉路をもつ $\Rightarrow$ 閉路グラフ」である。$C_4$ と同型な部分グラフは $K_4$ の誘導部分グラフにはならない。残りの 2 本の辺(対角線)が加わるからである。

補足

Die25 §1.3 では、path と cycle をグラフそのものとして定義し、長さ $k$ の cycle を $C^k$ と書く。そこでの「$G$ の cycle」は、$G$ の部分グラフのことである。この記事の閉路グラフは、その cycle を単独のグラフとして見たものである。$C_n$ の添字は頂点数と長さのどちらと読んでも同じである。
スペクトルは BH12 §1.4.3(pp. 8–9)にある。Smith による分類では、最大固有値がちょうど $2$ である連結グラフのうち、$C_{n+1}$ は記号 $\hat A_n$ の系列にあたる(BH12 Theorem 3.1.3、この記事では証明しない)。この記号は Dynkin図形 の $A_n$ に 1 頂点足した図を表す。
閉路空間(閉路)の次元は、辺数 $-$ 頂点数 $+$ 連結成分の個数 $=n-n+1=1$ である。新しい頂点 1 個を $C_n$ の全頂点と結ぶと車輪グラフが得られる。

関連項目

参考文献

[2]
Andries E. Brouwer, Willem H. Haemers, Spectra of Graphs, Universitext, Springer, 2012, §1.4.3 The cycle(pp. 8–9)、§3.1.1 の Theorem 3.1.3(p. 34)。頁は著者公開版(2011-02-01)の頁

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する