グラフの定義

平面グラフ

グラフ彩色

Adrian Bondy, U.S.R. Murty著Graph Theoryの演習問題の解答を掲載する。

Graph Theory演習問題解答

#平面グラフの定義

$F(K_5,K_{3,3})$に含まれるグラフを平面グラフと呼ぶ。

# グラフの定義

まずはグラフを定義する。

有限集合$V$と$V$の部分集合の族$E$の対$G=(V,E)$をハイパーグラフと呼ぶ。

特に$E$が異なる$2$元からなる$V$の部分集合の族のとき、$G=(V,E)$を単純グラフと呼ぶ。

以下では単純グラフのことをグラフと呼ぶ。

グラフ$G=(V,E)$の集合$V$を頂点集合、集合$E$を辺集合と呼びそれぞれ$V(G)$, $E(G)$と書く。

$V(G)$の元を頂点、 $E(G)$の元を辺と呼ぶ。

$\set{u,v}\in E(G)$を単に$uv$あるいは$vu$と書く。

グラフ$G$の頂点の数をオーダー、辺の数をサイズと呼ぶ。

頂点$e=uv\in E(G)$のとき、$u$と$v$は隣接すると言い、$u$と$e$は接続すると言う。

グラフ$H$が$V(H)\subset V(G)$かつ$E(H)\subset E(G)$を満たすとき、$H$を$G$のサブグラフと呼ぶ。

$V(G)$をどのように二つの集合$X,Y$に分割してもある$x\in X,y\in Y$が存在して$xy\in E(G)$となるとき、$G$を連結グラフと呼ぶ。 

#代表的なグラフ

グラフ理論の議論をする際によく表れる代表的なグラフを定義する。

任意の頂点が隣接するグラフを完全グラフと呼び、オーダー$n$の完全グラフを$K_n$と書く。

隣り合う頂点のみが隣接するように一列に並べられるグラフをパスグラフと呼び、オーダー$n+1$のパスグラフを$P_n$と書く。

隣り合う頂点のみが隣接するように円周上に並べられるグラフをサイクルグラフと呼び、オーダー$n$のサイクルグラフを$C_n$と書く。

任意の頂点の次数が等しいグラフを正則グラフと呼ぶ。


グラフ

&&&exc
$G$から任意に$2$頂点を選ぶ選び方は$_nC_2$であることから明らか。等号成立は$G=K_n$のとき。
&&&

&&&exc 
a)明らか。
b)$r+s=n$なので、ある$k$が存在して$rs=\lt(\frac{n}{2}+k\rt)\lt(\frac{n}{2}-k\rt)$と書ける。
よって$m\leq rs=\lt(\frac{n}{2}+k\rt)\lt(\frac{n}{2}-k\rt)\leq\frac{n^2}{4}$。
c)等号成立は$k=0$のときなので$r=s=\frac{n}{2}$のとき。
&&&

&&&exc *
a)明らか。
b)明らか。
&&&

&&&exc
明らか。
&&&

&&&exc
$k=0$)$nK_1$
$k=1$)$nK_2$
$k=2$)各コンポーネントがサイクルグラフとなるグラフ。
&&&

&&&exc
a)各人の持つ友人は高々$n-1$人なので箱の巣原理から従う。
b)バタフライグラフ。
&&&

&&&exc
a)省略。
b)$v(Q_n)=2^n, e(Q_n)=n\cdot2^{n-1}$
c)各頂点$v=(a_1,\cdots,a_n)$に対して、$S_v=\sum_{i=1}^na_i$を考える。$X=\set{v: S_v\equiv0(\mathrm{mod}.2)}, Y=V\backslash V_2$と定めると$ Q_n=G[X,Y]$が成り立つ。
&&&

&&&exc
a)省略。
b)グラフ準同型$\varphi:Q_n\ra BL_n$を$\varphi\lt((a_1,\cdots,a_n)\rt)=\set{i:a_i\neq0}$と定めるとこれはグラフ同型を定める。よって$v(BL_n)=2^n, e(BL_n)=n\cdot2^{n-1}$。
c)$Q_n$と同型であることから明らか。
&&&

&&&exc *
a)$\sum_{v\in X}d(v)=m$, $\sum_{v\in Y}d(v)=m$より成り立つ。
b)$k|X|=\sum_{v\in X}d(v)=\sum_{v\in Y}d(v)=k|Y|$より成り立つ。 
&&&

&&&exc *
大きさが$a_i$の部集合に含まれる頂点$v$の次数は$d(v)\leq n-a_i$。
よって$2m=\sum_{v\in V}d(v)\leq \sum_{i=1}^ka_i(n-a_i)$。
&&&

&&&exc *
a)
b)
&&&

&&&exc
a)対偶を示す。$G$が非連結であるとすると、$V=X\cup Y$を満たす互いに素な集合$X$, $Y$で、$X$と$Y$の間に辺の存在しないものが存在する。
$n\geq2$, $1\leq x\leq n-1$のとき、$x^2-nx\leq1-n$が成り立つことに注意すると、$m\leq\ _{|X|}C_2+\ _{|Y|}C_2=\frac{1}{2}\set{|X|(|X|-1)+(n-|X|)(n-|X|-1)}\leq\ _{n-1}C_2$
b)$K_1+K_{n-1}$
&&&

&&&exc
a)対偶を示す。$G$が非連結であるとすると、$V=X\cup Y$を満たす互いに素な集合$X$, $Y$で、$X$と$Y$の間に辺の存在しないものが存在する。$|X|\leq\frac{n}{2}$として一般性を失わない。任意の$v\in X$に対して、$d(v)\leq\frac{n}{2}-1=\frac{1}{2}(n-2)$が成り立つ。
b)$2K_{\frac{n}{2}}$
&&&

&&&exc
$$\delta_{ij}=\left\{\begin{array}{cl}
1 & (v_iv_j\in E) \\
0 & (v_iv_j\not\in E)
\end{array}\right.$$
と定める。
$A^2$の対角成分は$a_{ii}=\sum_{j=1}^n\delta_{ij}=d(v_i)$である。
$$\mu_{ij}=\left\{\begin{array}{cl}
1 & (v_i\in e_j) \\
0 & (v_i\not\in e_j)
\end{array}\right.$$
と定める。
$MM^t$の対角成分は$m_{ii}=\sum_{j=1}^m\mu_{ij}=d(v_i)$である。
&&&

&&&exc
$G$のコンポーネントに番号を付ける。接続行列を$i_1$行目までコンポーネント$1$の頂点、$i_1+1$行目から$i_2$行目までコンポーネント$2$の頂点$\cdots$、となるように取る。$i_k$行目に$i_k+1$行目から$i_{k+1}-1$行目までを足すと各列の値は$0$となる。よって、$A$のランクは$n-1$以下かつ等号成立は$G$がコンポーネントを一つしか持たない、すなわち連結のとき。
&&&

&&&exc
a)次数列$\mathbb{d}$を持つグラフが存在するならば握手補題より$\sum_{i=1}^n d_i$は偶数。逆に、$\sum_{i=1}^n d_i$が偶数とする。$d_i$が偶数ならば$\frac{d_i}{2}$個のループを持ち、$d_i$が奇数ならば$\frac{d_i-1}{2}$個のループを持つグラフ$G$を考える。$\mathbb{d}$には奇数次数が偶数個含まれているので適当にペアを組ませる。ペア同士を辺で結ぶとこれは与えられた次数列を持つグラフとなる。
b)ある$0$を含まない次数列$\mathbb{d}$を持つグラフが存在すると仮定し、$\mathbb{d}$は$\sum_{i=1}^nd_i$が奇数であるか、$d_1>\sum_{i=2}^nd_i$を満たすとする。$\sum_{i=1}^nd_i$が奇数であるとすると握手補題と矛盾するので$d_1>\sum_{i=2}^nd_i$が成り立つ。次数$d_1$を持つ頂点を$v$とする。$v$と隣接する頂点$w$に対して$v$と$w$の間の辺の数を$k_w$とし、$k=\sum_{w\in N(v)}(k_w-1)$とおく。$d_1-k>\sum_{i=2}^nd_i-k\geq n-1$よりこれは矛盾。
逆に、列$\mathbb{d}$が$\mathbb{d}$は$\sum_{i=1}^nd_i$が偶数かつ$d_1\leq\sum_{i=2}^nd_i$を満たすとする。次数列$\mathbb{d}$を持つグラフが存在することを$|\mathbb{d}|$に関する帰納法で示す。$|\mathbb{d}|=1$のとき、$\mathbb{d}=(0)$よりこれは空グラフの次数列となる。$|\mathbb{d}|=n-1$のとき次数列$\mathbb{d}$を持つグラフが存在すると仮定する。$\mathbb{d}=(d_1,\cdots,d_n)$とする($d_n>0$)。列$\mathbb{d^\p}$を$\mathbb{d^\p}=(d_1-\min\set{d_n,d_1-d_2},d_2-1,\cdots,d_{d_n-(d_1-d_2)+1}-1,d_{d_n-(d_1-d_2)+2},\cdots,d_{n-1})$と定義すると、必要であれば$d_2$以降を並べ替えることで単調非増加列となる。$\sum_{i=1}^{n-1}d^\p_i=\sum_{i=1}^nd_i-2d_n$より$\sum_{i=1}^{n-1}d^\p_i$は偶数である。$d_n>d_1-d_2$のとき、
$$\begin{split}
d_1^\p&\leq\sum_{i=2}^nd_i+(d_1-d_2)\\
&=\sum_{i=2}^{n-1}d_i-\lt(d_n-(d_1-d_2)\rt)\\
&=\sum_{i=2}^{d_n-(d_1-d_2)+1}(d_i-1)+\sum_{d_n-(d_1-d_2)+2}^{n-1}d_i\\
&=\sum_{i=2}^{n-1}d_i^\p
\end{split}$$
が成り立つ。$d_n\leq d_1-d_2$のときも$d_1^\p\leq\sum_{i=2}^nd_i^\p$が成り立つので、帰納法の仮定から次数列$\mathbb{d^\p}$を持つグラフ$G$が存在する。$G$に対して頂点を一つ追加し、次数$d_1^\p$の頂点との間に$\min\set{d_n,d_1-d_2}$本の辺を追加し、$d_i-d_i^\p=1$を満たす頂点との間に$1$本づつ辺を追加する。以上の操作でできるグラフは次数列$\mathbb{d}$を持つグラフとなる。

&&&

&&&exc
a)$Gの次数列を\mathbb{d}=(d_1,\cdots,d_n)$とする。このとき、$\overline{G}$の次数列は$(n-1-d_n,\cdots,n-1-d_1)$
b)$G_1$, $G_2$を$G$の異なる連結成分とする。任意の$v_1\in V(G_1)$, $v_2\in V(G_2)$に対して$v_1v_2\in E(\overline{G})$が成り立つ。よって任意の$x,y\in V(G_1)$はある$z\in V(G_2)$を通るパスが存在する。よって$\overline{G}$は連結。逆は$G=K_1$が反例となる。
&&&

&&&exc (Erdős–Gallaiの定理)
a)$e(K_7)=21$なので次数和がこれより大きな次数列はグラフ的ではない。
b)$V_k=\set{v_1,\cdots,v_k}$とすると、$\sum_{i=1}^kd_i$は$G[V_k]$内の辺を二回づつ、$G[V_k]$から$G[V(G)\backslash V_k]$への辺を一回づつ数えている。$G[V_k]$のサイズは高々$_kC_2$で、任意の$v\in V(G[V(G)\backslash V_k])$から$G[V_k]$への辺の数は高々$\min\set{k,d_i}$である。以上より、$\sum_{i=1}^kd_i\leq2\ _kC_2+\sum_{i=k+1}^n\min\set{k,d_i}=k(k-1)+\sum_{i=k+1}^n\min\set{k,d_i}$
&&&

&&&exc (Havel-Hakimiの定理)
a)次数列$\mathbb{d}^\p$を持つグラフ$G$が存在すると仮定する。$G$に頂点$v$を追加し、$d_i-d_i^\p=1$となる次数を持つ頂点との間に辺を追加することで次数列$\mathbb{d}$を持つグラフが得られる。
逆に、次数列$\mathbb{d}$を持つグラフ$G$が存在すると仮定する。$v_i\in V(G)$に対して$d(v_i)=d_i$とする。グラフ$G$から2-switchを繰り返すことで$N(v_1)=\set{v_2,\cdots,v_{d_1+1}}$を満たすグラフに変形できることを示す。グラフ$G$が$N(v_1)=\set{v_2,\cdots,v_{d_1+1}}$を満たすグラフに変形できないグラフで$N(v_1)$内の頂点の添え字の総和が最小のグラフとする。ある$v_k\in N(v_1)$に対して$j<k$を満たす$v_j\not\in N(v_1)$が存在する。$j<k$なのである$v_l$が存在して$v_jv_l\in E(G)$かつ$v_kv_k\not\in E(G)$となる。$v_1v_k$, $v_jv_l$を$v_1v_j$, $v_kv_l$で取り換えるとこれは$G$の2-switchで、得られるグラフ$G^\p$は次数列$\mathbb{d}$を持つが$N_{G^\p}(v_1)$の添え字の総和は$N_G(v_1)$の添え字の総和より小さい。よってこれは矛盾。以上よりグラフ$G$から2-switchを繰り返すことで$N(v_1)=\set{v_2,\cdots,v_{d_1+1}}$を満たすグラフに変形できる。変形して得られたグラフは次数列$\mathbb{d}$を持ち、$G-{v_1}$は$\mathbb{d^\p}$を持つ。
b)与えられた$\mathbb{d}$に対して(a)の$\mathbb{d^\p}$を計算して非増加列になるように並べ替えることを繰り返す。次数列$\mathbb{d}$を持つグラフが存在するならば$\mathbb{d^{(|\mathbb{{d}}|-1)}}=(0,\cdots,0)$となる。$\mathbb{d^{(|\mathbb{{d}}|-1)}}=(0,\cdots,0)$とならない場合は$\mathbb{d}$はグラフ的ではない。$\mathbb{d^{(|\mathbb{{d}}|-1)}}=(0,\cdots,0)$となるとき、(a)の証明と同様の手順で$\mathbb{d^{(i)}}$から$\mathbb{d^{(i+1)}}$を復元することを繰り返すことで次数列$\mathbb{d}$を持つグラフが得られる。
&&&

&&&exc
距離がちょうど$1$である点対の数が最大になるように並べるには正三角形のタイルで埋め尽くすように並べれば良い。これを$n$頂点のグラフとして表す。互いに距離が$1$の頂点間を辺で結ぶとこれは平面グラフとなる。よって$m\leq 3n-6$が成り立ち、$S$の点対は$3n$個以下となる。
&&&

&&&exc

&&&

&&&exc

&&&

&&&exc

&&&

&&&exc

&&&

&&&exc

&&&


第1章第1節


$\newcommand{\cG}{\mathcal{G}}$

#グラフマイナーの定義

任意に$e=uv\in E(G)$を取る。グラフ$G$から$e$を取り除いて$u$と$v$を同一視し、これによって発生する多重辺を同一視して一つの辺とみなす操作を辺の縮約と言う。$G$から$e$を縮約したグラフを$G/e$と書く。

辺の縮約と部分グラフを取る操作を総称してマイナー操作と呼ぶ。グラフ$G$からマイナー操作のみでグラフ$H$に到達できるとき、グラフ$H$はグラフ$G$のマイナーであると言い、$H\leq G$と書く。

マイナー関係はグラフ全体に半順序を定める。

グラフの集合$\cG$がマイナーについて閉じているとは、任意の$G\in\cG$と$G$のマイナー$H$に対して$H\in\cG$となることである。

有限個のグラフ$X_1,\cdots,X_n$に対して、どのグラフもマイナーとして含まないグラフの全体を$F(X_1,\cdots,X_n)$と書き、$X_1,\cdots,X_n$を禁止マイナーと呼ぶ。

&&&thm
$\cG$がマイナーについて閉じていることと、ある有限個のグラフ$X_1,\cdots,X_n$が存在して$\cG=F(X_1,\cdots,X_n)$となることは同値。
&&&

グラフマイナー

&&&exc
a)明らか。
b)明らか。
&&&

&&&exc
ループを持つ頂点に隣接する頂点の次数に注目すれば同型ではないことが分かる。
&&&

&&&exc
明らか。
&&&

&&&exc
a)同型写像$\varphi$について、$\varphi(1)$の定め方は$6$通りなので、$6×3!×2!=72$より求める同型写像の個数は$72$個。
b)$72$個
&&&

&&&exc
省略。
&&&

&&&exc
省略。
&&&

&&&exc
グラフ準同型$\varphi:Q_n\ra BL_n$を$\varphi\lt((a_1,\cdots,a_n)\rt)=\set{i:a_i\neq0}$と定めるとこれはグラフ同型を定める。
&&&

&&&exc

&&&

&&&exc
明らか。
&&&

&&&exc
a)グラフ$P_n$について$d(v)=d(v^\p)=1$とする。$P_n$の自己同型は恒等写像と$\varphi(v)=v^\p$となる同型の二つ。よって$Aut(P_n)\cong S_2$である。また、グラフ$C_n$について、$\varphi_{k^+}$を$\varphi_{k^+}(0)=k$, $\varphi_{k^+}(1)=k+1(mod.n)$と定める。$\varphi_{k^-}$を$\varphi_{k^-}(0)=k$, $\varphi_{k^-}(1)=k-1(mod.n)$と定めると、$Aut(C_n)=\set{\varphi_{k^+}:0\leq k\leq n-1}\cup\set{\varphi_{k^-}:1\leq k\leq n-1}\cong D_n$である。
b)$m\neq n$のとき、$S_m\times S_n$であり、$m=n$のとき、$S_{2m}$である。
&&&

&&&exc
明らか。
&&&

&&&exc

&&&

&&&exc
a)(反射律)恒等写像を考えると$v\sim v$
(推移律)$u\sim v$, $v\sim w$のとき、$\varphi(u)=v$, $\psi(v)=w$を満たす自己同型$\varphi$, $\psi$が存在する。$\psi\circ\varphi$は自己同型で$\psi\circ\varphi(u)=w$なので$u\sim w$
(対称律)$u\sim v$のとき、$\varphi(u)=v$を満たす自己同型が存在する。$\varphi^{-1}$は自己同型で$\varphi^{-1}(v)=u$を満たすので$v\sim u$
b)省略。
&&&

&&&exc
a)省略。
b)ブルグラフの片側の角を伸ばしたグラフを考えればよい。
&&&

第1章第2節

&&&exc *
明らか。
&&&

&&&exc *
a)連結な場合を考えれば良い。$G$の次数$1$の頂点が$1$つ以下であるとすると、$2m=\sum_{i=1}^nd_i\geq2(n-1)+1=2n-1$が成り立つが、$G$はtreeなので$m=n-1$が成り立つ。よって$2(n-1)=2n-2\geq2n-1$となりこれは矛盾。
b)(a)の証明より明らか。等号成立はパスグラフのとき。
&&&

&&&exc
a)閉路を持たないならば$m\leq n-1<n$が成り立つことから明らか。
b)$P_n$
&&&

&&&exc
a)$\delta<2$ならば明らかなので、$\delta\geq2$とする。$P=v_1\cdots v_k$を$G$の最長道とする。$d(v_k)\geq\delta\geq2$なので$v_k$は$v_{k-1}$以外の近傍を$\delta-1$個以上持つ。$P$の最長性と$G$が単純であることからこれらの近傍はそれぞれ異なる$P$上の頂点と隣接するので$P$の長さは$\delta$以上である。よって$G$は長さ$\delta$の道を持つ。
b)$K_{k+1}$
&&&

&&&exc
a)
b)$K_{k+1}$
&&&

&&&exc

&&&

第2章第1節

&&&exc *
省略。
&&&

&&&exc *
グラフ$G$が平面的ならば$G$の平面描画を固定して細分の配置を考えれば$G$の細分は平面的である。任意の細分が平面的なグラフ$G$について、各辺をちょうど一度細分したグラフを考える。このグラフの平面描画から細分された頂点を辺で置き換えれば$G$の平面描画が得られる。
&&&

&&&exc *
省略。
&&&

&&&exc *
a)平面的グラフはマイナーについて閉じていることから明らか。
b)$K_5$が反例。
&&&

&&&exc *
$n=4$のとき$G=K_4$より正しい。ある$n>4$について$4\leq v(G)< n$を満たす任意の$G$が$K_4$の細分を含むと仮定する。$v(G)=n$のとき、次数が最小の頂点を$v$とする。$d(v)=0$または$d(v)\geq4$のとき、$\delta(G-v)\geq3$なので帰納法の仮定から$G-v$は$K_4$の細分を含む。よって$G$も$K_4$の細分を含む。$d(v)=2,3$のとき、$G^\p$を$G-v$に対して(必要であれば)$N(v)$から選んだ二頂点の間に辺を付け加えたグラフとする。$G^\p$は帰納法の仮定から$K_4$の細分を含み、$G^\p$の構成から$G$も$K_4$の細分を含む。$d(v)=1$のとき、帰納法の仮定から$G-v$は$K_4$の細分を含み、$G$が$K_4$の細分を含むことが従う。
&&&

&&&exc
省略。
&&&

&&&exc
グラフ$G$が$m$-bookに埋め込めることを示す。任意の頂点を背表紙に埋め込み、各辺を異なるページに埋め込むとこれは$G$の$m$-bookへの埋め込みである。有限の$m$に対して$m$-bookは$\mR^3$に埋め込めるので$G$は$\mR^3$に埋め込める。
&&&

&&&exc
a)明らか。
b)実際に$cr(G)=1$となる埋め込みを構成すれば良い。省略。
c)$cr(P_{10})=k$とすると、$k\leq2$は実際に描画することで分かる。$P_{10}$の平面描画において交差している部分の辺をひとつづつ取り除いた平面グラフ$G$を考える。$v(G)=10$、$e(G)=15-k$であり、$P_{10}$はgirth $5$なので$2(15-k)\geq2\cdot5+5(15-k)-5\cdot10$が成り立つ。これを解くと$k\geq\frac{5}{3}$なので、$k=2$である。
d)$cr(K_6)=k$とすると、$k\leq3$は実際に描画することで分かる。$K_6$の平面描画において交差している部分の辺をひとつづつ取り除いた平面グラフ$G$を考える。$v(G)=6$、$e(G)=15-k$なので、$2(15-k)\geq2\cdot3+3(15-k)-3\cdot6$が成り立つ。$k\geq3$なので、$k=3$である。
&&&

&&&exc

&&&

&&&exc
$G$を交差数が$cr(G)$と一致するように平面に埋め込む。$G$は辺推移的なので自己同型を用いて埋め込みを固定したまま頂点の添え字を入れ替えることで辺$e$が異なる辺と交差するようにできる。よって、$G$は交差極小。
&&&

&&&exc

&&&

&&&exc

&&&

第10章第1節

&&&exc
$G$の平面描画から交差する辺を取り除いたグラフ$G^\p$は平面グラフである。よって$m-cr(G)\leq 3n-6$が成り立つ。
&&&

&&&exc
a)$G$の平面描画の面の数を$f$とする。girth $k$より$2m\geq kf$が成り立つ。Eulerの公式を代入すると$2m\geq k(2-n+m)$なので、これを変形すると$m\leq\frac{k(n-2)}{k-2}$
b)Pertersen graphはgirth $5$なので(a)の式に代入すれば非平面的であることが分かる。
&&&

&&&exc

&&&

&&&exc
a)位数$11$以上のグラフ$G$が平面的であるとすると、$m\leq3n-6$を満たす。$e(\overline{G})=\frac{n(n-1)}{2}-m$であり、$\frac{n(n-1)}{2}-m-3n+6\geq\frac{1}{2}(n^2-13n+24)>0$なので$\overline{G}$は非平面的。
b)省略。($K_4$を二つ並べて間に辺を付け加えたグラフを考えれば良い。)
&&&

&&&exc
面の次数を$r$とすると、$2m=rf$であり、頂点の次数を$r^\p$とすると、$2m=r^\p n$である。これらをEulerの公式に代入すると、$n-\frac{r^\p n}{2}+\frac{r^\p n}{r}=2$が成り立つ。これを整理すると、$n=\frac{4r}{2r+2r^\p-rr^\p}$
&&&

第10章第3節

グラフ理論について基礎的な内容を解説する。

グラフ理論入門

概要

目次

グラフの定義

平面グラフ

グラフ彩色

Graph Theory演習問題解答