ACM-ICPC 程序設計系列圖論及應用 ACM-ICPC程序设计系列:图论及应用

馮林,金博,姚翠莉 主編

  • 出版商: 哈爾濱工業大學
  • 出版日期: 2012-03-01
  • 定價: $192
  • 售價: 8.5$163
  • 語言: 簡體中文
  • 頁數: 240
  • 裝訂: 平裝
  • ISBN: 7560332919
  • ISBN-13: 9787560332918

已絕版

買這商品的人也買了...

相關主題

商品描述

 

<內容簡介>

馮林、金博、姚翠莉主編的《圖論及應用》主要介紹ACM-ICPC比賽中涉及的圖論,其中包括許多實際問題的抽象表示與求解,以及部分圖論理論內容的證明。全書共分6章,第1章介紹了圖論的基礎知識,包括基礎概念、存儲方法和遍歷方法;第2章介紹了有關樹的問題,著重講解生成樹和一些樹上特殊點集的求法;第3章介紹了最短路徑問題,包括幾種通用演算法和特殊圖上的演算法;第4章介紹圖論中有關連通性的問題,包括有向圖的強連通、無向圖的雙連通及其擴展問題;第5章介紹網絡流解法,包括幾種常用的網絡流演算法和對於問題如何抽象成網絡流模型的經驗方法;第6章介紹二分圖的相關問題,重點為二分圖的匹配及其變種問題。《圖論及應用》的內容基本滿足ACM-ICPC比賽對於圖論方面的要求,講解清晰易懂,代碼規範,例題豐富。

 

<章節目錄>

第1章  圖
  1.1 圖的定義和術語
    1.1.1 圖的定義
    1.1.2 特殊的圖
    1.1.3 有向圖和無向圖
    1.1.4 路徑與連通
  1.2 圖的存儲結構
    1.2.1 鄰接矩陣
    1.2.2 前向星
    1.2.3 鄰接表
  1.3 圖的遍歷
    1.3.1 圖的深度優先遍歷
    1.3.2 圖的寬度優先遍歷
    1.3.3 圖的拓撲排序
    1.3.4 圖的可行遍性
第2章  樹
  2.1 樹的定義和遍歷
    2.1.1 樹的相關定義
    2.1.2 樹的遍歷
  2.2 圖的生成樹
    2.2.1 最小生成樹
    2.2.2 次小生成樹
    2.2.3 有向圖的最小樹形圖
  2.3 樹的其他問題
    2.3.1 樹上兩點的最近公共祖先
    2.3.2 樹的最小支配集,最小點覆蓋與最大獨立集
第3章  圖的最短路徑問題
  3.1 單源最短路徑
    3.1.1 Dijkstra演算法
    3.1.2 Bellman-Ford演算法
    3.1.3 SPFA演算法
    3.1.4 例題
  3.2 每對頂點間的最短距離
    3.2.1 Floyd演算法
    3.2.2 例題
  3.3 最短路問題的擴展與應用
    3.3.1 k短路
    3.3.2 差分約束系統
    3.3.3 DAG圖上的單源最短路徑
    3.3.4 Floyd求最小環
第4章  連通性問題
  4.1 圖的強連通
    4.1.1 強連通的定義
    4.1.2 Kosaraju演算法
    4.1.3 Tarjan演算法
    4.1.4 Garbow演算法
    4.1.5 例題
  4.2 最小點基
    4.2.1 最小點基的定義
    4.2.2 最小點基

    4.2.3 最小權點基
    4.2.4 例題
  4.3 圖的雙連通
    4.3.1 雙連通的定義
    4.3.2 點雙連通分量
    4.3.3 邊雙連通分量
    4.3.4 例題
  4.4 圖的全局最小割問題和Stoer-Wagner演算法
  4.5 2-SAT
    4.5.1 SAT
    4.5.2 2-SAT
    4.5.3 例題
第5章  網絡流
  5.1 網絡
    5.1.1 容量與流
    5.1.2 殘留網絡及增廣路
    5.1.3 最小割最大流定理
  5.2 最大流演算法
    5.2.1 Ford-Fulkson方法的基本思想
    5.2.2 Edmond-Karp演算法
    5.2.3 SAP演算法及其優化
    5.2.4 Dinic演算法
    5.2.5 例題與應用
  5.3 有上下界的網絡流
    5.3.1 解決上下界網絡流的一般思路
    5.3.2 例題與應用
  5.4 網絡的費用流
    5.4.1 連續最短路演算法
    5.4.2 例題與應用
第6章  二分圖及匹配演算法
  6.1 匹配問題
  6.2 匹配基本定理
    6.2.1 Berge定理
    6.2.2 Hall定理
  6.3 二分圖最大匹配
    6.3.1 匈牙利演算法
    6.3.2 Hopcroft-Karp演算法
    6.3.3 二分圖多重匹配
    6.3.4 二分圖最大匹配的網絡流解法
  6.4 二分圖最佳匹配
    6.4.1 Kuhn Munkras演算法
  6.5 二分圖模型的應用
    6.5.1 二分圖最小點覆蓋
    6.5.2 有向無環圖的最小路徑覆蓋
    6.5.3 二分圖的最大獨立點集
    6.5.4 最小點權覆蓋
參考文獻