平成 28 年度 情報数学 I 第 2 回レポート問題

平成 28 年度 情報数学 I 第 2 回レポート問題
次の問題 1~6 を解き、その解答を提出せよ。所属、学生証番号、名前をレポートの一番上に記入せよ。
提出方法:レポートを講義開始時に直接提出。
〆切り: 2016 年 7 月 27 日(水) 12:40 (講義開始時に回収します)
問題 1. 完全グラフ5 と完全 2 部グラフ(3,3)を描け。
問題 2. 次のグラフに関して、長さ 3 となる1 3経路をすべて記せ。また、それ以外に長さ 3 となる13
経路が存在しないことを隣接行列と経路の個数に関する定理を用いて示せ。
問題 3. 次のグラフにおいて互いに辺素な道の最大本数を答えよ。また、それが最大本数となる理由
について、具体的なカットと互いに辺素な道を例示して答えよ。
問題 4. 平面グラフに関する次の問題 4a~4c に答えよ。
問題 4a. 完全グラフ (1 ≤  ≤ 10)のうち、平面的グラフであるのはどれか全て答えよ。
問題 4b. 完全二部グラフ(, ) (1 ≤  ≤  ≤ 10)のうち、平面的グラフであるのはどれか全て答えよ。
問題 4c. 完全三部グラフ(, , ) (1 ≤  ≤  ≤  ≤ 10)のうち、平面的グラフであるのはどれか全て
答えよ。
1
問題 5. グラフに関する次の問題 5a~5d に答えよ。
問題 5a. 完全グラフ  の辺の数を答えよ。
問題 5b. 完全 3 部グラフ (, , ) の辺の数を答えよ。
問題 5c.  個の頂点から成る木グラフの辺の数を答えよ。
問題 5d. 正二十面体は正三角形 20 枚からなる多面体である。正二十面体の辺の数と頂点数を答えよ。
問題 6. 次のグラフについて、次の問題 6a~6d に答えよ。
問題 6a. の補グラフを描け。
問題 6b. オイラーグラフの定義を記せ。また、がオイラーグラフであるか否か理由をつけて答えよ。
問題 6c. ハミルトングラフの定義を記せ。また、がハミルトングラフであるか否か理由をつけて答え
よ。
問題 6d. 単純グラフのうち、最も少ない頂点数で、オイラーグラフでないハミルトングラフ、ハミルト
ングラフでないオイラーグラフの例を描け。
2