グラフ理論/離散数学

有限離散の組合せ構造の諸性質を解析し、組合せ最適化を効率よく行うアルゴリズムを講究する。

0. グラフ基礎

1. 平面グラフ、双対平面グラフ

2. 2部グラフ、Eulerグラフ、双対性

3. ネットワーク、最大流問題、最大流最小カット定理

4. 最大2部マッチング点被覆定理、Mengerの定理

5. 線形計画法、単体法

6. 双対定理、相補性定理

7. 線形計画法と整数性、完全単模行列

8. 最小費用流問題

9. 理想グラフ

10. 区間グラフ

11. マトロイド、独立性、双対性

12. 双対性、貪欲アルゴリズム

13. グラフマイナー理論

14. 離散数学まとめ

第1講 グラフの基礎

vertex set:点集合

Edge set:辺集合

(U,v)でuからvへの枝を表す

(U,u)で自己閉路を表す

無限グラフになると色々おかしいことが起こるので有限グラフで考える

枝は無向と有向を考える。

単純：自己閉路、並列枝なし

完全グラフ：どの2点の間にも枝がある→枝数はCで求められる

Planer：平面上の交差なしで描ける

削除：

縮約：

全域木：

Eulerの定理：

双対平面グラフ

第2講 ネットワークフローの基礎

ネットワーク：重み付き有向グラフ、有向グラフで、枝に実数値が割り当てられていて、特別な２点が存在する

(A,b)は順序付きで、{a,b}は順序なしを表す

今回は、自己閉路がなくて、平行辺がない単純な有向グラフを扱う

フローの定義：容量保存かつ流量保存

カットの定義：

カット容量について調べることでフローについてわかることがある

第3講 ネットワークフローの基礎

第4講 線形計画

線形計画問題

・多変数の線形等式・線形不等式の制約のもと、その他変数の線形関数を最適化

-様々な現実問題をモデル化できる

-ネットワークフローの諸問題は特殊な場合（整数性）

-かなり大規模問題も解ける(単体ほう、内点法)

・単体法

-基底解をpivotingで写って最適解を求める

考え方

最適解は凸多面体の端点に限って良い

ある端点からスタートして、辺をたどって隣の端点でより良い端点に動く、これを繰り返しどの隣の端点より良い端点が最適解となる

これを行列で表現する（標準形から基底形式へ）

ー部分正方行列で正則な基底に着目

-実行可能基底解：端点になっている

-隣の端点に移動：pivoting(現基底から一変数入れ替え)

単体法の基底形式での考え方

・等式制約で注目している単位行列（基底）

第5講 線形計画の双対性

第6講 計算量理論

アルゴリズムとは与えられたデータの中から欲しい情報を見つける手順

計算不可能の時は停止性問題というプログラムが有限時間で終わるかを調べる問題になる

計算可能の時は、

NP困難：解の候補の大部分を調べることが必要、整数計画問題、Ising模型、コミュニティ発見

NP完全：怪異の候補の大部分を調べることが必要かつ解の候補をある程度は調べなければいけない

NP：解本候補をある程度は調べなければいけない、素因数分解、グラフ同型

P：解の候補を部分だけ調べれば最適解が求まる、最短経路問題、線形計画問題、pagerank

最近では計算機の高速化によって計算困難な問題でも取り扱い可能になり、一緒くたに計算困難とされていた問題の中にも困難さのグラデーションが存在することがわかった

というのも、従来は一変数解析だったが、多変数解析になった

指数時間は計算困難で、多項式時間は効率的である

第7講 最短路問題

第8講 最小費用流

有向グラフの接続行列ではtotally moduler

で整数性と関係している

第9講 Matroid

Sによる点誘導部分グラフ

Induced subgraphがsubgraphの特殊な場合。

点が中心のグラフ問題では誘導部分グラフを考えるのがセオリーである。

補グラフ：全てを結ぶEdgeを加えたグラフ

GのクリークはGの捕グラフの

レジスターロケーションはグラフの彩色の問題となる

３点について考えたときに完全グラフになっているのがクリーク

双対性が壊れたとき、NP完全になる

Duality-gapが0になるケースを考える

Weak perfect graph theorem

Strong perfect graph theorem

PerfectGraphの有用な部分クラスとしてInterval Graphがある。

実数のグラフ

第10講

無効グラフで閉路がないことがあ

過去問用語

単純、連結、外平面グラフ、２部グラフ、マッチング、最大流量最小カット定理、マトロイド、双対グラフ、双対マトロイド、基底形式、ピボッティング、双対性・相補性、退化、交差グラフ、区間グラフ、最大重み安定集合、単体法、クリーク、

重み付きのMaxmam weightのstabke setを求めるのが出題

単体法

最小費用流の問題

最短路問題

1問 平面グラフ、オイラーの公式、トポロジカルな公式、平面グラフのduality、Matroidのduality、平面グラフの場合の木分解、最大の重さを求める(?)

2問 ネットワークフローについての線形計画問題、線形計画の単体法

3問 最小費用流の問題

4問 そこまでに見つかった最長路のを中間変数として定義して、前回やったアルゴリズムの重みがあるバージョンを出す

ランダムグラフ