スポンサーリンク

「グラフ理論」と「組み合わせ最適化アルゴリズム」の教科書PDF。離散数学の入門用の教科書


グラフ理論・組み合わせ最適化の講義ノート。

ネットワーク(経路系)のアルゴリズムも含む。


大学の情報科学では,「離散数学」という分野だ。

以下に,「グラフ理論」と「組み合わせ最適化」の入門段階の要点を並べてみる。

  • 最大フロー問題,最短経路問題,ダイクストラ法
  • オイラーグラフ,ハミルトングラフ
  • 巡回セールスマン問題,郵便配達人問題
  • 幅優先探索,深さ優先探索
  • グラフの連結性
  • 有向グラフと無向グラフ,グラフの隣接行列,双対グラフ
  • 辺彩色と面彩色,四色問題
  • マトロイド,離散マルコフ連鎖

これらの要点を独学で勉強しよう。

グラフがわかれば,グラフ上の最適化もわかる。


資料は,下記の分類にしたがって掲載した。


※P/NPなどの計算量理論のノートはこちら


(1)日本語の教科書

しっかりしたテキスト:

グラフ理論 講義ノート
http://chaosweb.complex.eng.hokudai.a...

  • 北海道大,268ページ。

イントロダクション
定義と例
様々なグラフの例
道と閉路
オイラー・グラフとハミルトン・グラフ
木とその数え上げ
平面性
有向グラフ
マッチング


2004年度 グラフ理論講義ノート : HUSCAP
http://eprints.lib.hokudai.ac.jp/dspa...

  • 上と同じ北大の資料を,章ごとに分割したもの。
  • グラフの定義からマッチング,結婚, Mengerの定理まで。


【2013 グラフ理論】資料置き場
http://www.kobepharma-u.ac.jp/~knot/d...

  • 神戸薬科大。

1章 ガイダンス
2章 グラフの定義と応用
3章 一筆書き
4章 畳を敷きましょう
5章 論理を学ぼう
6章 彩色グラフ
8章 グラフの基本概念
7章 三色の三角形
9章 赤い三角形・青い三角形
10-11章 マッチング・貨車の入れ替えクイズ
12章 あみだ籤の阿弥陀さま
13章 たくさん観光するためには
14章 オイラーの定理
15章 問題集


Graphs and Networks
http://coconut.sys.eng.shizuoka.ac.jp...

  • 静岡大。
  • 最短経路問題や最小費用フロー問題まで。


短めの資料:

アルゴリズム概論 講義資料・グラフ
http://ito-lab.naist.jp/lecture/alg04...

  • 26ページのスライド

探索
連結性
最短経路


7.グラフとネットワークのアルゴリズム
http://www2.kobe-u.ac.jp/~ky/da2/haih...

  • 神戸大,4ページのまとめ。


Webページ形式のノート:

Copy of 点と線の部屋
http://www.iis.it-hiroshima.ac.jp/~oh...

  • グラフ理論。広島工業大。

動画で勉強:

グラフ理論をYoutube動画で勉強。入門からオンライン講義,最先端の研究まで
http://study-guide.hatenablog.jp/entry/20140527/p1

(2)英語の教科書

Webページとして閲覧できるノート:

Graph Theory Lecture Notes
http://www-math.ucdenver.edu/~wcherow...

  • デンバー大の講義資料。
  • Basic Definitions and Graph Families (§§ 1.1 - 1.2)
  • Subgraphs and Graph Operations (§§ 2.1 - 2.2)
  • Graph Isomorphism and Matrix Representations (§§ 2.3 - 2.5)
  • Trees (§§ 3.1 - 3.3)
  • Counting, Traversing and Searching Binary Trees (§§ 3.4 - 3.6)
  • Depth-First and Breadth-First Search (§§ 4.1 - 4.3)
  • Spanning Trees (§§ 4.4 - 4.5)
  • Connectivity (§§ 5.1 - 5.3)
  • Optimal Graph Traversals (§§ 6.1 - 6.4)
  • Graph Colorings (§§ 10.1 - 10.2)
  • Network Flows and Applications (§§ 12.1 - 12.4)


PDFとして入手できるノート:

Diestel: Graph Theory - DiestelGT.pdf
http://www.esi2.us.es/~mbilbao/pdffil...

  • 322ページ,スペインのセビリヤ大。

1. The Basics
2. Matching
3. Connectivity
4. Planar Graphs
5. Colouring
6. Flows
7. Substructures in Dense Graphs
8. Substructures in Sparse Graphs
9. Ramsey Theory for Graphs
10. Hamilton Cycles
11. Random Graphs
12. Minors, Trees, and WQO


Graph Theory Lecture Notes - Math485.pdf
http://www.personal.psu.edu/cxg286/Ma...

  • 173ページ,ペンシルバニア州立大。

Chapter 1. Preface and Introduction to Graph Theory
Chapter 2. Some Definitions and Theorems
Chapter 3. More Definitions and Theorems
Chapter 4. Some Algebraic Graph Theory
Chapter 5. Applications of Algebraic Graph Theory: Eigenvector Centrality and Page-Rank
Chapter 6. Trees, Algorithms and Matroids
Chapter 7. A Brief Introduction to Linear Programming
Chapter 8. An Introduction to Network Flows and Combinatorial Optimization
Chapter 9. A Short Introduction to Random Graphs
Chapter 10. Coloring
Chapter 11. Some More Algebraic Graph Theory


GraphTheory.dvi - graphtheory.pdf
http://cs.bme.hu/fcs/graphtheory.pdf

  • フィンランドのテュルク大,100ページ。

1 Introduction
1.1 Graphs and their plane figures
1.2 Subgraphs
1.3 Paths and cycles
2 Connectivity of Graphs
2.1 Bipartite graphs and trees
2.2 Connectivity
3 Tours and Matchings
3.1 Eulerian graphs
3.2 Hamiltonian graphs
3.3 Matchings
4 Colourings
4.1 Edge colourings
4.2 Ramsey Theory.
4.3 Vertex colourings
5 Graphs on Surfaces
5.1 Planar graphs
5.2 Colouring planar graphs
5.3 Genus of a graph
6 Directed Graphs
6.1 Digraphs.
6.2 Network Flows


GTkansi.dvi - GT_English.pdf
http://math.tut.fi/~ruohonen/GT_Engli...

  • 114ページ,フィンランドのタンペレ技術大。

I DEFINITIONS AND FUNDAMENTAL CONCEPTS
II TREES
III DIRECTED GRAPHS
IV MATRICES AND VECTOR SPACES OF GRAPHS
V GRAPH ALGORITHMS
VI DRAWING GRAPHS
VII MATROIDS

(3)グラフ理論の応用に関する話題(組み合わせ最適化など離散数学)

グラフ理論をベースにした,組み合わせ最適化・離散数学のテキスト:

グラフ理論から組合せ最適化へ
http://www.kurims.kyoto-u.ac.jp/~kenk...

  • 8ページ。

内容:Euler閉路,マッチング,最大重みマッチング,主双対マッチング,完全マッチング多面体,郵便配達人問題


情報ネットワーク基礎論 ネットワークアルゴリズム
http://www-imase.ist.osaka-u.ac.jp/le...

  • 大阪大,36ページのスライド

通信ネットワークの基盤となる理論
 待ち行列理論
  ネットワークシミュレーション
  ネットワークの動きを確率的事象ととらえて解析
 ネットワークアルゴリズム(グラフ、ネットワーク理論、アルゴリズム理論、分散アルゴリズム理論)
  ネットワークをトポロジーとフローで(かなり大雑把な)モデル化
  組み合わせ理論として把握
  実際のネットワークでの利用(特に分散アルゴリズム理論)



数理科学特別講義(OR):2004年度〜2005年度(南山大学)
http://www-sys.ist.osaka-u.ac.jp/~ume...

  • 南山大の講義スライド。
  • この講義では代表的な組合せ最適化問題である巡回セールスマン問題(Traveling Salesman Problem)を通じて,計算困難な組合せ最適化問題に対する様々なアプローチを解説する.

 巡回セールスマン問題の紹介
 計算の複雑さとNP困難問題
 精度保証付き近似解法
 発見的解法
 局所探索法とメタ戦略
 配送計画問題


組み合わせ最適化問題 - CombinatorialOptimization.pdf
http://aoba.cc.saga-u.ac.jp/lecture/C...

  • 23ページのスライド,佐賀大。

 統計力学から計算機科学へ
  最低エネルギー状態を求める問題
 組合せ最適化問題
  厳密解を得られない場合
  近似的解法


近似アルゴリズム
http://www.ci.seikei.ac.jp/yamamoto/l...

  • 45ページ,成蹊大。

近似アルゴリズムとは
カット問題
集合被覆問題
頂点被覆問題
独立頂点集合問題
巡回セールスマン問題
負荷分散問題
ナップサック問題
ビンパッキング問題
近似スキーム
充足可能性問題
近似不可能性


社会や交通・プログラミングなどへの応用:

平面グラフと交通ネットワークのアルゴリズム
http://www.slideshare.net/iwiwi/ss-26...

  • 54ページのスライド。

1. 平面グラフのアルゴリズム
– 平面グラフ専用のグラフアルゴリズム
– 平面性をアルゴリズムでどのように活用?
– 基礎的なアプローチを紹介 (STOC, FOCS のような理論コミュニティの話題)
2. 交通ネットワークのアルゴリズム
– 現実世界の交通ネットワークにおける課題
– 最近の研究を紹介 (DB系, GIS系, 実験系アルゴリズムのような応用コミュニティの話題)
3 理論 応用


ネットワーク理論の基礎
http://www.meijigakuin.ac.jp/~mashiya...

  • 明治学院大,24ページ。

ネットワーク理論と社会・経済ネットワークの特徴
ネットワークの基本モデル
スモールワールド・モデルとスケールフリー・モデル


Spaghetti Source - 各種アルゴリズムの C++ による実装
http://www.prefield.com/algorithm/

  • 各種グラフのアルゴリズムをC++で実装。

基本要素
連結成分
最短路
全域木
フロー・カット
マッチング
ツリー
周遊路
その他



関連する記事:

ゲーム理論の講義ノートPDF。応用を含めた講義資料 (戦略と意思決定の方法論)
http://language-and-engineering.hatenablog.jp/entry/20140516/GameTheoryPDFNot...


多様体上の「積分幾何学」の,入門用講義ノートPDF。幾何学的な確率論への応用を学習
http://language-and-engineering.hatenablog.jp/entry/20140520/IntegralGeometry...


「群論入門」や代数学の講義ノートPDFまとめ。群・環・体の基礎から物理への応用までのオンライン教科書
http://language-and-engineering.hatenablog.jp/entry/20140505/AlgebraAndGroupT...


大学の「情報理論」(暗号を含む) の講義ノートPDF。代数学を使った情報量・符号化・通信路の理論
http://language-and-engineering.hatenablog.jp/entry/20140519/InformationTheor...