(問題文) 無向グラフの直径とは、グラフの2頂点間の距離の最大値のことである。 上記のグラフの直径を求めよ。 (答; 間違いを含むもの) グラフの形状から明らかに、2点間の距離の最大値は3である。 (より丁寧にかきなおした問題文) 無向グラフの2つの頂点間の距離とは、その2つの頂点をつなぐ道の うち長さ最小のものの長さである。ただし、2つの頂点をつなぐ道が 存在しないときは距離は無限大である。 無向グラフの直径とは、2つの頂点間の距離の最大値である。距離が 無限大である2頂点が存在するならば、グラフの直径は無限大である。 上記のグラフの直径を求めよ。 (正しい答) 頂点2 から頂点4 への道は存在しない。このような場合、頂点2と頂点4の 距離は(0ではなく) 無限大(∞)と考える。よって、このグラフの直径(距離 の最大値)も∞となる。
講義資料は 共通ページにあります。
以下の予定は、授業の進捗状況その他により、多少変更することが あります。 演習があるときは、原則として、演習を3限に実施し、講義を 4限に実施します。
講義中に使う例題です。
ここに置いてある演習問題(全部で6回出題する予定)を解き、 レポートの形にして、授業の際に提出してください。 この際、A4サイズの紙に、 氏名、学籍番号を、1枚目上部に明記して、提出してください。 2枚以上になるときは、ホッチキス等でしっかり留めてください。 (留めていない時は、必ず、全ての紙に 氏名、学籍番号を書いてください。)
参考までに、過去の試験問題はこちら (学内からのみアクセス可能、 2003年度期末試験 、 2003年度期末試験の解答 、 2004年度中間試験 、 2004年度期末試験 , 2004年度期末試験の解答 2005年度のページ(下の方に、中間試験と期末試験へのリンクあり) , 2006年度期末試験 問1-2 , 2006年度期末試験 問1-2の解答 , 2006年度期末試験 問3-4 , 2006年度期末試験 問3-4の解答 ， 2007年度 期末試験の問題 , 2007年度 期末試験の解答概要と成績評価, 2008年度 期末試験問題, 2008年度 期末試験の解答概要、 2009年度 期末試験問題、 2009年度 期末試験の解答概要 ) です。ただし、過去の授業では、記号の使い方や試験範囲が若干異なることが あります。