2014-05-28

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

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

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

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

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

最大フロー問題，最短経路問題，ダイクストラ法

オイラーグラフ，ハミルトングラフ

巡回セールスマン問題，郵便配達人問題

幅優先探索，深さ優先探索

グラフの連結性

有向グラフと無向グラフ，グラフの隣接行列，双対グラフ

辺彩色と面彩色，四色問題

マトロイド，離散マルコフ連鎖

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

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

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

（１）日本語の教科書

（２）英語の教科書

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

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

（１）日本語の教科書

しっかりしたテキスト：

グラフ理論講義ノート
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ページのスライド

探索
連結性
最短経路

７．グラフとネットワークのアルゴリズム
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

（２）英語の教科書

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...

３２２ページ，スペインのセビリヤ大。

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

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

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

グラフ理論から組合せ最適化へ
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 （Computational Geometry）

計算機科学講義ノートリンク集幾何学アルゴリズム

講義ノートの目次へ

CGやゲーム開発にも役立つ計算・幾何学（けいさん・きかがく）の教科書。

点・線分などの図形を数値計算する時に必要なアルゴリズムを勉強できる。

プログラミングにすごく役立つ。

複雑な図形どうしの関係を，三角形や木構造を使ってシンプルに考えられるようになり面白い。

たとえば…

平面上に，たくさんの点が存在する。点の分布にしたがって領域を分割し，境界線を描画したい。勢力図やテリトリーを生成したい。（＝ボロノイ図）

複雑な形の部屋で，監視カメラで全体を見渡す。部屋中をもれなく監視するには，どこにいくつカメラを置けばいいか？（＝美術館問題，領域の三角形分割）

地図上で，川が国境をまたぐのはどこ？（＝線分の交差問題）

点とエリアの「当たり判定」をしたい。地図上の１点を選んだとき，その点がどの国に属するのかを高速に求めたい（＝点位置決定問題）

平面上に，たくさんの点が存在する。すべての点をカバーするようなエリアを定めたい。すべての点を内部に含むような１つの多角形（または円）を作るには？（＝凸包問題）

こういったグラフィカルな問題を扱うのが計算幾何学。

コンピュータ・グラフィクスの重要な知識だ。

※なお，この手の図形的問題をさらに解析的に扱うためには，積分幾何学のノートもあわせて学習するとよい。

※図形から構造の概念だけを抽出し，グラフ構造として考えることも多い。グラフ理論の教科書を読んでおくとよい。

計算幾何学を勉強するためのテキスト

日本語で学べる資料：

情報科学コース『数理科学特論』ならびに情報科学科３年『応用幾何学』のページ
http://www.kanenko.com/~kanenko/KOUGI...

お茶の水女子大。

第１回　凸包の計算．
第２回　線分交又．
第３回　面分交又．
第４回　三角形分割．
第５回　三角形分割から半平面交叉へ．
第６回　線型計画法．
第７回　Kd 木．
第８回　領域探索の続き．
第９回　点の位置特定
第１０回　ロボットモーション立案
第１１回　ボロノイ図
第１２回　ドロネー３角形分割

Blogopolisから学ぶ計算幾何：連載｜gihyo.jp … 技術評論社
http://gihyo.jp/dev/serial/01/geometry

TopHatenarなどのWebサービスの実装に使われた技術を解説。サンプルコードつき。

第1回　直線の幾何
第2回　線分の幾何
第3回　平面走査法による線分の交差検出（前編）
第4回　平面走査法による線分の交差検出（中編）
第5回　平面走査法による線分の交差検出（後編）
第6回　多角形の幾何（前編）
第7回　（臨時回）線分の交差判定再訪
第8回　多角形の幾何（後編）
第9回　凸多角形の交差計算（前編）
第10回　凸多角形の交差計算（後編）
第11回　ボロノイ図の作成（前編）
第12回　ボロノイ図の作成（後編）

Computational Geometry - Lecture Notes
http://i-health.u-aizu.ac.jp/CompuGeo...

会津大の講義資料スライド。

第一章　基本概念
第二章　線分交差
第三章　凸包
第四章　ボロノイ図
第五章　ドローネ三角形分割
第六章　幾何的領域探索
第七章　多角形の三角形分割

計算幾何学の問題のジャンルがリストになっているページ：

計算幾何学(computational geometry)
http://www.triplefalcon.com/Lexicon/G...

引用：計算幾何学(computational geometry) は、おそらく最も工学上の応用が多い数学分野の一つです。...人間が紙に描くことができる図形上の学問に、計算量的な考察を加えた研究分野全般を計算幾何学という

Computational Geometry
http://isotope.sist.chukyo-u.ac.jp/le...

引用：計算幾何学は，幾何学に計算の複雑さの理論を導入し， 幾何学的な問題に対する効率の良いアルゴリズムを開発，またはその問題の難しさを解析する計算機科学の一分野である．

英語で読める教科書：

Introduction to Computational Geometry - arbintrocgtrichy.pdf
http://www.tcs.tifr.res.in/~workshop/...

インドの統計学研究所，106ページのスライド。

1 Introduction
2 Area Computation of a Simple Polygon
3 Point Inclusion in a Simple Polygon
4 Line Segment Intersection: An application of plane sweep
5 Convex Hull: An application of an incremental algorithm
6 Art Gallery Problem: A study of combinatorial geometry

Computational Geometry
http://www.cimec.org.ar/~ncalvo/DeBer...

367ページ。

Lecture Notes | Computational Geometry | Mechanical Engineering | MIT OpenCourseWare
http://ocw.mit.edu/courses/mechanical...

MITの講義資料。有限要素法も扱っている。

Computational Geometry
http://www.robots.ox.ac.uk/~ian/Teach...

オックスフォード大の講義資料。

Lecture1:Euclidean,similarity,projective transformations. Homo-geneous coordinatesandmatrices. Coordinateframes.
Lecture2:Perspective projection and its matrix representation. Vanishing points. Applications of projective transformations.
Lecture3:Convexity of point-sets, convexhull and algorithms. Conics and quadrics,implicit and parametric forms,computation of intersections.
Lecture4:Bezier curves,B-splines.Tensor-product surfaces.