Web Analytics Made Easy - StatCounter

工業大学生ももやまのうさぎ塾

うさぎでもわかるをモットーに大学レベルの数学・情報科目をわかりやすく解説! 数式が読み込まれない場合は1回再読み込みしてみてください。

離散数学2・グラフ理論 総復習テスト(本番レベル模試)

こんにちは、ももやまです!

今回は「うさぎでもわかる離散数学」のグラフ理論の総復習として、行基本変形サークルさんの「離散数学2本番レベル模試」の解説記事を作成しました!!

復習にぜひご利用ください!!

 

1.グラフの基礎1

グラフ  G の点集合  V,  E をそれぞれ\[
V = \{ a,b,c,d,e,f \} \\
E = \{ (a,c), (a,d), (b,c), (c,e), (d,e) \}
\]とする。このとき、次の問いに答えなさい。(配点 15)

 

(1) Gを描画しなさい。
(2) Gの点の数、辺の数を答えなさい。
(3) Gの連結成分数を答えなさい。
(4) Gの最大次数、最小次数を答えなさい。
(5) Gのカット点、橋辺をすべて答えなさい。

 

★解答・解説★

(1) [3点]

頂点集合  V は、グラフに点が何個あるか、辺集合  E は、グラフの辺がどこにあるのかを表しています。

今回の場合、 V より、a, b, c, d, e, f の6つの点があることがわかり、 E より a-c, a-d, b-c, c-e, d-e 間に辺があることがわかります。よって描画すると

f:id:momoyama1192:20200215133726g:plain

のようなグラフになります。

(紫色の数字は各頂点の次数を表します。(3)で使うので書いています。)

 

(2) [1点×2]

頂点数:6
辺数:5

書いたグラフから数えてもいいですが、書いたグラフが間違っていたら悲惨なことになるため、 V の要素数(辺数)と  E の要素数(辺数)を数えることをおすすめします。

 

(3) [2点]

連結成分数:2

「グラフGは何個の塊で出来ている?」という問題。

孤立点を忘れないでください…。

 

(4) [2点×2]

最大次数:3
最小次数:0

最大次数は、グラフの中で最も次数が多い点の次数、最初次数はグラフの中で最も次数が小さい点の次数を表します。

孤立点の最小次数0を忘れないようにしましょう。

 

(5) [2点×2]

カット点:c
橋辺:(b,c)

 

カット点:削除すると連結成分数が増加する点
橋辺:削除すると連結成分数が増える辺

のことです。

 

★コメント・復習記事紹介★

グラフ理論の基礎の復習でした。ここはぜひ満点通過してほしいところです。

この大問の復習記事は下の2つとなっているので、自信ないなと思った人はぜひお読みください。

グラフ理論の基礎1グラフ理論の基礎3

 

2.グラフの基礎2

つぎの6つのグラフA~Fのうち、(1)~(5)の記述に該当するものをすべて選びなさい。(配点 15)

f:id:momoyama1192:20200215141236g:plain

(1) 木
(2) 2次の正則グラフ
(3) 2部グラフ
(4) 彩色数が3のグラフ
(5) 互いに同型なグラフの組

 

★解答・解説★

まず、A~Fのグラフの辺数、点数、彩色数、各点における次数を求めておきます。

f:id:momoyama1192:20200215133723g:plain

では、1問ずつ解いていきましょう。

(1) [3点]

木:F

木であれば、「(辺数)=(頂点数)-1」が成立します。よって答えはFとなります。

 

(2) [3点]

2次の正則グラフ:A, B, C, D

正則グラフは、すべての頂点において次数が等しいグラフを表します。

今回は、2次の正則グラフなので、すべての頂点の次数が2のグラフを探せばOKです。

 

(3) [3点]

2部グラフ:A, D, E, F

2部グラフは、彩色数が2となるグラフ(閉路を持たないグラフでもOK)を表します。

 

(4) [3点]

彩色数3のグラフ:B, C

彩色数は、頂点の塗り分け(隣り合った点が異なる色になるようにする)に必要な色の最低数を表します。

 

(5) [3点]

互いに同型な組:B, C

同型であれば、少なくとも「頂点数、点の数、各点における次数(次数列)」が等しくないといけません。そのようなグラフはB, Cしかないため、自動的に答えはB, Cとなります。

(ただし頂点数、点数、各点における次数が等しければ必ず同型とは限らないので注意!)

 

★コメント・復習記事紹介★

こちらもグラフ理論の基礎についての問題でした。

しかし、すべて選ぶ必要があるので大問1よりは難易度が少し高かったかと思います。

 

3.グラフ理論の定義チェック

つぎの(a)~(d)の空欄に適切な数式を補い、文章を完成させなさい。
(配点  8)

(a) 完全2部グラフ  K_{r,s} の点の個数は( 1 )個、辺の個数は( 2 )本である。

(b)  n 点からなる道の彩色数は( 3 )、彩色指数は( 4 )である。
ただし  n \geqq 3 とする。

(c) 点数  n のグラフ  G が木であるとき、 G の辺の本数は( 5 )本である。

(d) グラフ  G が完全グラフ  K_n であるとする。このとき、 G の連結度  \kappa (G) は( 6 )、 G の辺連結度  \lambda (G) は( 7 )となる。 

★解答・解説★

(a)

(1):r+s (2):rs [1点×2]

完全2部グラフ  K_{r,s} は、1つのグループAに属する  r 個の点と、もう1つのグループBに属する  s 個の点同士にすべて辺が存在するようなグラフを指します。

そのため、点の個数は r+s 個となります。

 

また、 r 個のそれぞれに対し、 s 通りの辺が存在するため、辺の数は合計 rs 個となります。

 

(b)

(3):2 (4):2 [1点×2]

 

道とは、図のような同じ頂点を2回以上通らないようなものを表します。

道であれば、当然分岐する点などもないため、下のように2色で頂点、辺を塗り分けることができます。

f:id:momoyama1192:20200215133739g:plainf:id:momoyama1192:20200215133743g:plain

 

(c)

(5):n-1 [2点]

これは定理なので覚えておきましょう。

 

(d)

(6):n-1 (7):n-1 [1点×2]

連結度、辺連結度とは、連結なグラフを非連結にするために消す必要のある点、辺の際小数を表します。

n点からなる完全グラフの場合、どの頂点同士も辺がつながっているため、それぞれの頂点に n-1 個の辺がつながっています。

 

完全グラフを非連結にする場合、頂点であれば自分以外のすべての点を消しても連結となるので連結度は n-1となります。

辺の場合であれば、n-1本すべての辺を取り除かない限り連結なままなので辺連結度も n-1 となります。

 

4.平面グラフ

つぎのグラフは平面グラフかどうかを答えなさい。理由も答えること。
(配点 10)

※平面グラフは平面的グラフのことを指しています

f:id:momoyama1192:20200215133730g:plain

★解答・解説★

答え:No

理由は2パターンあります。

 

(1) クラトフスキーの定理を使う

グラフの紫色の部分が完全グラフ  K_5 となっているため、平面グラフとは言えないから。

f:id:momoyama1192:20200215133734g:plain

 

(2) 頂点数と辺数で示す

グラフの点の数を n 、辺の数をmとする。

 

ここで、題意のグラフが平面グラフと仮定すると、三角形となる部分が存在しないため、\[
m \leqq 2n - 4
\]が成立する。しかし、このグラフの頂点数  n  = 6、辺数  m = 11 を代入すると、\[
11 \leqq 2 \cdot 6 - 4 = 8 
\]となり、矛盾する。

よって平面グラフとは言えない。

 

5.最短経路導出(ダイクストラ)

つぎのグラフに対し、 s を始点としてダイクストラのアルゴリズムを適応して得られる最短路木と各点までの距離を求めなさい。なお、距離は点の〇の中にそれぞれ記すこと。(配点 10)

f:id:momoyama1192:20200215141240g:plain

 

★解答★

f:id:momoyama1192:20200215162715g:plain

 

アルゴリズムを適用させていく様子をアニメーションで出しているので参考までに。

f:id:momoyama1192:20200215133655g:plain 

6.正誤問題

つぎの(a)~(e)のうち、正しい記述をすべて選びなさい。(配点 10)

(a) 任意のグラフの各頂点の次数の和は偶数である
(b) あるグラフとその補グラフが同型なグラフが存在する。
(c) 回路と閉路をちょうど1つずつ含むグラフが存在する。
(d) オイラーグラフでかつハミルトングラフであるようなグラフは存在しない。
(e) あるグラフが完全グラフであることは、そのグラフが正則グラフであることの必要条件であるが十分条件ではない。

★解答・解説★

正解:(a), (b), (c)
※1ミス -3点(正解でない選択肢を選ぶ or 正解の選択肢を選んでいないもの1つにつき1ミス)

 

(a):1つ辺を足すと、次数の和は必ず2つずつ増えるので辺の数にかかわらず次数の和は偶数となる。よって正しい。(握手定理)

(b):例えば下のグラフは、元のグラフと補グラフが同型になる。よって正しい。

 

f:id:momoyama1192:20200215162723g:plain

(c):例えば下のグラフが回路、閉路を1つずつもつ。よって正しい。

f:id:momoyama1192:20200215162727g:plain

(d):下のグラフはオイラーグラフでもハミルトングラフである。よって誤り。

 

f:id:momoyama1192:20200215162727g:plain

(e):あるグラフが完全グラフであれば必ず正則グラフとなるが、正則グラフは必ずしも完全グラフになるとは限らない。よって十分条件であるが必要条件ではない。(誤り)

 

7.最大フロー

つぎのグラフの最大フローを記しなさい。

また、このグラフの最小カット容量を求めなさい。(配点 10)

f:id:momoyama1192:20200215141245g:plain

★解答・解説★

最大フロー↓ [6点]

f:id:momoyama1192:20200215162719g:plain

最小カットの容量:6 [4点]

 

何も追加してない状態の残余ネットワークは下のようになります。

ここから、スタート点(一番左側の点)からゴール点(一番右側の点)まで流せなくなるまで流していきます。

f:id:momoyama1192:20200215133747g:plain

 まず、4流します。残余ネットワークも変化するのを忘れずに。

f:id:momoyama1192:20200215133752g:plain

さらに1流します。

f:id:momoyama1192:20200215133757g:plain

 実はまだ1流せるので忘れずに流しましょう。

f:id:momoyama1192:20200215133801g:plain

ここで残余ネットワークを見てみると、スタート点からゴール点まで流せる点がないことがわかりますね。

よってこの状態が最大フロー(6流した状態)となることがわかります。

 

また、最小カットの容量は最大フローにおける流した数(今回の場合は6)と一致するので最小カットの容量は6となります。

 

なお、最小カット  S は下のようになるので参考までに。

f:id:momoyama1192:20200215133806g:plain

 

8.応用問題1

6つの点を2色の辺で結ぶグラフを考える。このとき、以下の問いに答えなさい。(配点 10)

(1) 6つの点のうち、1つに注目する。このとき、他の5つの点と結ばれている辺のうち、常に最大何本以上が同じ色であるといえるか。

(2) 6人いると互いに知り合いである3人組か互いに知らない3人組が必ず存在する。これを示しなさい。

★解答・解説★

(1) 3本以上 [4点]

6つの点を結ぶ場合、自分以外の5つの点と辺をつなげるので、5本の辺を赤・青の2色でわけることになる。

 

ここで、5つの辺を2色(赤と青とします)で塗り分けるパターンとしては、(赤5本・青0本)、(赤4本・青1本)、(赤3本・青2本)、(赤2本・青3本)、(赤1本・青4本)、(赤0本・青5本)の6パターンで塗り分ける方法がある。

よって、少なくとも3本以上が同じ色となる。

 

(2) [6点]

ここで、知り合いである組を青色の辺、知り合いでない組を赤色の辺で表すこととする。

すると、(1)より、5つの結ばれている辺のうち3つ以上は同じ色となる。

 

このとき、知り合いの3人組ができることはグラフ内に青色の三角形が存在すること、知り合いではない3人組ができることはグラフ内に赤色の三角形が存在することと同値である。

 

ここで、ある人(Aさんとします)はB, C, Dさんの3人と知り合いとする。

f:id:momoyama1192:20200215162732g:plain

このとき、つぎの(1)~(4)の場合を考えられる。

(1) BさんとCさんが知り合いの場合

f:id:momoyama1192:20200215162736g:plain

A, B, Cで三角形ができるので題意を満たす。

 

(2) BさんとDさんが知り合いの場合

f:id:momoyama1192:20200215162745g:plain

A, B, Dで三角形ができるので題意を満たす。

 

(3) CさんとDさんが知り合いの場合

f:id:momoyama1192:20200215162740g:plain

A, C, Dで三角形ができるので題意を満たす。

 

(4) B, C, Dさんが互いに誰も知り合いでない場合

f:id:momoyama1192:20200215162749g:plain

B, C, Dで赤色の三角形ができるので題意を満たす。

 

よって、(1)~(4)すべての場合において題意を満たす。

また、知り合いでない人が3人で知り合いの場合が2人の場合は、上の部分の青色の辺を赤色に、赤色の辺を青色にすれば題意を満たす。

 

なお、この議論を応用すると完全グラフ  K_6 を2色(赤・青)で塗り分けた際に、どのように塗り分けても必ず同色  K_3 の一部が含まれることを示すことができます。 

9.応用問題2

一般工業大学生のA男は何を血迷ったのか大学メンバーで合コンを企画した。参加者は次の通りである。

[男性] A男、B助、C太、D也
[女性] E子、F香、G美、パジュラ・H・モジュラ

また、事前アンケートで異性がアリかナシかの調査を行っている。調査結果は表のとおりである。例えば、A男とF香はお互いにアリだと思っている(〇)が、A男とG美はどちらかもしくは双方がなし(×)と思っている。このとき、次の問いに答えなさい。(配点 12)

(1) 参加者を点、お互いにアリだと思っている人の組を辺として、この状態をグラフで書きなさい。

(2) この合コンではどう頑張ってもカップルが4組できない。その理由を説明しなさい。

(※ただし互いにアリだと思っているカップルしか付き合わないと仮定する)

★解答・解説★

(1) [6点]

下のような2部グラフで書くことができる。

f:id:momoyama1192:20200215133810g:plain

 

(2) [6点]

上のグラフの男性 A, B, C, D の点集合をM、女性 E, F, G, Hの点集合をWとする。

題意を示すためには、MからWへの完全マッチングがないことを示せばよい。

 

ここで、MからWへの完全マッチングがあると仮定する。

すると、ホールの定理より、どのような集合  S(ただし  S \subseteq M)でも  S \leqq N(S) が成立する。

しかし、 S = \{A,D\} とすると、 N(S) = \{F \} となってしまい、\[
2 = |S| > | N(S) | = 1
\]となってしまい、ホールの定理が成立しない。

f:id:momoyama1192:20200215133816g:plain

よって仮定は矛盾するため、完全マッチングが存在しないことが示された。

 

わかりやすく言うと、AくんとDくんの2人の中でカップルになりえる候補はFさん1人だけですよね。

なので、2人のうちどちらか1人は絶対にカップルになれません。なので完全マッチング(男性側全員がカップルを作ること)は無理~ってことをグラフ理論用語で示そうよ~って問題でした。

 

10.さいごに

今回はグラフ理論の総復習として、行基本変形サークルの「離散数学2 本番レベル模試」の解説記事を作成しました。

 

グラフ理論(離散数学)は、定義さえ知ってしまえばあとはパズル解ける問題が増えるのでぜひパズルを楽しみましょう!

離散数学(グラフ理論)のテストはパズル!!