グラフとネットワーク [2008年度後期] (終了)

• 試験について (2009.02.24 総合得点の採点結果を掲載しました. )
• 授業アンケートの回答に答えて (2008.11.13 更新)
• シラバス
• 担当教員: 安藤和敏 (静岡大学工学部)
• 使用する教科書と参考書
  
  • 教科書
    

    藤重悟著 「グラフ・ネットワーク・組合せ論」 共立出版, 2002年. [著者によるサポートのページ]

• 講義予定
  • 第01回 [2008.10.02] ガイダンス.
    スライド (PDF)
  • 第02回 [2008.10.09] 1.1 グラフの定義 (部分グラフの定義を除く).
    練習問題の解答例 (PDF)
  • 第03回 [2008.10.16] 1.2 グラフの表現: 行列表現, リスト表現.
    練習問題の解答例 (PDF)
    プログラム ( graph.h, graph.c, test-graph.c), 入力ファイル ( ex2.max, ex3.max), コンパイルと実行の仕方(README3.txt)
  • 第04回 [2008.10.23] 1.3 特殊なグラフ(木, 有向木), 1.4 グラフの探索.
    スライド (PDF), ハンドアウト (PDF)
    練習問題の解答例 (PDF)
    プログラム ( stack.h, stack.c, queue.h, queue.c, graph_search.c), 入力ファイル ( ex2.max, ex3.max), コンパイルと実行の仕方(README4.txt)
    
  • 第05回 [2008.10.30] 1.5 連結性: 1.5.1〜1.5.3.
    ハンドアウト (PDF)
    演習問題の解答例 (PDF)
  • 第06回 [2008.11.06] 1.5 連結性: 1.5.4.
    演習問題の解答例 (PDF)
    
  • 第07回 [2008.11.13] 1.3 特殊なグラフ (オイラーグラフとハミルトングラフ)
    ハンドアウト (PDF)
    演習問題の解答例 (PDF)
  • 第08回 [2008.11.20] 中間試験 (@佐鳴会館会議室)
    解答例 (PDF)
  • 第09回 [2008.11.27] 2.1 木と道 2.1.1 最小木問題 (貪欲アルゴリズム, ヤルニーク-プリムのアルゴリズム).
    ハンドアウト (PDF)
    演習問題の解答例 (PDF)
    プログラム ( kruscal.c, prim.c), 入力ファイル ( mcst1.dat, mcst2.dat), コンパイルと実行の仕方(README9.txt)
    
  • 第10回 [2008.12.04] 2.1 木と道 2.1.2 最短路問題 (ダイクストラ法).
    ハンドアウト (PDF)
    演習問題の解答例 (PDF)
    プログラム (dijkstra0.c), 入力ファイル ( ex3.max, ex4.max), コンパイルと実行の仕方(README10.txt)
    
  • 第11回 [2008.12.11] 2.1 木と道 2.1.2 最短路問題 (ベルマン-フォード法).
    ハンドアウト (PDF)
    演習問題の解答例 (PDF)
    プログラム (bermanford0.c), 入力ファイル ( ex5.txt, ex5-2.txt, ex6.txt, ex6-2.txt), コンパイルと実行の仕方(README11.txt)
    
  • 第12回 [2009.01.15] 2.2 フローとカット 2.2.1 2端子フロー (フォード-ファルカーソンのアルゴリズム).
    ハンドアウト (PDF)
    演習問題の解答例 (PDF)
    
  • 第13回 [2009.01.22] 2.2 フローとカット 2.2.1 2端子フロー (最大フロー-最小カット定理).
    ハンドアウト (PDF)
    練習問題の解答例 (PDF)
    
  • 第14回 [2009.01.29] 2.4 マッチングと被覆.
    ハンドアウト (PDF)
    練習問題の解答例 (PDF)
  • 第15回 [2009.02.12] 期末試験.