グラフ理論 塩田教官 次の問題から 【 】 ≧ 平成 年度 学期試験問題 問以上を選択し解答せよ。 のとき頂点数 の完全グラフ を求めよ。 は正則であることを示せ。 の隣接行列を とする。 【】次のような連結単純グラフの例をひとつずつ挙げよ。 ハミルトン・グラフであってオイラー・グラフでない。 オイラー・グラフであってハミルトン・グラフでない。 【】 正二十面体グラフは 色で点彩色できることを示せ。 正二十面体グラフは 色では点彩色できないことを示せ。 【】次の重み付きグラフに対して、頂点 【】次の重み付きグラフ から頂点 へ至る最短路を求めよ。 に対して、頂点 を出発点とする郵便配達員問題を の全ての辺を少なくとも 回以上通り 解け。すなわち、 から出発して へ戻る歩道のうち、重みの総和が最小のものをひとつ求めよ。 立方体グラフ の頂点数 と辺数 を で表せ。 は三角形（長さ の閉路）を含まないことを示せ。 は平面的でないことを示せ。（テキストの定理等も使って良い。） 【】 【】有限単純グラフ は、その補グラフ と同型であるとき「自己補対である」 という。 自己補対な木を全て求めよ。 完全二部グラフ は自己補対でないことを示せ。 完全二部グラフ ≧ 【】グラフ き、頂点数 ≧ は自己補対でないことを示せ。 の小道が含む辺の本数を、その小道の長さと定める。 ≧ のと の完全グラフ の最長の閉じた小道の長さを を用いて表せ。 【】任意のカットセットが同じ本数の辺から成るが、木でも閉路でもないような 連結単純グラフの例をひとつ挙げよ。 【 】自分で考えてきた問題など。
© Copyright 2024 ExpyDoc
