第 1 回レポート問題 解答 数学の世界 (担当: 新國) 2015 年 11 月 20 日 (金) 配付 問題. 図 1 のグラフ G1 , G2 , G3 について, 以下の問いに答えよ. G1 G2 G3 図 1: グラフ G1 , G2 , G3 (1) G1 , G2 , G3 のうち, Euler グラフであるものを全て挙げ, その Euler 回路を具 体的に図示せよ. また, Euler グラフでないものも全て挙げ, その理由を述べよ. (2) G1 , G2 , G3 のうち, 閉小径でない Euler 小径を持つものを全て挙げ, その Euler 小径を具体的に図示せよ. また, 閉小径でない Euler 小径を持たないものも全 て挙げ, その理由を述べよ. (3) G1 , G2 , G3 のうち, 2 部グラフであるものを全て挙げ, 実際に 2 部グラフであ ることを示せ. また, 2 部グラフでないものも全て挙げ, その理由を述べよ. (4) G1 , G2 , G3 のうち, このグラフが分ける平面上の領域を 2 色で塗り分けるこ とができるものを 1 つ挙げ, 実際に 2 色で塗り分けよ. ここで一般に「平面上 の領域を n 色で塗り分ける」とは, 辺で隣り合う 2 つの領域は異なる色となる ように全ての領域を n 色以下で彩色することを意味する. (5) G1 , G2 , G3 のうち, このグラフが分ける平面上の領域が 2 色では塗り分けら れないが, 3 色では塗り分けることができるものを 1 つ挙げ, 2 色では塗り分け られない理由を述べたうえで, 実際に 3 色で塗り分けよ. 以上 1 解答. G2 G1 G3 図 2: グラフ G1 , G2 , G3 (1) G3 は全ての頂点が偶点である. 従って講義における定理 1.8 から, G3 は Euler グラフであり, その Euler 回路は例えば図 3 の右図に示した通りである. 一方, G1 は奇点 (図 2 で赤丸で示された頂点) を持ち, また, G2 は全ての頂点が奇点である. 従って定理 1.8 から, G1 , G2 はともに Euler グラフでない. (2) G1 はちょうど 2 つの奇点を持つ. 従って講義における系 1.9 から, G1 は閉小径 でない Euler 小径を持ち, その Euler 小径は例えば図 3 の左図に示した通りである. 一方, G2 は奇点を 3 つ以上持ち, また G3 は奇点を持たない. 従って系 1.7 から, G2 , G3 はともに閉小径でない Euler 小径を持たない. G1 G3 図 3: G1 の Euler 小径, G3 の Euler 回路 (3) G2 の各頂点を, 図 4 の黒頂点と白頂点に分け, 黒頂点全体の集合を X とし, ま た白頂点全体の集合を Y とおく. このとき, X ∪ Y = V (G2 ) 及び X ∩ Y = ∅ が成 り立ち, 更に任意の 2 つの黒頂点及び任意の 2 つの白頂点は辺で結ばれない. 従っ 2 て G2 は 2 部グラフである. 一方, G1 , G3 はともに奇閉路を持つ (図 3 において青色 で示された閉路). 故に講義における補題 2.4 から, G1 , G3 は 2 部グラフでない. G2 図 4: G2 は 2 部グラフ (4) G3 の全ての頂点は偶点である. 従って講義における定理 1.8 から, G3 は Euler グラフである. 更に, G3 は平面上に辺の交差なく描かれた連結グラフである. 従っ て, 講義における定理 2.5 (2 色定理) から, G3 が分ける平面上の領域を 2 色で塗り 分けることができる. 実際に赤, 緑の 2 色で塗り分けると, 例えば図 5 の右図のよ うになる. (5) G1 が分ける平面上の領域は 3 色で塗り分けることができる. 実際に赤, 青, 緑 の 3 色で塗り分けると, 例えば図 5 の左図のようになる. 一方, G1 は奇点を持つの で, 講義における定理 1.8 から, G1 は Euler グラフでなく, 従って講義における定 理 2.5 から, G1 が分ける平面上の領域を 2 色で塗り分けることはできない. G1 G3 図 5: グラフ G1 , G3 がそれぞれ分ける平面上の領域の塗り分け 3
© Copyright 2024 ExpyDoc
