ゼミナールⅡ

年度	2008
科目名	ゼミナールⅡ
教員名	惠羅　博
授業概要	コンピュータ・サイエンスの発展に伴い、それを支援する目的で、あるいはその影響を受けるかたちで、この半世紀の間、数学の世界に多くの新しい領域が生まれ、現在も猛烈な勢いで発展しつつある。そのような領域の多くは、離散数学と呼ばれる分野に集中している。このゼミナールでは、離散数学の中でも重要なグラフ理論の初歩的な概念と応用例を学ぶ。授業の進め方は輪講形式で、テキストの講読と演習問題を行う。受講者の自発的な探究心を育てるとともに、プレゼンテーションの訓練も目的の一つとしている。予備知識として必要なレベルは、高校数学の数I、数A程度である。
授業計画	グラフの定義と様々な例 「グラフ」の概念を理解し、いくつかの応用例を紹介する。 道と最短経路問題 グラフを各種の流通経路の表現として捉えたとき、中心的話題は2点間を結ぶ最も効率の良い経路の発見である。これまでにどういうことが学問的に判明しているかを学ぶ。 次数と隣接行列 グラフをコンピュータで解析する際などに用いられるデータ形式として、一番単純な形式である行列表現について学ぶ。 オイラーグラフと中国人郵便配達人問題 グラフを構成する辺集合のすべての要素を巡回する問題を扱う。「一筆書き」として知られている問題と同値である。 ハミルトングラフと巡回セールスマン問題 グラフを構成する点集合のすべての要素を巡回する問題を扱う。「巡回セールス問題」とは、最も効率の良い地域巡回の問題で、最適解を求める有効な方法が得られていない未解決問題として有名なものである。 木の基本的な性質と最適木 「木」とは閉路を持たないグラフの構造で、データベースの構造や検索問題において基本的な役割を持つ重要な概念である。
評価方法	毎週のゼミナールでの発表内容と受講態度により評価する。基礎概念の理解ができていればC以上、簡単な応用問題を処理できればB以上、いくつかの重要な定理、公式などを理解し数理的な考察力を習得していればA以上、という基準で評価を行う。
教科書
参考書
メッセージ	グラフ理論の世界は極めてパズル的な知的な世界です。考えることが好きな人の挑戦を待っています。