演習グラフ理論: 基礎と応用

まえがき 用語,記号についての注意 目次 1. グラフの基礎概念 1.1 グラフの構造 演習問題の解答 1.2 道,閉路,カットセット 演習問題の解答 1.3 連結成分と木 演習問題の解答 1.4 基本閉路と基本カットセット 演習問題の解答 1.5 非可分性,連結度,強連結性 演習問題の解答 1.6 特殊な構造をもつグラフ 演習問題の解答 2. グラフの行列 2.1 隣接行列 演習問題の解答 2.2 接続行列 演習問題の解答 2.3 閉路行列(タイセット行列) 演習問題の解答 2.4 カットセット行列 演習問題の解答 3. グラフの基礎算法 3.1 グラフを表現するデータ構造 演習問題の解答 3.2 縦形探索 演習問題の解答 3.3 横形探索と迷路法 演習問題の解答 3.4 最短路問題 演習問題の解答 3.5 最小木 演習問題の解答 3.6 マッチングと被覆 演習問題の解答 3.7 2部グラフのマッチング 演習問題の解答 3.8 組合せ問題の計算の複雑 演習問題の解答 4. ネットワーク手法 4.1 最大フロー問題 演習問題の解答 4.2 最小コストフロー問題 演習問題の解答 4.3 フロー問題と線形計画法 演習問題の解答 4.4 最小コスト循環フロー問題 演習問題の解答 5. 回路 5.1 Kirchhoffの法則 5.2 枝特性 5.3 状態方程式 5.4 混合方程式──タイセット方程式とカットセット方程式の一般化 5.5 位相幾何学的自由度と基本分割 5.6 点方程式とグラフ理論的公 6. マトロイド 6.1 マトロイドの公理と基本概念 演習問題の解答 6.2 マトロイド算法1──グリーディ算法 6.3 マトロイド算法2──独立マッチング算法 6.4 マトロイドの基本分割 演習問題の解答 付録 A6.1 マトロイドの表現可能性 A6.2 ポリマトロイドの公理 A6.3 ポリマトロイド算法──独立フロー算法 A6.4 パラメータ入りの基本分 参考文献 AB CDE F GH I JK L MN OP RS T VWYZ 演習問題の解答 索引 ABCDEFG HIJK LM NOPRS T UWYZ