セジウィック：アルゴリズムC 第5部 グラフアルゴリズム
7,150円
(6,500円+税)
【注意】本書のEPUB版は固定レイアウト型になっております。文字の大きさの変更や検索、引用などはお使いいただけません。画面の大きい端末でご利用ください。
関連サイト
本書の関連ページが用意されています。
内容紹介
本書は『セジウィック：アルゴリズムC 第1〜4部』に続く，第5部の日本語版．グラフは，現実の問題をコンピュータで計算できるよう離散的な数学モデルに落とし込むための概念であり，本書は，その基礎として外せない項目を網羅している．また、グラフを現実的な時間で解くためのアルゴリズムを豊富に掲載しており，アルゴリズム研究の入門書としてもうってつけである．原著は，『アルゴリズムイントロダクション』と並び称される世界的名著．様々な分野でグラフおよびグラフアルゴリズムの知識が求められている今，待望の翻訳書といえる．
書誌情報
- 著者: R．セジウィック(著), 田口 東, 高松 瑞代, 高澤 兼二郎(訳)
- 発行日: 2021-11-24 (紙書籍版発行日: 2021-11-24)
- 最終更新日: 2021-11-24
- バージョン: 1.0.0
- ページ数: 400ページ(PDF版換算)
- 対応フォーマット: PDF, EPUB
- 出版社: 近代科学社
対象読者
グラフ,グラフアルゴリズム木,森,パス,グラフADT,隣接行列,隣接リスト,グラフ探索,深さ優先探索,幅優先探索,有向グラフ,有向非巡回グラフ,最小全域木,最短路,全点対間最短路,非巡回ネットワーク,ネットワークフローに興味がある人
著者について
R．セジウィック
田口 東
1974年 東京大学工学部計数工学科卒業
現 職 中央大学理工学部情報工学科教授 工学博士
高松 瑞代
2005年 東京大学工学部計数工学科卒業
2010年 東京大学大学院情報理工学系研究科博士課程修了
現 職 中央大学理工学部情報工学科准教授 博士（情報理工学）
高澤 兼二郎
2005年 東京大学工学部計数工学科卒業
2010年 東京大学大学院情報理工学系研究科博士課程修了
現 職 法政大学理工学部経営システム工学科准教授 博士（情報理工学）
目次
まえがき
練習問題に関する注意
目次
第5部 グラフアルゴリズム
第17章 グラフの特徴と種類
- 17.1 グラフに関する用語
- 17.2 グラフADT
- 17.3 隣接行列表現
- 17.4 隣接リスト表現
- 17.5 変種，拡張，コスト
- 17.6 グラフの生成
- 17.7 単純パス，オイラーパス，ハミルトンパス
- 17.8 グラフ処理問題
第18章 グラフ探索
- 18.1 迷路の探索
- 18.2 深さ優先探索
- 18.3 グラフ探索ADT 関数
- 18.4 DFS 森の性質
- 18.5 深さ優先探索アルゴリズム
- 18.6 分離可能性と二重連結性
- 18.7 幅優先探索
- 18.8 一般化グラフ探索
- 18.9 グラフアルゴリズムの解析
第19章 有向グラフと有向非巡回グラフ
- 19.1 用語と議論の枠組み
- 19.2 有向グラフにおける深さ優先探索の分析
- 19.3 到達可能性と推移閉包
- 19.4 同値関係と半順序
- 19.5 有向非巡回グラフ
- 19.6 トポロジカルソート
- 19.7 有向非巡回グラフにおける到達可能性
- 19.8 有向グラフの強連結成分
- 19.9 推移閉包の再検討
- 19.10 展望
第20章 最小全域木
- 20.1 重みつきグラフの表現
- 20.2 最小全域木アルゴリズムの根底にある原理
- 20.3 プリムのアルゴリズムと順位優先探索
- 20.4 クラスカルのアルゴリズム
- 20.5 ボルブカのアルゴリズム
- 20.6 比較と改良
- 20.7 ユークリッド最小全域木
第21章 最短路
- 21.1 根底にある原理
- 21.2 ダイクストラのアルゴリズム
- 21.3 全点対間最短路
- 21.4 非巡回ネットワークの最短路
- 21.5 ユークリッドネットワーク
- 21.6 帰着
- 21.7 負の重み
- 21.8 展望
第22章 ネットワークフロー
- 22.1 フローネットワーク
- 22.2 増加道を用いる最大流アルゴリズム
- 22.3 プリフロープッシュ最大流アルゴリズム
- 22.4 最大流への帰着
- 22.5 最小費用流
- 22.6 ネットワークシンプレックス法
- 22.7 最小費用流への帰着
- 22.8 展望