离散数学-图的矩阵表示

《离散数学》期末复习大纲一、数理逻辑[复习知识点]1、命题与联结词（否定￢、析取∨、合取∧、蕴涵→、等价?），复合命题2、命题公式与赋值（成真、成假），真值表，公式类型（重言、矛盾、可满足），公式的基本等值式3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法）5、命题逻辑的推理理论6、谓词、量词、个体词（一阶逻辑3要素）、个体域、变元（约束出现与自由出现）7、命题符号化、谓词公式赋值与解释，谓词公式的类型（永真、永假、可满足）8、谓词公式的等值式（代换实例、消去量词、量词否定和量词辖域收与扩、量词分配）和置换规则（置换规则、换名规则）9、一阶逻辑前束范式（定义、求法）本章重点内容：命题与联结词、公式与解释、（主）析取范式与（主）合取范式、公式类型的判定、命题逻辑的推理、谓词与量词、命题符号化、谓词公式赋值与解释、求前束范式。

[复习要求]1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。

2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。

3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。

4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。

5、掌握命题逻辑的推理理论。

6、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；掌握命题的符号化。

7、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。

8、掌握求一阶逻辑前束范式的方法。

二、集合[复习知识点]1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补以及对称差等运算及有穷集的计数（文氏（Venn）图、包含排斥原理）3、集合恒等式（幂等律、交换律、结合律、分配律、吸收律、矛盾律、德摩根律等）及应用本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明。

图谱简介图论与组合是一门历史悠久而在近四十年又获得蓬勃发展的应用数学学科，是处理离散问题的强有力的工具，是整个离散数学的一个重要组成部分。

图论与组合包含着十分丰富的内容，按其所研究的问题的侧重点不同，可以分为图论、计数理论、组合矩阵论、最优化理论、组合设计等几个方面。

近五十年来，随着计算机科学、信息科学和系统科学的发展，图论组合及其应用的研究越来越引起人们的关注。

无论从其理论价值和实际应用的广度和深度来看，图论与组合正处于一个具有强大生命力的迅速发展的新时期。

一．图的矩阵在图论中，为了研究图的性质，人们引进了各种各样的矩阵，诸如图的邻接矩阵，拉普拉斯矩阵，规范拉普拉斯矩阵等，这些矩阵与图都有着自然的联系，代数图论的一个主要问题就是研究图的性质能否以及如何由这些矩阵的代数性质反映出来，这里所指的矩阵的代数性质，主要指矩阵的特征值。

图谱理论主要研究图的邻接矩阵、拉普拉斯矩阵和规范拉普拉斯矩阵的特征值及其特征向量，是当前代数图论、组合矩阵论和代数组合论共同关注的一个重要研究课题，极大地丰富和促进了图论和组合学的研究内容。

假设),(E V G =是一个无向无环的图（简单图或多重图），其中{}n v v v V ,,,21 =，{}m e e e E ,,,21 =。

定义1 G 的邻接矩阵是一个n n ⨯的矩阵n n ij a G A ⨯=)()(，其中ij a 是连接顶点i v 与j v 的边的条数。

图的邻接矩阵的特征值，是代数图论的一个基本研究课题，已经形成相当成熟的理论。

图谱的第一篇论文发表于1957 年，其结果是.定理1 令G 是n 个结点的简单连通图，则1)(1cos 2-≤≤+n G n ρπ，左边的等号成立，当且仅当G 是一路；右边的等号成立，当且仅当G 是一个完全图。

在国内该方面的研究直到1979年才出现了第一篇论文，该论文由李乔和冯克勤合写并发表在1979年的《应用数学学报》上。

代表人物: C. D. Cvetkovic.专 著：D. M. Cvetkovic, M. Doob, and H. Sachs, Spectra of graph-theory and applications, VEB Deutscher Verlag d. Wiss. Berlin, 1979; Acad. Press, New York, 1979. 1995注：1．)()(),(k ijk ij k a a A = 表示 G 中点 i v 到 j v 长为 k 的路的数目—数学归纳法。

“离散数学”实验报告目录一、实验目的 (3)二、实验内容 (3)三、实验环境 (3)四、实验原理和实现过程（算法描述） (3)1、实验原理........................................................................................................2、实验过程.......................................................................................................五、实验数据及结果分析 (13)六、源程序清单 (24)源代码 (24)七、其他收获及体会 (45)一、实验目的实验一：熟悉掌握命题逻辑中的联接词、真值表、主范式等，进一步能用它们来解决实际问题。

实验二：掌握关系的概念与性质，基本的关系运算，关系的各种闭包的求法。

理解等价类的概念，掌握等价类的求解方法。

实验三：理解图论的基本概念，图的矩阵表示，图的连通性，图的遍历，以及求图的连通支方法。

二、实验内容实验一：1. 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、条件和双条件的真值。

（A）2. 求任意一个命题公式的真值表（B，并根据真值表求主范式（C））实验二：1.求有限集上给定关系的自反、对称和传递闭包。

（有两种求解方法，只做一种为A，两种都做为B）2. 求有限集上等价关系的数目。

（有两种求解方法，只做一种为A，两种都做为B）3. 求解商集，输入集合和等价关系，求相应的商集。

（C）实验三：以偶对的形式输入一个无向简单图的边，建立该图的邻接矩阵，判断图是否连通（A）。

并计算任意两个结点间的距离（B）。

对不连通的图输出其各个连通支（C）。

三、实验环境C或C＋＋语言编程环境实现。

四、实验原理和实现过程（算法描述）实验一：1.实验原理（1）合取：二元命题联结词。

1.内容及范围主要来自 ppt，标签对应书本2.可能有错，仅供参考离散数学知识点说明：定义：红色表示。

定理性质：橙色表示。

公式：蓝色表示。

算法: 绿色表示页码：灰色表示数理逻辑：1.命题公式：命题，联结词(⌝，∧，∨，→，↔)，合式公式，子公式2.公式的真值：赋值，求值函数，真值表，等值式，重言式，矛盾式3.范式：析取范式，极小项，主析取范式，合取范式，极大项，主合取范式4.联结词的完备集：真值函数，异或，条件否定，与非，或非，联结词完备集5.推理理论：重言蕴含式，有效结论，P 规则，T 规则， CP 规则，推理6.谓词与量词:谓词，个体词，论域，全称量词，存在量词7.项与公式:项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入8.公式语义:解释，赋值，有效的，可满足的，不可满足的9.前束范式:前束范式10.推理理论:逻辑蕴含式，有效结论，∀-规则（US），∀+规则（UG），∃-规则(ES)，∃+规则(EG), 推理集合论：1.集合: 集合, 外延性原理, ∈, ⊆, ⊂, 空集, 全集, 幂集, 文氏图, 交, 并, 差, 补, 对称差2.关系: 序偶, 笛卡尔积, 关系, domR, ranR, 关系图, 空关系, 全域关系, 恒等关系3.关系性质与闭包:自反的, 反自反的, 对称的, 反对称的, 传递的,自反闭包 r(R),对称闭包 s(R), 传递闭包 t(R)4.等价关系: 等价关系, 等价类, 商集, 划分5.偏序关系:偏序, 哈斯图, 全序(线序), 极大元/极小元, 最大元/最小元, 上界/下界6.函数: 函数, 常函数, 恒等函数, 满射,入射,双射，反函数, 复合函数7.集合基数:基数, 等势, 有限集/无限集, 可数集, 不可数集代数结构：1.运算及其性质：运算，封闭的,可交换的,可结合的,可分配的,吸收律, 幂等的，幺元,零元,逆元2.代数系统：代数系统，子代数，积代数，同态，同构。

命题：称能判断真假的陈述句为命题。

命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。

命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。

给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。

若指定的一组值使A的值为真，则称成真赋值。

真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。

将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。

命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。

（2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。

（3）若A至少存在一组赋值是成真赋值，则A是可满足式。

主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。

主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。

命题的等值式：设A、B为两命题公式，若等价式A↔B是重言式，则称A与B是等值的，记作A<=>B。

约束变元和自由变元：在合式公式∀x A和∃x A中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。

一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A↔B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。

前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Q k…x k B，称A为前束范式。

集合的基本运算：并、交、差、相对补和对称差运算。

笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。

二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。