グラフ・ネットワーク・マトロイド

講座・数理計画法7

伊理正夫、藤重 悟、大山達夫(著)

産業図書、1986年(初版)、2005年(復刊)

目次

1. グラフ

1.1 グラフの定義と基礎概念
(a) 点と枝の接続関係
(b) 道と閉路
(c) グラフノ同形性
(d) グラフの変形
1.2 グラフの連結性
(a) 連結性
(b) 2連結性
(c) 3連結性
1.3 グラフの強連結性
1.4 グラフの代数的構造
(a) 木、補木、サーキット、カットセット
(b) 基本サーキット系、基本カットセット系
(c) グラフに関して定まるベクトル空間
(d) 2同形性
(e) 双対グラフと平面グラフ
1.5 特殊なグラフ
文献ノート


2. データ構造と基本的算法

2.1 グラフの表現
2.2 効率のよい算法(基本形)
(a) 奥優先探索と幅優先探索
(b) 最小木問題
(c) 最短路問題 
(c-1) Dijkstra法
(c-2) べき乗法
(c-3) Warshall-Floyd法
文献ノート


3. 分配束、半順序集合と劣モジュラ関数

3.1 分配束と半順序集合
3.2 劣モジュラ関数と分配束
3.3 劣モジュラ・システム
3.4 最小基問題
3.5 劣モジュラ・システムの基本分割と基本構造
文献ノート

4. ネットワーク

4.1 最大流
(a) 循環流
(b) 2端子流
(c) 最大流問題の解法
(d) 最小カット族の束構造
(e) 実行可能循環流の存在定理
4.2 最小費用流
(a) プライマルな算法
(b) プライマル・デュアルな算法
(c) Hitchcock型輸送問題
(d) 最小費用循環流
4.3 複数端末流
(a) ネットワークの実現可能性
(b) 流量関数の決定
(c) ネットワークの合成
文献ノート

5. マッチングと連接

5.1 2部グラフのマッチング
(a) 最大マッチングと最小被覆
(b) Dulmage-Mendelsohn 分解
(c) Dulmage-Mendelsohn 分解の性質
(d) 割当問題
5.2 連接
(a) 枝を共有しない道の集合
(b) 点を共有しない道の集合
(c) 点型の連接と2部グラフのマッチング
5.3 一般のグラフのマッチング
(a) 最大マッチング
(b) ``花’’と増加道
(c) マッチングに関する最大・最小定理
(d) 次数制約を満たす部分グラフ
(e) 最適マッチング問題
文献ノート

6. マトロイド

6.1 マトロイド
(a) マトロイドの定義とその例
(b) マトロイドの基礎概念と公理系
(c) 双対マトロイド
(d) マトロイドの変換
6.2 ポリマトロイド
(a) ポリマトロイドの定義とその例
(b) ポリマトロイドと劣モジュラ・システム
(c) マトロイドとポリマトロイド
(d) ポリマトロイドの変換
6.3 独立流
(a) 最大独立流
(b) 最大独立流の特徴づけ
(c) 最大独立流問題の解法
(d) 最小費用独立流問題
(e) 最小費用独立流問題の特徴づけ
(f) 最小費用独立流問題の解法
6.4 劣モジュラ流
6.5 独立マッチング
(a) 最大独立マッチング
(b) 最適独立割当
(c) 合併マトロイドと最大共通独立集合
6.6 ポリマトロイドの基本分割
(a) 基に関するポリマトロイドの基本分割
(b) 重みベクトルに関するポリマトロイドの最適基
6.7 応用
(a) 最適有向木問題
(b) 電気回路網の諸問題
(b-1) 最小基本方程式
(b-2) 電気回路網が一意解をもつための位相幾何学的条件
(c) 組合せ的制約をもつ線形動的システムの可観測性・可制御性
(c-1) 可観測性
(c-2) 可制御性
(d) 複数個の入口と出口をもつネットワークの最適流
(e) 情報理論的問題
(e-1) 情報理論的相関分析
(e-2) 多重通信網の問題
(f) Shannonのスイッチング・ゲーム
文献ノート

参考文献
索引
人名索引