0去购物车结算
购物车中还没有商品,赶紧选购吧!
当前位置: 图书分类 > 数学 > 运筹学/控制论 > 有向图的理论算法及其应用

相同语种的商品

浏览历史

有向图的理论算法及其应用


联系编辑
 
标题:
 
内容:
 
联系方式:
 
  
有向图的理论算法及其应用
  • 书号:9787030228048
    作者:姚兵,张忠辅
  • 外文书名:
  • 装帧:平装
    开本:B5
  • 页数:663
    字数:835000
    语种:zh-Hans
  • 出版社:科学出版社
    出版时间:2009-01-01
  • 所属分类:O15 代数、数论、组合理论
  • 定价: ¥198.00元
    售价: ¥156.42元
  • 图书介质:
    纸质书

  • 购买数量: 件  商品库存: 4
  • 商品总价:

相同系列
全选

内容介绍

样章试读

用户评论

全部咨询

本书作者从近30年关于有向图理论研究的数千篇论文中精选了具有理论意义、重要算法及其实际应用的结果,涵盖了有向图理论中从最基本到较为高深的重要专题。主要内容有:有向图的基本知识和理论、连通性、图的定向、网络流、哈密尔顿性的深入研究、有向图的路和圈、子模流、竞赛图的推广以及有向图的推广、Menger定理和NP完全问题等。书中介绍了有向图研究中数十个未解决的问题和猜想,尽可能为读者在主要方向上提供最新的研究成果。对于计算机科学领域的学者来说,书中的大量算法以及实际应用的例子提供了难得的帮助。此外,配备了练习题700多道、方便查询的参考文献762篇,以及记号和术语索引等。
样章试读
  • 暂时还没有任何用户评论
总计 0 个记录,共 1 页。 第一页 上一页 下一页 最末页

全部咨询(共0条问答)

  • 暂时还没有任何用户咨询内容
总计 0 个记录,共 1 页。 第一页 上一页 下一页 最末页
用户名: 匿名用户
E-mail:
咨询内容:

目录

  • 目录
    第1章 基本术语及结论 1
    1.1 集合、子集、矩阵和向量 1
    1.2 有向图、有向子图、邻集和度数 2
    1.3 有向图的同构及其基本运算 6
    1.4 途径、迹、路、刚和路圈有向子图 10
    1.5 强连通性和单侧连通性 15
    1.6 无向图、双定向和定向性 17
    1.7 混合图和超图 21
    1.8 有向图和无向图的分类 23
    1.9 算法简介 26
    1.9.1 算法及其复杂性 26
    1.9.2 NP完全问题和NP困难问题 30
    1.10 应用:求解2可满足性问题 32
    习题 35
    第2章 距离 40
    2.1 关于距离的术语和记号 40
    2.2 最短路结构 42
    2.3 寻找有向图距离的算法 44
    2.3.1 宽度优先搜索(BFS) 44
    2.3.2 无圈有向图 46
    2.3.3 Dijkstra算法 47
    2.3.4 Bellman-Ford-Moore算法 48
    2.3.5 Floyd-Warshall算法 51
    2.4 半径、山半径和直径之间的不等式 52
    2.4.1 强有向图的半径和直径 52
    2.4.2 出半径和直径的极值 53
    2.5 定向图的最大有限直径 54
    2.6 多重图定向的最小直径 55
    2.7 完全多重图的最小直径定向 59
    2.8 图扩张的最小直径定向 61
    2.9 笛卡儿积图的最小直径定向 63
    2.10 有向图中的王 66
    2.10.1 竞赛图的2王 66
    2.10.2 半完全多部分有向图中的王 66
    2.10.3 广义竞赛图中的王 68
    2.11 应用:单行道问题和闲话问题 69
    2.11.1 单行道问题和有向图的定向 69
    2.11.2 闲话问题 71
    2.12 应用:旅行售货员问题的指数邻集局部搜索 72
    2.12.1 TSP局部搜索 72
    2.12.2 TSP的线性时间叮搜索指数邻集 74
    2.12.3 分配邻集 75
    2.12.4 关于TSP的邻集结构有向图的直径 76
    2.13 习题 78
    第3章 网络流 82
    3.1 定义及基本性质 82
    3.1.1 流及流平衡向量 83
    3.1.2 剩余网络 85
    3.2 网络模型的简约 86
    3.2.1 消除下界 86
    3.2.2 单源单收点网络 86
    3.2.3 循环 87
    3.2.4 顶点上有费用及下界的网络 88
    3.3 流分解 90
    3.4 时论剩余网络 91
    3.5 最大流问题 93
    3.5.1 Ford-Fullkerson算法 96
    3.5.2 最大流与线性规划 98
    3.6 寻找最大(s,t)流的多项式算法 99
    3.6.1 沿最短增广路的流增广 99
    3.6.2 在分层网络和Dinic算法中的块化流 100
    3.6.3 前置流推进算法 101
    3.7 单位容量网络和简单网络 105
    3.7.1 单位容量网络 106
    3.7.2 简单网络 107
    3.8 循环与可行流 108
    3.9 最小值可行(s,I)流 110
    3.10 最小费用流 111
    3.10.1 刻画最小费用流 113
    3.10.2 创建最优化解 116
    3.11 流的应用 118
    3.11.1 部分图的最大匹配 118
    3.11.2 有向中国邮递员问题 121
    3.11.3 寻找具有预先指定度的有向子图 l23
    3.11.4 有向多重图的路圈因子 124
    3.11.5 覆盖指定顶点的圈有向子图 126
    3.12 分配问题和运输问题 127
    3.13 习题 l36
    第4章 有向图类 148
    4.1 深度优先搜索 148
    4.2 无圈有向图中的顶点无圈序 151
    4.3 可传递有向图、可传递闭包和简约 153
    4.4 强有向图 155
    4.5 线有向图 158
    4.6 de Bruijn有向图和Kautz有向图及其特征 l62
    4 7 系列平行有向图 165
    4.8 拟可传递有向图 169
    4.9 路重合性质和路可重合有向图 171
    4.10 局部入半完全有向图和局部山半完全有向图 173
    4.11 局部半完全有向图 175
    4.11.1 圆有向图 175
    4.11.2 非强局部半完全有向图 179
    4.11.3 强圆可分解局部半完全有向图 l8l
    4.11.4 局部半完全有向图类 183
    4.12 全φi可分解有向图 l85
    4.13 相交有向图 187
    4.14 平而有向图 189
    4.15 应用:高斯消去法 l9l
    4.16 习题 l93
    第5章 哈密尔顿性及其相关问题 l96
    5.1 有向图哈密尔顿性的必要条件 197
    5.1.1 路收缩 197
    5.1.2 拟哈密尔顿性 198
    5.1.3 伪哈密尔顿性和1拟哈密尔顿性 200
    5.1.4 关于伪哈密尔顿性和拟哈密尔顿性的算法 201
    5.2 路覆盖数 201
    5.3 无圈有向图的路因子及其应用 203
    5.4 路可重合有向图的哈密尔顿路与圈 204
    5.5 局部入半完全有向图的哈密尔顿路和圈 205
    5.6 具有度约束条件的有向图的哈密尔顿圈和路 20?
    5.6.1 充分性条件 207
    5.6.2 多重插入技巧 211
    5.6.3 定理5.6.1和定理5.6.5的证明 213
    5.7 半完全多部分有向图中的最长路和最长路圈 215
    5.7.1 基本结论 215
    5.7.2 良圈因子定理 217
    5.7.3 引理5.7.12的推论 220
    5.7.4 Yeo不可约圈有向子图定理及其应用 222
    5.8 扩张局部半完全有向图的最长路和最长圈 226
    5.9 拟可传递有向图中的哈密尔顿路和圈 227
    5.10 拟可传递有向图中顶点最重路和最重圈 230
    5.11 有向图类的哈密尔顿路和圈 234
    5.12 习题 236
    第6章 深入研究哈密尔顿性 241
    6.1 具有预先指定起(终)点的哈密尔顿路 242
    6.2 弱哈密尔顿连通有向图 243
    6.2.1 关于扩张竞赛图的结论 244
    6.2.2 关于局部半完全有向图的结论 248
    6.3 哈密尔顿连通有向图 251
    6.4 在半完全有向图中寻找(x,y)哈密尔顿路 253
    6.5 有向图的泛圈性 256
    6.5.1 度约束有向图的(顶点)泛圈性 256
    6.5.2 扩张半完全有向图和拟可传递有向图的泛圈性 257
    6.5.3 泛局部半完全有向图和顶点泛局部半完全有向图 260
    6.5.4 关于图泛圈性的其他结果 263
    6.5.5 有向图的圈可扩张性 264
    6.6 弧泛圈性 265
    6 7 包含或避开预先指定弧的哈密尔顿圈 267
    6.7.1 包含预先指定弧的哈密尔顿圈 268
    6 7 2 避开预先指定弧的哈密尔顿圈 270
    6.7.3 避开2圈中弧的哈密尔顿圈 272
    6.8 弧不交的哈密尔顿路和圈 273
    6.9 定向的哈密尔顿路和圈 275
    6.10 用少量圈覆盖一个有向图的全部顶点 280
    6.10.1 具有固定圈数目的圈因子 280
    6.10.2 父于路和圈的支撑结构中α(D)的作用 282
    6.11 最小强支撑有向子图 283
    6.11.1 关于一般有向图的一个下界 284
    6.11.2 关于扩张半完全有向图的MSSS问题 285
    6.11.3 关于拟可传递有向图的MSSS问题 286
    6.11.4 可分解有向图的MSSS问题 287
    6.12 应用:TSP直观探索法的控制数 288
    6.13 习题 290
    第7章 全连通性 294
    7.1 附加的概念和预备知识 295
    7.2 耳朵分解 297
    7.3 Menger定理 300
    7.4 应用:确定弧强连通度和顶点强连通度 303
    7.5 撕裂运算 305
    7.6 最优化增长弧强连通性 309
    7.7 最优化增长顶点强连通性 312
    7.7.1 单行对 313
    7.7.2 最优化的k强增广 315
    7.7.3 特殊类有向图 316
    7.7.4 保持k强连通性的撕裂 318
    7.8 弧强连通性的一个推广 320
    7.9 弧反转和顶点强连通性 322
    7.10 最小k(弧)强有向多重图 325
    7.10.1 最小良弧强有向多重图 326
    7.10.2 最小k强有向图 329
    7.11 临界k强有向图 333
    7.12 弧强连通性与最小度 334
    7.13 特殊类有向图的连通性性质 335
    7.14 有向图的高连通定向 337
    7.15 拼装割集 341
    7.16 应用:关于k(弧)强连通性的小认证 344
    7.16.1 寻找强连通性的小认证 345
    7.16.2 寻找k强认证(k>1) 346
    7.16.3 关于弧强连通性认证 348
    7.17 习题 349
    第8章 图的定向 353
    8.1 几类有向图的底图 353
    8.1.1 可传递有向图和拟可传递有向图的底图 353
    8.1.2 局部半完全有向图的底图 356
    8.1.3 正常循环弧图的局部竞赛图定向 358
    8.1.4 局部入半完全有向图的底图 360
    8.2 快速识别局部半完全有向图 364
    8.3 无偶圈定向 367
    8.4 图的着色与定向 369
    8.5 定向与无处零整流 371
    8.6 达到高弧强连通性的定向 375
    8 7 具有度约束的定向 378
    8 7 1 具有预先指定度序列的定向 378
    8.7.2 对顶点予集的限制 382
    8.8 子模流 383
    8.8.1 子模流模型 383
    8.8.2 可行子模流的存在性 385
    8.8.3 最小费用子模流 388
    8.8.4 子模流的应用 388
    8.9 混合图的定向 392
    8.10 习题 396
    第9章 不交路和不交树 402
    9.1 补充定义 403
    9.2 不交路问题 403
    9.2.1 k路问题的复杂性 404
    9.2.2 有向图是良链接的充分性条件 408
    9.2.3 无圈有向图的k路问题 410
    9.3 竞赛图和广义竞赛图的链接问题 413
    9.3.1 具有(局部)连通性的充分性条件 413
    9.3.2 半完全有向图的2路问题 417
    9.3.3 广义竞赛图的2路问题 418
    9.4 平面有向图的链接问题 42l
    9.5 弧不交分枝 424
    9.5.1 Edmonds分枝定理的重要性 426
    9.6 边不交的混合分枝 429
    9 7 弧不交的路问题 430
    9.7.1 无圈有向多重图中弧不交的路 432
    9 7 2 欧拉有向多重图中弧不交的路 433
    9 7 3 竞赛图和广义竞赛图中弧不交的路 438
    9.8 整多物品流 44l
    9.9 弧不交的出分枝和入分枝 442
    9.10 最小费用分枝 447
    9.10.1 拟阵相交的表述 447
    9.10.2 有关最小费用分枝问题推广的一个算法 448
    9.10.3 最小覆盖树形图问题 453
    9.11 添加新弧以增加有根弧强连通性 455
    9.12 刊题 456
    第10章 有向图的圈结构 462
    10.1 有向图的向量空间 462
    10.2 关于路和圈的多项式算法 466
    10.3 不交圈和反馈弧集 469
    10.3.1 不交圈和反馈集问题的复杂性 469
    10.3.2 最大出度至少为k的有向图中不交圈 470
    10.3.3 有向图的反馈集和线性序 472
    10.4 不交圈对反馈集的比较 476
    10.4.1 参数vi和Ti的关系 476
    10.4.2 Younger猜想的解决 477
    10.5 应用:Markov链的周期 480
    10.6 模p下的k长圈 482
    10.6.1 模下k长圈存在性问题的复杂度 482
    10.6.2 模p下k长圈存在的充分性条件 483
    10 7 半完全多部分有向图中的“短”圈 486
    10.8 半完全多部分有向图中圈对路的比较 489
    10.9 围长 493
    10.10 有关圈的补充专题 495
    10.10.1 圈的弦 495
    10.10.2 Adam猜想 496
    10.11 习题 498
    第11章 有向图的推广 501
    11.1 边着色多重图中的正常着色迹 501
    11.1.1 正常着色欧拉迹 503
    11.1.2 正常着色圈 506
    11.1.3 边着色多重图的连通性 509
    11.1.4 边着色二部分多重闯的交错圈 512
    11.1.5 2边着色完全多重图的最长交错路和圈 514
    11.1.6 c边着色完全图中正常着色哈密尔顿路(c≥3) 520
    11.1 7 c边着色完全图中正常着色哈密尔顿圈(c≥3) 521
    11.2 弧着色有向多重图 525
    11.2.1 交错有向圈问题的复杂性 526
    11.2.2 函数f(n)和函数g(n) 529
    11.2.3 弱欧拉弧着色有向多重图 531
    11.3 超竞赛图 532
    11.3.1 超竞赛图的出度序列 533
    11.3.2 哈密尔顿路 534
    11.3.3 哈密尔顿圈 535
    11.4 应用:遗传学中的交错哈密尔顿圈 536
    11.4.1 定理11.4.1的证明 538
    11.4.2 定理11.4.2的证明 539
    11.5 习题 540
    第12章 些重要的专题 542
    12.1 Seymour第二邻集猜想 542
    12.2 配对比较有向图的顶点排序 545
    12.2.1 配对比较有向图 545
    12.2.2 Kano-Sakamoto排序法 547
    12.2.3 半完全PCD的顶点排序 548
    12.2.4 相互序 549
    12.2.5 关于向前序和向后序的算法及其复杂性 549
    12.3 (k,l)核 552
    12.3.1 核 552
    12.3.2 拟核 554
    12.4 完全二部分有向图的列表边着色 555
    12.5 同态——着色的一个推广 558
    12.6 有向图独立性的其他度量法 563
    12.7 拟阵 565
    12.7.1 拟阵的对偶 567
    12.7.2 拟阵的贪婪算法 567
    12.7.3 独立性问答器 569
    12.7.4 拟阵的并 569
    12.7.5 二个拟阵的相交 570
    12.7.6 多个拟阵的相交 57l
    12.8 为NP困难问题寻找好解 572
    12.9 习题 575
    参考文献 580
    记号索引 616
    术语索引 625
    译后记 661
    《现代数学译丛》已出版书目 663
帮助中心
公司简介
联系我们
常见问题
新手上路
发票制度
积分说明
购物指南
配送方式
配送时间及费用
配送查询说明
配送范围
快递查询
售后服务
退换货说明
退换货流程
投诉或建议
版权声明
经营资质
营业执照
出版社经营许可证