Laplacian行列
概要
Laplacian行列（Laplacian matrix）とは、グラフの次数を並べた対角行列 $D$ から隣接行列 $A$ を引いた行列 $L=D-A$ のことである。$x^{\mathsf T}Lx$ は隣り合う頂点の値の差の 2 乗の和になるので、$L$ は半正定値で、固有値 $0$ の重複度はグラフの連結成分の個数に等しい。2 番目に小さい固有値を代数的連結度、その固有ベクトルを Fiedler ベクトルといい、代数的連結度はグラフが連結なときに限り正である。
Laplacian 行列（Laplacian matrix）とは、グラフ $G$ の頂点の次数を並べた対角行列 $D$ から隣接行列 $A$ を引いた行列 $L=D-A$ のことである。Laplace 行列、グラフラプラシアンとも呼ぶ。隣接行列が「どの頂点とどの頂点がつながっているか」をそのまま記録するのに対し、Laplacian 行列は、頂点の上の関数 $x$ に対して「隣どうしの値の差の 2 乗の和」
$$
x^{\mathsf T}Lx=\sum_{uv\in E}(x_u-x_v)^2
$$
を与える 2 次形式として働く。この式から、Laplacian 行列の固有値はすべて $0$ 以上であり、固有値 $0$ の重複度はグラフの連結成分の個数に等しいことがしたがう。この記事の主定理はこの事実であり、記事の中で完全に証明する。
2 番目に小さい固有値は 代数的連結度（algebraic connectivity）と呼ばれ、グラフが連結であるときに限り正になる。その固有ベクトル（Fiedler ベクトル）の符号は、グラフを 2 つに切り分ける目安になる。Laplacian 行列の小行列式が全域木の個数を与えることは 行列木定理 で扱う。
定義
この記事では、グラフは有限で無向とし、ループ（両端が同じ辺）はもたないとする。多重辺は許す。頂点集合を $V=\{1,\dots,n\}$、辺集合を $E$ とし、$|E|=m$ とする。
$G$ の隣接行列を $A$（$A_{uv}$ は $u$ と $v$ を結ぶ辺の本数）、頂点 $u$ の次数を $d_u$、$D=\operatorname{diag}(d_1,\dots,d_n)$ とする。
$$
L:=D-A,\qquad L_{uu}=d_u,\qquad L_{uv}=-A_{uv}\ (u\neq v)
$$
を $G$ の Laplacian 行列 という。$L$ の固有値を重複度こめて $\mu_1\le\mu_2\le\dots\le\mu_n$ と並べたものを $G$ の Laplacian スペクトル という。
$L$ の各行の和は $d_u-\sum_vA_{uv}=0$ である。つまり、すべての成分が $1$ のベクトル $\mathbf 1$ について $L\mathbf 1=0$ であり、$0$ は必ず固有値になる。$L$ は実対称行列なので、固有値はすべて実数で、固有ベクトルからなる $\mathbb R^n$ の正規直交基底がある（スペクトル定理 の定理「有限次元の自己共役スペクトル定理」）。定義は BH11 §1.1（p. 1）にある。
$G$ の各辺に向きを 1 つずつ決める（どちらの端を始点にしてもよい）。$n\times m$ 行列 $N$ を、辺 $e$ が $u$ から $w$ へ向くとき
$$
N_{ue}=1,\qquad N_{we}=-1,\qquad \text{それ以外の頂点 }v\text{ で }N_{ve}=0
$$
で定め、$G$ の（向きに関する）向き付き接続行列 という。
道 $P_3$（頂点 $1,2,3$、辺 $12$、$23$）では
$$
L=\begin{pmatrix}1&-1&0\\-1&2&-1\\0&-1&1\end{pmatrix}
$$
であり、固有値は $0,1,3$、固有ベクトルはそれぞれ $(1,1,1)$、$(1,0,-1)$、$(1,-2,1)$ である（BH11 §1.2、p. 2）。辺 $12$ を $1\to2$、辺 $23$ を $2\to3$ と向き付けると
$$
N=\begin{pmatrix}1&0\\-1&1\\0&-1\end{pmatrix},\qquad NN^{\mathsf T}=\begin{pmatrix}1&-1&0\\-1&2&-1\\0&-1&1\end{pmatrix}=L
$$
となる。これは次の命題の一例である。
半正定値性と 2 次形式
向きをどう選んでも $L=NN^{\mathsf T}$ である。したがって、任意の $x\in\mathbb R^n$ について
$$
x^{\mathsf T}Lx=\|N^{\mathsf T}x\|^2=\sum_{e\in E}(x_{u(e)}-x_{w(e)})^2\ \ge 0
$$
（$u(e),w(e)$ は $e$ の両端）であり、$L$ は半正定値である。とくに $L$ の固有値はすべて $0$ 以上である。
$(NN^{\mathsf T})_{uv}=\sum_{e\in E}N_{ue}N_{ve}$ を計算する。$u=v$ のとき、$N_{ue}^2$ は $e$ が $u$ に接続すれば $1$、しなければ $0$ なので（ループはない）、和は $u$ に接続する辺の本数 $d_u$ である。$u\neq v$ のとき、$N_{ue}N_{ve}\neq0$ となるのは $e$ の両端が $u$ と $v$ であるときで、そのとき一方が $1$、他方が $-1$ なので積は $-1$ である。よって和は $u$ と $v$ を結ぶ辺の本数の $-1$ 倍 $-A_{uv}$ である。これで $NN^{\mathsf T}=D-A=L$ が示された。
次に $x^{\mathsf T}Lx=x^{\mathsf T}NN^{\mathsf T}x=(N^{\mathsf T}x)^{\mathsf T}(N^{\mathsf T}x)=\|N^{\mathsf T}x\|^2$ である。$N^{\mathsf T}x$ の $e$ 成分は $\sum_vN_{ve}x_v=x_{u(e)}-x_{w(e)}$（$e$ が $u(e)$ から $w(e)$ へ向くとき）なので、2 乗の和は向きによらず $\sum_e(x_{u(e)}-x_{w(e)})^2$ である。最後に、$Lx=\mu x$、$x\neq0$ なら $\mu\,x^{\mathsf T}x=x^{\mathsf T}Lx\ge0$ で $x^{\mathsf T}x>0$ なので $\mu\ge0$ である。$\square$
この命題は BH11 §1.1（p. 1）にある。固有値の和は跡 $\operatorname{tr}L=\sum_ud_u=2m$ に等しい（BH11 §1.3、pp. 3–4）。
主定理：固有値 0 の重複度と連結成分
$G$ の連結成分を $G_1,\dots,G_c$、その頂点集合を $V_1,\dots,V_c$ とする。このとき
$$
\ker L=\{x\in\mathbb R^n\mid x\text{ は各 }V_i\text{ の上で定数}\}
$$
であり、$\dim\ker L=c$ である。$L$ は対称なので、固有値 $0$ の重複度は $G$ の連結成分の個数 $c$ に等しい。
段 1（核の特徴づけ）．$x$ が各 $V_i$ の上で定数なら、どの辺も両端が同じ成分にあるので $N^{\mathsf T}x=0$、したがって $Lx=N(N^{\mathsf T}x)=0$ である。逆に $Lx=0$ とすると、prop-lap-quadratic により
$$
0=x^{\mathsf T}Lx=\sum_{e\in E}(x_{u(e)}-x_{w(e)})^2
$$
であり、各項は $0$ 以上なので、すべての辺 $e$ で $x_{u(e)}=x_{w(e)}$ である。同じ成分 $V_i$ の 2 頂点 $u,v$ は $G_i$ の道 $u=v_0,v_1,\dots,v_k=v$ で結ばれ、隣り合う頂点で値が等しいので $x_u=x_{v_1}=\dots=x_v$ である。よって $x$ は各 $V_i$ の上で定数である。
段 2（次元）．$V_i$ の上で $1$、ほかで $0$ のベクトルを $\mathbf 1_{V_i}$ とする。段 1 により $\ker L$ は $\mathbf 1_{V_1},\dots,\mathbf 1_{V_c}$ で張られる。これらは台が互いに交わらない $0$ でないベクトルなので線形独立であり、$\dim\ker L=c$ である。
段 3（重複度）．実対称行列では、各固有値の代数的重複度は固有空間の次元に等しい（スペクトル定理）。固有値 $0$ の固有空間は $\ker L$ なので、重複度は $c$ である。$\square$
この定理は BH11 Proposition 1.3.7（p. 7）にある。とくに次がしたがう。
$n\ge2$ とする。$G$ が連結であることと $\mu_2>0$ であることは同値である。このとき $\ker L$ は $\mathbf 1$ で張られる。
隣接行列のスペクトルからは、一般には連結かどうかを読み取れない（後の節「反例と注意」の表）。Laplacian スペクトルは、$0$ の重複度という形で連結成分の個数をそのまま含んでいる。
スペクトルの例
$J$ をすべての成分が $1$ の行列とする。
完全グラフ．$K_n$ では $L=nI-J$ である。$J$ の固有値は $n$（固有ベクトル $\mathbf 1$）と $0$（重複度 $n-1$、$\mathbf 1$ に直交するベクトル）なので、$L$ のスペクトルは $0$（重複度 $1$）と $n$（重複度 $n-1$）である（BH11 §1.4.1、p. 8）。
正則グラフ．すべての頂点の次数が $k$ なら $L=kI-A$ なので、隣接行列の固有値 $\lambda_1\ge\dots\ge\lambda_n$ と $\mu_i=k-\lambda_i$ で対応する（BH11 §1.3.1、p. 4）。
補グラフ．$G$ が単純グラフ（多重辺もない）なら、補グラフ $\overline G$ の Laplacian 行列は $\overline L=nI-J-L$ である。$L$ の固有ベクトルを $\mathbf 1$ と、$\mathbf 1$ に直交するもの $u_2,\dots,u_n$（$Lu_i=\mu_iu_i$）からなる正規直交基底にとると、$Ju_i=0$ なので $\overline Lu_i=(n-\mu_i)u_i$ である。よって $\overline G$ の Laplacian スペクトルは $0,\ n-\mu_n,\dots,n-\mu_2$ であり、固有値は $0$ 以上なので $\mu_n\le n$ である（BH11 §1.3.2、p. 4）。
閉路．閉路グラフ $C_n$（頂点 $0,\dots,n-1$、$j$ と $j+1$ を $n$ を法として結ぶ）で $\omega=e^{2\pi\sqrt{-1}\,k/n}$ とし、$x_j=\omega^j$ とおくと
$$
(Lx)_j=2\omega^j-\omega^{j-1}-\omega^{j+1}=(2-\omega-\omega^{-1})\,\omega^j
$$
なので、$2-2\cos(2\pi k/n)$（$k=0,\dots,n-1$）が固有値である。$k$ ごとのベクトル $x$ は異なる固有値に属するか、Vandermonde 行列の列として線形独立なので、これで重複度こめてすべてである（BH11 §1.4.3、p. 9）。例えば $C_4$ のスペクトルは $0,2,2,4$ である。
道．道 $P_n$ の Laplacian スペクトルは $2-2\cos(\pi k/n)$（$k=0,\dots,n-1$）であり（BH11 §1.4.4、p. 9）、$k$ に対する固有ベクトルは $x_j=\cos\bigl(\pi k(j-\tfrac12)/n\bigr)$（$j=1,\dots,n$）である。$n=4$ では $0,\ 2-\sqrt2,\ 2,\ 2+\sqrt2$ である（計算機でも確かめた）。
| グラフ | Laplacian スペクトル | $\mu_2$（代数的連結度） |
|---|---|---|
| $K_n$ | $0,\ n^{(n-1)}$ | $n$ |
| $K_{p,q}$（$p+q\ge3$） | $0,\ p^{(q-1)},\ q^{(p-1)},\ p+q$ | $\min(p,q)$ |
| $C_n$ | $2-2\cos(2\pi k/n)$ | $2-2\cos(2\pi/n)$ |
| $P_n$ | $2-2\cos(\pi k/n)$ | $2-2\cos(\pi/n)$ |
| 星 $K_{1,n-1}$（$n\ge3$） | $0,\ 1^{(n-2)},\ n$ | $1$ |
| Petersen グラフ | $0,\ 2^{(5)},\ 5^{(4)}$ | $2$ |
右肩の括弧の中の数は重複度である。$K_{p,q}$ は BH11 §1.4.2（p. 8）、Petersen グラフは 3 正則で隣接行列の固有値が $3,1^{(5)},(-2)^{(4)}$（BH11 §1.4.5、p. 10）であることから $\mu_i=3-\lambda_i$ で求めた。完全二部グラフ の記事もこのスペクトルを扱っている。
道 $P_n$ では $(Lx)_j=-(x_{j+1}-2x_j+x_{j-1})$（$1< j< n$）であり、これは 2 階差分の符号を変えたものである。Laplacian 行列は、微分作用素 $-\frac{d^2}{dt^2}$ の差分版をグラフの上に広げたものとみなせる。
代数的連結度と Fiedler ベクトル
$n\ge2$ とする。$G$ の Laplacian 行列の 2 番目に小さい固有値 $a(G):=\mu_2$ を $G$ の 代数的連結度 という。固有値 $\mu_2$ に属する固有ベクトルを $G$ の Fiedler ベクトル という。
代数的連結度は Fiedler が導入した（Fie73 §1、p. 298。BH11 §1.7、p. 13）。Fiedler は、$a(G)$ に属する固有ベクトルの成分を頂点に割り当てたものを、グラフの characteristic valuation と呼んで調べた（Fie75 p. 624）。cor-lap-connected により、$a(G)>0$ であることと $G$ が連結であることは同値である。
$n\ge2$ とすると
$$
a(G)=\min\Bigl\{\frac{x^{\mathsf T}Lx}{x^{\mathsf T}x}\ \Bigm|\ x\in\mathbb R^n,\ x\neq0,\ x^{\mathsf T}\mathbf 1=0\Bigr\}
$$
であり、$x^{\mathsf T}\mathbf 1=0$、$x\neq0$ をみたす $x$ で最小値をとるのは $Lx=a(G)\,x$ となる $x$ に限る。
$L\mathbf 1=0$ で $0$ は最小の固有値なので、$\ker L$ の正規直交基底を $u_1=\mathbf 1/\sqrt n$ から始めてとり、ほかの固有空間の正規直交基底と合わせて、$Lu_i=\mu_iu_i$ をみたす $\mathbb R^n$ の正規直交基底 $u_1,\dots,u_n$ をとる（スペクトル定理）。$x^{\mathsf T}\mathbf 1=0$ なら $x$ は $u_1$ に直交するので $x=\sum_{i\ge2}c_iu_i$ と書け、
$$
x^{\mathsf T}Lx=\sum_{i\ge2}\mu_ic_i^2\ \ge\ \mu_2\sum_{i\ge2}c_i^2=\mu_2\,x^{\mathsf T}x
$$
である。等号は $\mu_i>\mu_2$ となる $i$ で $c_i=0$ となること、すなわち $Lx=\mu_2x$ と同値である。$x=u_2$ で等号が成り立つので、最小値は $\mu_2$ である。$\square$
この特徴づけから、辺を増やしても代数的連結度は減らないことがわかる。
$G$ と $H$ を同じ頂点集合の上のグラフで、辺を共有しないものとし、$G\cup H$ をそれらの辺を合わせたグラフとする。このとき
$$
a(G\cup H)\ \ge\ a(G)+a(H)\ \ge\ a(G)
$$
である。
Laplacian 行列は辺ごとの寄与の和なので $L_{G\cup H}=L_G+L_H$ である。prop-lap-rayleigh により、$x^{\mathsf T}\mathbf 1=0$、$x^{\mathsf T}x=1$ をみたす $x$ について
$$
x^{\mathsf T}L_{G\cup H}x=x^{\mathsf T}L_Gx+x^{\mathsf T}L_Hx\ \ge\ a(G)+a(H)
$$
であり、左辺のそのような $x$ についての最小値が $a(G\cup H)$ である。$a(H)\ge0$ から 2 つ目の不等式がしたがう。$\square$
この命題は Fie73 3.1・3.2（pp. 298–299）と BH11 Proposition 1.7.1（p. 13）にある。次の定理は、代数的連結度が組合せ的な連結度の下界であることを述べる。$G$ の 頂点連結度 $\kappa(G)$ は 連結度(グラフ) の記事で定義したもので、完全グラフでない単純グラフでは、取り除くと残りが連結でなくなる頂点集合の大きさの最小値である。
$G$ を完全グラフでない単純グラフとする（$n\ge2$）。頂点集合 $S\subset V$ を取り除いたグラフ $G-S$ が連結でないなら、$a(G)\le|S|$ である。とくに $a(G)\le\kappa(G)$ である。
$G-S$ の連結成分の 1 つの頂点集合を $C$ とし、$R:=V\setminus(S\cup C)$ とおく。$G-S$ は連結でないので $C$ も $R$ も空でない。$G$ に、$S$ の頂点と $V\setminus S$ の頂点を結ぶ辺のうち $G$ にないものをすべて加えた単純グラフを $H$ とする。加えた辺からなるグラフを $H'$ とすると $H=G\cup H'$ なので、prop-lap-monotone により $a(G)\le a(H)$ である。
$H$ でも $C$ と $R$ を結ぶ辺はなく（加えた辺は一端が $S$ にある）、$V\setminus S$ の各頂点は $S$ のすべての頂点とちょうど 1 本の辺で結ばれている。ベクトル $u$ を
$$
u_v=|R|\ (v\in C),\qquad u_v=-|C|\ (v\in R),\qquad u_v=0\ (v\in S)
$$
で定めると、$u\neq0$ かつ $u^{\mathsf T}\mathbf 1=|C||R|-|R||C|=0$ である。$H$ の Laplacian 行列を $L_H$ とし、$(L_Hu)_v=\sum_{w\sim v}(u_v-u_w)$（和は $H$ で $v$ に隣接する $w$ にわたる）を計算する。$v\in C$ なら、隣接する頂点は $C$ か $S$ にあり、$C$ の頂点との差は $0$、$S$ の $|S|$ 個の頂点との差はどれも $|R|$ なので $(L_Hu)_v=|S|\,u_v$ である。$v\in R$ でも同様に $(L_Hu)_v=|S|\,u_v$ である。$v\in S$ なら、$u_v=0$ で、$v$ は $V\setminus S$ のすべての頂点に隣接し、$S$ の頂点では $u=0$ なので
$$
(L_Hu)_v=-\sum_{w\in C\cup R}u_w=-(|C||R|-|R||C|)=0=|S|\,u_v
$$
である。よって $L_Hu=|S|\,u$ であり、prop-lap-rayleigh により $a(H)\le u^{\mathsf T}L_Hu/u^{\mathsf T}u=|S|$ である。合わせて $a(G)\le|S|$ を得る。$G$ は完全グラフでないので、隣接しない 2 頂点がありそれ以外の頂点を取り除けば連結でなくなる。取り除いて連結でなくなる頂点集合の大きさの最小値が $\kappa(G)$ なので、$a(G)\le\kappa(G)$ である。$\square$
この定理は Fie73 4.1（p. 303）と BH11 Proposition 1.7.2（pp. 13–14）にあり、証明は後者に従った。$G$ が連結でない場合は $S=\emptyset$ ととれて、$a(G)=0$ と整合する。
Fiedler ベクトルの符号は、グラフの形を反映する。次の定理はこの記事では証明しない。
$G$ を連結なグラフ、$y$ を Fiedler ベクトルとする。$r\ge0$ について $M(r):=\{v\in V\mid y_v+r\ge0\}$ とおくと、$G$ の $M(r)$ の上の誘導部分グラフは連結である。$\{v\mid y_v-r\le0\}$ についても同様である。この定理の証明は Fie75 に譲り、この記事では証明しない。
この定理は Fie75 (3,3) と (3,4)（pp. 625–626）にある（そこでは辺に正の重みのついたグラフで述べている）。$r=0$ の場合、$y\ge0$ となる頂点の集合と $y\le0$ となる頂点の集合は、どちらも連結な部分グラフをなす。例えば道 $P_n$ の Fiedler ベクトルは $y_j=\cos\bigl(\pi(j-\tfrac12)/n\bigr)$ で、$j$ について単調に減るので、符号で分けると道の前半と後半になる（$n=4$ では $y\approx(0.92,0.38,-0.38,-0.92)$）。Fiedler ベクトルの符号でグラフを 2 つに分ける方法は、このような性質を手がかりにしている。
辺に重みのあるグラフ
辺 $e$ に正の重み $c_e>0$ があるとき、$L_{uv}:=-\sum_{e:\,u\text{–}v}c_e$（$u\neq v$）、$L_{uu}:=\sum_{e\ni u}c_e$ とおくと、prop-lap-quadratic と同じ計算で
$$
x^{\mathsf T}Lx=\sum_{e\in E}c_e\,(x_{u(e)}-x_{w(e)})^2
$$
となり、半正定値性・thm-lap-kernel・prop-lap-rayleigh はそのまま成り立つ（証明の $N$ を、$e$ 列を $\sqrt{c_e}$ 倍した行列に替えればよい）。Fiedler はこの設定で代数的連結度を扱っている（Fie75 (6)、p. 624）。重みが正であるという仮定は外せない（次の節の表の 4 行目）。
反例と注意
| 外す条件・替える条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $D-A$ を $D+A$（符号なし Laplacian）に替える | 三角形 $K_3$ | 連結なのに $D+A$ のスペクトルは $1,1,4$ で、$0$ の重複度が連結成分の個数 $1$ と一致しない |
| Laplacian の代わりに隣接行列のスペクトルを見る | 星 $K_{1,4}$ と、孤立点と $C_4$ の和 $K_1+C_4$ | 隣接行列のスペクトルはどちらも $2,0,0,0,-2$ で、連結かどうかを区別できない |
| 無向グラフを有向グラフに替える（$L=D_{\mathrm{out}}-A$） | 有向 3 閉路 $1\to2\to3\to1$ | 固有値が $0,\ \frac32\pm\frac{\sqrt3}2\sqrt{-1}$ で実数でなく、2 次形式による議論が使えない |
| 重みが正であること | 2 頂点を重み $-1$ の辺で結ぶ | $L=\begin{pmatrix}-1&1\\1&-1\end{pmatrix}$ の固有値が $-2,0$ で、半正定値でない |
| thm-lap-vertex-connectivity の「完全グラフでない」 | 完全グラフ $K_n$（$n\ge2$） | $a(K_n)=n>n-1=\kappa(K_n)$ |
各行で、どの条件が破れ、何が成り立たなくなるかを確かめる。
各行の確認を開く
1 行目：$K_3$ の $D+A$ は対角が $2$、非対角が $1$ の行列 $I+J$ で、固有値は $1+3=4$ と $1$（重複度 2）である。$D+A$ の 2 次形式は $\sum_e(x_{u(e)}+x_{w(e)})^2$ で、$0$ になるのは隣どうしで符号が反転する $x$ だから、$0$ の重複度は二部グラフである連結成分の個数になる（BH11 Proposition 1.3.9、pp. 7–8）。$K_3$ は二部グラフでないので $0$ をもたない。
2 行目：BH11 §1.3.7（p. 7）の例である。Laplacian スペクトルは $K_{1,4}$ が $0,1,1,1,5$、$K_1+C_4$ が $0,0,2,2,4$ で、$0$ の重複度 $1$ と $2$ が連結成分の個数を正しく与える。
3 行目：$L=I-P$（$P$ は巡回置換の行列）で、$P$ の固有値は 1 の 3 乗根 $\omega^k$ なので $L$ の固有値は $1-\omega^k$ である。$L$ は対称でない。
4 行目：$x=(1,-1)$ で $x^{\mathsf T}Lx=-4< 0$ である。
5 行目：ex-lap-complete により $a(K_n)=n$ であり、連結度(グラフ) の記事の命題により $\kappa(K_n)=n-1$ である。$K_n$ ではどの頂点を除いても連結なので、証明の $S$ がとれない。
注意を 2 つ挙げる。
- Laplacian スペクトルはグラフを決めない．同型でない 2 つのグラフが同じ Laplacian スペクトルをもつことがある。例えば、同じスペクトルをもつ同型でない正則グラフは、隣接行列 の固有値と $\mu_i=k-\lambda_i$ で対応するので、Laplacian スペクトルも等しい（BH11 §1.8、p. 14 の図 1.2 の 2 つの 4 正則グラフ）。
- 全域木の個数．Laplacian 行列から 1 行と 1 列を除いた行列式は全域木の個数に等しく、それは $\frac1n\mu_2\cdots\mu_n$ でもある。これは 行列木定理 で証明する。
関連項目
- 前提: グラフ, 隣接行列, 次数(グラフ), 連結グラフ, スペクトル定理
- 比較: 符号なしLaplacian, 接続行列, Laplace–de Rham作用素
- 直後に読む: 行列木定理, Perron–Frobeniusの定理
- 発展: 固有値の交錯定理, Cheegerの不等式(グラフ), エクスパンダーグラフ, 連結度(グラフ)
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
