書籍詳細:よくわかるネットワークのアルゴリズム

郵政研究所研究叢書 よくわかるネットワークのアルゴリズム

の画像の画像
  • アラン・ドーラン
  • ジョーン・オールダス
  • 大石 泰彦
  • 紙の書籍
定価:税込 9,350円(本体価格 8,500円)
在庫なし
発刊年月
2003.03
旧ISBN
4-535-78373-X
ISBN
978-4-535-78373-7
判型
A5判
ページ数
632ページ
Cコード
C3041
ジャンル

内容紹介

数学・情報科学・工学・経済学など多くの分野で必須の知識である「ネットワークのアルゴリズム」について、豊富な実例と練習問題で懇切丁寧に解説した入門書。英国オープン・ユニバーシティ(通信放送教育)から生まれた定評あるテキスト。

目次

第1章 序論

1 基本概念

2 ネットワークの例

3 ネットワークの問題の分類

4 アルゴリズムの効率

5 ネットワーク分析の手順

第2章 グラフとダイグラフ

1 グラフと同型

2 グラフの隣接と接続

3 グラフにおける道とサイクル

4 グラフの例

5 グラフの表現

6 ダイグラフと同型

7 ダイグラフの隣接と接続

8 ダイグラフにおける道とサイクル

9 ダイグラフの表現

第3章 基本的ネットワークにおけるフロー

1 基本的ネットワーク

2 フロー増大道

3 最大フローと最小カット

4 最大フロー・最小カットの定理

5 最大フローのアルゴリズム

第4章 基本的フロー問題の諸変型

1 3つの変換

2 容量の下方制約、上方制約を持つネットワーク

第5章 多端点フロー

1 容量ルール

2 ゴモリーとフーのアルゴリズム

3 基本的アルゴリズム

4 完全なアルゴリズム

第6章 道と連結度

1 連結グラフと連結ダイグラフ

2 グラフについてのメンガーの定理(辺形式)

3 メンガーの定理の若干の類同命題

4 メンガーの定理の証明

5 テレコミュニケーションのネットワーク

第7章 最長道と最短道のアルゴリズム

1 最短道のアルゴリズム

2 最長道のアルゴリズム

3 最大フロー・最小コストのアルゴリズム

第8章 木

1 木の数学的諸性質

2 全域木を構成する

3 木を調べる

4 木を数え上げる

5 海底天然ガス・パイプラインの組織

第9章 物理的なネットワーク

1 成分と通過変数・横断変数

2 グラフによる表現

3 成分の動きをモデル化するさいに設定される諸仮定

第10章 電気のネットワーク

1 キルヒホフの電圧法則の方程式

2 基本サイクル

3 キルヒホフの電流法則の方程式

4 基本カットセット

5 基本サイクル行列と基本カットセット行列を得る

6 テリゲンの定理

第11章 電気のネットワーク

1 行列方程式の定式化

2 行列方程式を解く

3 状態方程式

第12章 マッチングの問題

1 結婚問題

2 修正された結婚問題

3 結婚定理の2つの証明

4 最大マッチングを求めるためのアルゴリズム

第13章 割りあて問題

1 割りあて問題についてのハンガリーのアルゴリズム

2 割りあて問題のいくつかの変型

第14章 輸送問題

1 輸送問題についてのハンガリーのアルゴリズム

2 輸送問題についての1つの交代的なアルゴリズム

3 積み替え問題

第15章 臨界道分析

1 活動の表現に頂点を用いる活動ネットワーク

2 事象の表現に頂点を用いる活動ネットワーク

3 2つのタイプの活動ネットワーク

4 臨界道

5 最も速い開始時間と最も遅い開始時間

第16章 日程計画(スケジューリング)

1 所与の人数の働き手についての、プロジェクトの日程計画

2 臨界道日程計画のアルゴリズム

3 防護の仕組みつきのアルゴリズム

第17章 収納問題

1 箱詰め問題

2 ナップザック問題

第18章 立地問題

1 頂点単一中心立地問題

2 頂点多中心立地問題

3 絶対中心立地問題

第19章 ネットワーク分析の理論

1 ネットワークのモデルの諸性質

2 ネットワークの問題のリニア・プログラミングとしての定式化

3 ネットワーク問題の双対形式

4 その他のネットワークの問題の双対形式

第20章 アルゴリズムとNP-完全性

1 アルゴリズムの効率

2 NP-完全問題

さらに進んだ読書のための案内

追い書き

本文中の問題の解

訳者あとがき

索引