离散数学引论

图书标准信息

• 作者 王树禾
• 出版社 中国科学技术大学出版社
• 出版时间 2001-09
• 版次 1
• ISBN 9787312013003
• 定价 18.00元
• 装帧 平装
• 开本 其他
• 纸张 胶版纸
• 页数 410页

【内容简介】

本书按硕士研究生教材定位写成，供数学、应用数学、计算机科学技术、信息等专业的研究生和需要较深离散数学的本科生选用。全书划分六篇，主要内容如下：

  图论与算法图论、组合论、代数系统、数理逻辑、离散数学中的空间、矩阵和拟阵、Turing机和计算复杂度理论，每篇配有难易适当的足够作业题。

   全书概念与理论明晰严谨，注重算法与应用，文字洗练生动，立论深入浅出，可读与可教性强。

【作者简介】

王树禾，河北乐亭人，1938年生，毕业于北京大学数学力学系，中国科学技术大学教授。科研与教学方向为离散数学和微分方程，发表数学论文30篇，出版数学著作17种，获中国科学技术大学校级优秀教师奖、中国科学院教学成果一等奖和国家级教学成果二等奖等奖项。

【目录】

序 言

第一篇 图及其算法

  1.1 什么是图论

  1.2 图的定义

  1.3 Brouwer不动点定理

  1.4 Dijkstra算法

  习题一

  1.5 树

  1.6 生成树

    1.6.1 生成树的个数

    1.6.2 最优生成树的Kruskal算法

  1.7 常用树

    1.7.1 有序二元树

    1.7.2 Huffman树

  习题二

  1.8 平面图

    1.8.1 平面图及其Euler公式

    1.8.2 对偶图和极大平面图

    1.8.3 Kuratowsky定理

    1.8.4 图的厚度

  习题三

  1.9 纵深搜索和平面嵌入算法

    1.9.1 广度优先与深度优先搜索算法

    1.9.2 求割顶和块的算法

    1.9.3 有向图的DFS和极大强连通子图的算法

    1.9.4 平面嵌入算法

  习题四

  1.10 匹配

    1.10.1 匹配理论

    1.10.2 二分图中最大匹配与最佳匹配的算法

  习题五

  1.11 图上遍历

    1.11.1 Euler图

    1.11.2 求Euler回路的算法

    1.11.3 中国邮路问题

    1.11.4 Harmihon图

  习题六

  1.12 色

    1.12.1 边色数

    1.12.2 顶色数与面色数

    1.12.3 色多项式

  习题七

  1.13 支配集.独立集和Ramsey数

    1.13.1 支配集和独立集

    1.13.2 a （G ）,B（G） ,Y （G） 的计算

    1.13.3 Ramsey数

    1.13.4 多元Ramsey数和Schur定理

  习题八

  1.14 有向图

    1.14.1 有向图的连通性

    1.14.2 有向轨与竞赛图

    1.14.3 有向圈与竞赛图

    1.14.4 有向Euler图

  习题九

  1.15 网络流

    1.15.1 Ford-Fulkerson最大流算法

    1.15.2 Dinic最大流算法

    1.15.3 有上下界的网络中的流

    1.15.4 有供需约束的流

    1.15.5 PERT问题

    1.15.6 流与二分图

  习题十

  1.16 连通度

    1.16.1 无向图的顶连通度

    1.16.2 有向图的顶连通度

    1.16.3 无向图的边连通度

    1.16.4 有向图的边连通度和弱独立外向生成树

    1.16.5 可靠通讯网络

  习题十一

第二篇 组合基础

  2.1 什么是组合论

  2.2 鸽笼原理

  2.3 +×原理与排列组合

    2.3.1 无重复的排列组合

    2.3.2 Catalan数

    2.3.3 可重复的排列组合

  习题一

  2.4 容斥原理

  习题二

  2.5 生成函数

    2.5.1 生成函数概念

    2.5.2 组合数的生成函数

    2.5.3 拆分自然数

    2.5.4 排列数的生成函数

  习题三

  2.6 递归方程

    2.6.1 递归方程的初值问题

    2.6.2 线性常系数递归方程的生成函数解法

    2.6.3 常系数线性齐次递归方程的特征值解法

    2.6.4 常系数线性非齐次递归方程的解

    2.6.5 递归方程的其它解法

    2.6.6 Stirling数

  习题四

第三篇 代数与计数

  3.1 代数系统及其性质

    3.1.1 代数系统的定义

    3.1.2 代数系统的同构与同态

  3.2 群.环.域

    3.2.1 群

    3.2.2 环

    3.2.3 域

  习题一

  3.3 置换群和循环群

    3.3.1 置换

    3.3.2 置换群与循环群

  3.4 Lagrange定理和Burnside定理

  3.5 Polya定理

  习题二

  3.6 图的群

    3.6.1 图的自同构群

    3.6.2 有限群的Cayley图

  习题三

第四篇 离散数学中的空间.矩阵和拟阵

  4.1 圈空间和断集空间

    4.1.1 圈空间

    4.1.2 断集空间

  4.2 关联矩阵和邻接矩阵

    4.2.1 关联矩阵

    4.2.2 邻接矩阵

  4.3 圈矩阵和割集矩阵

  4.4 开关网络分析

  习题一

  4.5 拟阵

    4.5.1 拟阵的概念

    4.5.2 拟阵理论

  习题二

  4.6 倒称矩阵与层次分析

  4.7 正交拉丁方

  4.8 区组设计与区组矩阵

    4.8.1 BIBD问题

    4.8.2 区组关联矩阵

    4.8.3 Hadamard矩阵

    4.8.4 区组设计的构作

  4.9 魔矩阵密码

  习题三

第五篇 不确定Turing机和计算的时间复杂度

  5.1 好算法和坏算法

  5.2 不确定Turing机和NP类问题

  5.3 NPC问题和Cook定理

  5.4 NPC中的组合问题

  5.5 NPC中的图论问题

  习题

第六篇 数理逻辑

  6.1 命题逻辑

    6.1.1命题及其真假

    6.1.2 联结词与命题公式

    6.1.3 真值表

    6.1.4 等价公式.代换定理与对偶定理

    6.1.5 范式

  6.2 命题逻辑中的推理

    6.2.1 蕴含关系

    6.2.2 真值表推理法

    6.2.3 直接推理法

    6.2.4 间接推理法

  习题一

  6.3 谓词逻辑

    6.3.1 命题的谓词表达形式

    6.3.2 量词

    6.3.3 谓词公式及其变元

    6.3.4 谓词逻辑中的等价定律.代入规则

  6.4 谓词逻辑中的推理

  习题二

参考文献