GraphTheory/グラフ理論入門/演習問題 - tmura's note

GraphTheory > グラフ理論入門 > 演習問題

第2章

2.9

は単純グラフであり、２個以上の点があるとする。には同じ次数の点が２個以上あることを証明せよ。

$G$ には同じ次数の点が１つもないと仮定し、背理法で証明する。
$G$ は $N$ 個の点を持つとする。ただし、 $(N \geq 2)$ 。
$G$ における次数の最大値は $N-1$ である。
従って、仮定より、全ての点は異なる次数を持つため、 $G$ の次数列は $(N-1,N-2,\dots,0)$ になる。
しかし、次数 $N-1$ の点は、他の全ての点と繋がっていることを意味しており、次数 $0$ の点があることと矛盾する。
従って、仮定は間違っており、 $G$ には同じ次数の点が２個以上ある。

演習5

5.3

定理5.1の逆、すなわち、グラフのすべての閉路が偶数長ならばは二部グラフであることを証明せよ。

$G$ の任意の異なる二点 $v_1,v_2$ の間に偶数長の道 $v_1 \rightarrow \cdots \rightarrow v_2$ があるなら、 $v_1$ と $v_2$ を直接結ぶ辺はない。
なぜなら、そのような辺があると、奇数長の閉路 $v_1 \rightarrow \cdots \rightarrow v_2 \rightarrow v_1$ が存在し、仮定に反するからである。
いま、 $G$ の適当な点を選び、その点から偶数長の道で到達できる点を白色、奇数長の点で到達できる点を黒色で塗る。
上述の性質により、任意の点について、その点と同色の点を直接結ぶ辺はないことが分かる。
従って、 $G$ は二部グラフである。

5.4

単純グラフとその補グラフの両方とも非連結であるということはないことを証明せよ。

単純グラフ $G$ は非連結であり、その補グラフを $\bar{G}$ とする。

まず、異なる二点 $v_i,v_j \in G$ の間に道がない場合、すなわち、 $v_i$ と $v_j$ が $G$ の異なる成分に属する場合、 $v_i$ と $v_j$ を直接つなぐ辺は無いので、 $\bar{G}$ においては $v_i$ と $v_j$ は直接つなぐ辺を持つ。

次に、異なる二点 $v_i,v_j \in G$ の間に道がある場合、すなわち、 $v_i$ と $v_j$ が $G$ の同じ成分に属する場合、 $\bar{G}$ においても $v_i$ と $v_j$ の間に必ず道が存在する。
なぜなら、 $v_r \in G$ を $v_i,v_j$ とは異なる成分に属する任意の点として、前述の結論により、 $v_i$ と $v_r$ およびは $v_j$ と $v_r$ は $\bar{G}$ において直接接続されるため、道 $v_i \rightarrow v_r \rightarrow v_j$ が存在するからである。

以上より、任意の異なる二点は $\bar{G}$ において直接つながるか、または道を持つので、 $\bar{G}$ は必ず連結である。

5.6

(i) 連結グラフGの最小次数がならば、であることを示せ。

最小次数を持つ点 $v$ に隣接する $k$ 個の点を全て除去すれば、 $v$ は孤立点となり、 $G$ は非連結となるので、 $\kappa(G) \leq k$ は明らか。

(ii) 最小次数がであり、かつとなるグラフGを1つ作れ。

例えば以下のグラフ。ブリッジを作れば、グラフは簡単に切れる。

5.7

グラフが2-連結であるための必要十分条件は、任意の２点が同じ閉路に含まれることである。このことを証明せよ。

まず、 $\Leftarrow$ 方向から証明する。
グラフ $G$ の任意の２点は同じ閉路に含まれるとする。
どの閉路についても、閉路上のどの１点を除去しても、他の点は互いに連結したままである。
従って、 $G$ のどの１点を除去しても $G$ は連結を保ち、 $\kappa(G) \geq 2$ となる。

次に $\Rightarrow$ 向きを証明する。
グラフ $G$ は2-連結であるとする。
$G$ 上の任意の2点 $v_1,v_2$ について、まず、 $v_1,v_2$ が直接繋がっている場合を考える。
いま、第3の点 $v_3$ を適当に選ぶ。
$G$ は2-連結だから、 $v_1$ を除去しても $v_2$ と $v_3$ の間に道はあるはずで、その道は $v_1$ を含まない。
同じく、 $G$ から $v_2$ を除去しても $v_1$ と $v_3$ の間に道はあるはずで、その道は $v_2$ を含まない。
従って、 $v_1,v_2,v_3$ を通る閉路を作ることができ、 $v_1$ と $v_2$ はその閉路に含まれる。
次に、 $v_1,v_2$ が直接繋がっていない場合を考える。
その場合、 $v_1$ と $v_2$ の間には、共通点を全く含まない2つの道があるはずだ。
なぜなら、1つしか道が無いならば、その道の上のどの1点を除去しても $v_1$ と $v_2$ が断絶するし、
2つの道があっても、共通点を含む場合は、その共通点を除去することで $v_1$ と $v_2$ が断絶するからである。
共通点を含まない2つの道があるならば、その2つの道から $v_1$ と $v_2$ を含む閉路を作ることができる。
以上より、 $G$ が2-連結であれば、任意の二点は同じ閉路に含まれることが証明できた。

2-辺連結グラフに関して対応する命題を書け。

グラフが2-辺連結であるための必要十分条件は、任意の２辺が同じ閉路に含まれることである。
線グラフに変換して考えれば、この対応は自明である。

5.8

連結グラフの点集合はであり、本の辺と個の三角形があるとする。

(i) の隣接行列をとしたとき、行列の要素はと間の長さ2の歩道の個数に等しいことを証明せよ。

$A^2$ の $ij$ 要素を $a^{(2)}_{ij}$ とすると、
$a^{(2)}_{ij} = \sum a_{ik}a_{kj}$
であるが、 $a_{ik}a_{kj}$ は歩道 $i \righarrow k \righarrow j$ の数を表す。
ここで、多重辺やループがあってもかまわない。
従って、 $a^{(2)}_{ij}$ は、 $i$ から $j$ への長さ2の全ての歩道の数である。

(ii) =行列の対角要素の総和であることを示せ。

行列 $A^2$ の対角要素の総和は、 $\sum_{i} a^{(2)}_{ii}$ で表される。
$a^{(2)}_{ii}$ は、点 $i$ から点 $i$ へ戻る長さ2の全ての歩道の数の和であり、多重辺はないとすると、
点 $v_i$ から出る辺の総数に一致する。
全ての $i$ について和を取ると、各辺が２回ずつカウントされるから、
$\sum_{i} a^{(2)}_{ii}$ は $G$ の全ての辺の数のちょうど2倍となる。

(iii) と間の長さ3の歩道の個数の場合はどうか。また=行列の対角要素の総和であることを示せ。

$A^3$ の $ij$ 要素は以下の式に展開される。
$a^{(3)}_{ij} = \sum_{m} a^{(2)}_{im} a_{mj} = \sum_{m}(\sum_{k} a_{ik}a_{km})a_{mj} = \sum_{k,m} a_{ik}a_{km}a_{mj}$
これは、 $v_i \rightarrow v_k \rightarrow v_m \rightarrow v_j$ で表される歩道の数について、可能な全ての $k,m$ について数え上げており、 $v_i$ と $v_j$ 間の長さ3の歩道の個数を示している。

$a^{(3)}_{ii}$ は、 $v_i$ から $v_i$ へ戻る長さ3の歩道の数であり、
点 $v_i$ を一点として持つ三角形を時計回りに進む道と反時計回りに進む道を１つずつ含む。
全ての点 $i$ について数え上げると、1つの三角形を3回ずつカウントすることになる。
従って、 $\sum_{i} a^{(3)}_{ii}$ は、 $G$ が含む三角形の総数の6倍となる。

5.9

連結グラフにおいて、からへの距離はからへの最短路の長さである。
(i) ならばなる点が存在することを示せ。

$v$ から $w$ への最短路を1つ選び、 $P_{v,w}$ とする。
$d(v,w) \geq 2$ であるから、 $P_{v,w}$ の上には $v$ でも $w$ でもない点 $z$ が存在する。
$P_{v,w}$ の部分路 $P_{v,z}$ も、 $v$ から $z$ までの最短路でなければならない。
もし、より短い道 $P'_{v,z}$ が存在すると、 $P'_{v,z}$ と $P_{z,w}$ を組み合わせた道は $P_{v,w}$ より短くなり、
$P_{v,w}$ が最短路であるという前提に反するからである。
同様にして、 $P_{z,w}$ も $z$ から $w$ までの最短路である。
従って、 $P_{v,z}$ の長さが $d(v,z)$ を与え、 $P_{z,w}$ の長さが $d(z,w)$ を与える。
$P_{v,z}$ の長さと $P_{z,w}$ の長さの和は $P_{v,w}$ の長さであり、前提より $d(v,w)$ を与える。
以上より、 $d(v,z)+ d(z,w) = d(v,w)$ が導かれる。

5.10

の極値定理: は個の点をもつ単純グラフで、三角形はないとする。の辺は本以下であることをの帰納法で証明せよ。また、この上界を実現するグラフを１つつくれ。

まず、 $k=1$ のとき、辺は高々１本であり、 $k^2$ 本以下であることは自明である。
次に、点数が $2k$ 個のときは辺数が $k^2$ 以下であるとして、点数が $2(k+1)$ 個の場合を考える。
つまり、 $2k$ 個の点からなるグラフ $G$ に、新しく点を2つ（A,Bとする）追加する場合を考える。
大きく、以下の2通りに分けることができる。
(i) AとBを辺で結ぶ場合
(ii) AとBを辺で結ばない場合

(i)の場合、元々あった $2k$ 個の各々の点から、AまたはBのどちらか一方には必ず辺を引けることを説明する。
元々ある $2k$ 個の点のうち、任意の3点を選ぶとする。
このとき、それら3点の間には全く辺が無いか、1つだけ辺があるか、2つの辺があるかのいずれかである。
$G$ に三角形はない前提なので、3つの辺があることはない。
全く辺がない場合は、3点のそれぞれは、A,Bのどちらに繋いでもよい（三角形は生じない）。
辺が1つの場合、その辺で繋がっている2点は、一方をA、他方をBに繋げばよい。残りの1点は、Aに繋いでもBに繋いでもよい。
辺が2つの場合、2つの辺を持つ点が1つあるはずなので、その点をAに繋ぎ、残りの2点はBに繋ぐ。そうすれば三角形は生じない。
ところで、元々ある $2k$ 個の点のいずれについても、A,Bの両方と繋ぐことはできない。
なぜなら、いまAとBは辺で繋がれているから、もう一点からA,B両方に繋ぐと三角形ができてしまうからである。
従って、点A,Bの追加に伴って増やすことのできる辺の数は、高々 $2k+1$ 本であることが分かる。
$2k$ は、元々ある $2k$ 個の各点からAまたはBに引かれる辺であり、 $+1$ はAとBを繋ぐ辺である。
つまり、 $2(k+1)$ 個の点に対して、 $G$ の辺数は $k^2 + 2k + 1 = (k+1)^2$ 本以下である。

次に(ii)の場合を考える。
いま、元々ある $2k$ 個の点の集合を $S$ とする。
もし、 $S$ の点が全て孤立点であるとしたら、それらの各々の点を、新しく追加した2点 $A,B$ と辺で繋ぐことができ、合計4k本の辺を追加することができる。この場合、 $G$ の辺の合計数も $4k$ である。
この状態から、 $S$ の点と $A,B$ との接続辺をなるべく減らさずに、 $S$ の点の間に辺を増やすには、どうすればよいだろうか?
その方法は、 $S$ から1点( $P$ とする)を選び、 $P$ から $A,B$ への接続辺を切ることである。それにより、 $P$ は、 $S$ の $P$ 以外の全ての点と辺で繋ぐことができる（そうしても三角形は生じない）。つまり、 $PA,PB$ の2辺のみを犠牲にして、 $S$ の点の間に多くの辺を追加することができる。
さらに、 $S$ から別の1点 $Q$ を選び、 $Q$ から $A,B$ への接続辺を切り、同様に $S$ の点の間に辺を追加できる。ただし、 $P$ と $Q$ の接続は切る必要がある。そうしないと、P,Qおよび他の1点の間で三角形ができてしまうからである。
この操作を $k$ 回繰り返すと、 $S$ から $k$ 個の点が選ばれ、それぞれが、残りの $k$ 個の点と辺で繋がっている状態が得られる。このとき、 $S$ の点の間の辺の総数は $k^2$ であり、仮定より、 $S$ の点の間の辺数はこれ以上増やすことができないので、 $G$ の辺数も最大となる。*1
このとき、 $S$ の点とA,Bを繋ぐ辺の総数は $2k$ 本であるから、 $G$ の辺の総数は $k^2+2k$ 本となり、 $(k+1)^2$ 以下である。
従って、(ii)の場合も、点数が $2k$ 個のときに辺数が $k^2$ 以下であるならば、点数が $2(k+1)$ 個の場合には辺数が $(k+1)^2$ 以下となる。

以上、数学的帰納法により、全ての $k \geq 1$ において $G$ の辺は $k^2$ 本以下であることが証明できた。

5.11

辺 $e$ は、点 $P$ と点 $Q$ を繋いでいるとしよう。
$e$ を含む閉路が2つあるということは、 $P$ から $Q$ への異なる道が2つあることを意味する。
片方の道を $P \rightarrow path1 \rightarrow Q$ 、他方の道を逆から辿って $Q \rightarrow path1 \rightarrow P$ とすると、 $P \rightarrow path1 \rightarrow Q \rightarrow path2 \rightarrow P$ となる閉じた歩道が存在する。
この閉じた歩道は、重複辺やループを含んでいるかもしれないが、それらを取り除いて閉路を作ることができる。

「演習問題」をウィキ内検索

最終更新：2012年03月06日 19:37

添付ファイル

Training_5.6.ii.png

*1 これがGの辺数が最大の状態になっていることの証明になっているか? 直感的に正しそうな気はするが、証明というには少し弱い気がする...

tmura's note

メニュー

リンク

他のサービス

更新履歴