离散数学图论3图矩阵表示

《离散数学》期末复习大纲一、数理逻辑[复习知识点]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.命题公式:命题, 联结词(,，，，），合式公式,⼦公式2.公式的真值：赋值，求值函数,真值表,等值式，重⾔式,⽭盾式3.范式：析取范式，极⼩项,主析取范式，合取范式，极⼤项,主合取范式4.联结词的完备集：真值函数，异或,条件否定，与⾮,或⾮，联结词完备集5.推理理论：重⾔蕴含式,有效结论,P规则,T规则, ＣP规则，推理6.谓词与量词:谓词，个体词,论域,全称量词,存在量词7.项与公式:项，原⼦公式，合式公式，⾃由变元,约束变元，辖域，换名，代⼊8.公式语义:解释，赋值,有效的，可满⾜的,不可满⾜的9.前束范式:前束范式10.推理理论:逻辑蕴含式，有效结论，-规则(US)，+规则(ＵG), -规则(ＥS)，+规则(ＥG), 推理集合论：1.集合: 集合, 外延性原理, , , , 空集, 全集, 幂集，⽂⽒图, 交, 并，差, 补, 对称差2.关系: 序偶, 笛卡尔积, 关系, ｄomR，ｒａnR，关系图, 空关系, 全域关系，恒等关系3.关系性质与闭包：⾃反的, 反⾃反的，对称的, 反对称的, 传递的，⾃反闭包 r(R),对称闭包 s(R），传递闭包 t(Ｒ)4.等价关系: 等价关系, 等价类, 商集, 划分5.偏序关系:偏序，哈斯图，全序（线序), 极⼤元／极⼩元，最⼤元／最⼩元，上界/下界6.函数: 函数，常函数, 恒等函数, 满射,⼊射，双射,反函数，复合函数7.集合基数：基数, 等势，有限集／⽆限集，可数集, 不可数集代数结构:1.运算及其性质：运算,封闭的，可交换的,可结合的,可分配的,吸收律, 幂等的,⼳元,零元,逆元2.代数系统:代数系统，⼦代数,积代数,同态,同构。

3.群与⼦群:半群,⼦半群,元素的幂，独异点，群，群的阶数，⼦群,平凡⼦群，陪集,拉格朗⽇(Lａgranｇe)定理4.阿贝尔群和循环群：阿贝尔群(交换群),循环群，⽣成元5.环与域：环，交换环,含⼳环,整环,域6.格与布尔代数：格，对偶原理,⼦格,分配格,有界格,有补格，布尔代数,有限布尔代数的表⽰定理图论:1.图的基本概念：⽆向图、有向图、关联与相邻、简单图、完全图、正则图、⼦图、补图,握⼿定理，图的同构2.图的连通性：通路，回路，简单通路,简单回路(迹）初级通路（路径)，初级回路（圈），点连通,连通图，点割集，割点，边割集，割边，点连通度,边连通度，弱连通图，单向连通图，强连通图,⼆部图(⼆分图）3.图的矩阵表⽰:关联矩阵，邻接矩阵，可达矩阵4.欧拉图与哈密顿图：欧拉通路、欧拉回路、欧拉图、半欧拉图，哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图5.⽆向树与根树：⽆向树，⽣成树,最⼩⽣成树,Krｕskaｌ,根树，m叉树，最优⼆叉树,Huffman算法6.平⾯图:平⾯图,⾯，欧拉公式,Kuｒatoski定理数理逻辑：命题：具有确定真值的陈述句。

第四篇图论自从1736年欧拉（）利用图论的思想解决了哥尼斯堡（Konigsberg）七桥问题以来，图论经历了漫长的发展道路。

在很长一段时期内，图论被当成是数学家的智力游戏，解决一些著名的难题。

如迷宫问题、匿门博奕问题、棋盘上马的路线问题、四色问题和哈密顿环球旅行问题等，曾经吸引了众多的学者。

图论中许多的概论和定理的建立都与解决这些问题有关。

1847年克希霍夫（Kirchhoff）第一次把图论用于电路网络的拓扑分析，开创了图论面向实际应用的成功先例。

此后，随着实际的需要和科学技术的发展，在近半个世纪内，图论得到了迅猛的发展，已经成了数学领域中最繁茂的分支学科之一。

尤其在电子计算机问世后，图论的应用范围更加广泛，在解决运筹学、信息论、控制论、网络理论、博奕论、化学、社会科学、经济学、建筑学、心理学、语言学和计算机科学中的问题时，扮演着越来越重要的角色，受到工程界和数学界的特别重视，成为解决许多实际问题的基本工具之一。

图论研究的课题和包含的内容十分广泛，专门著作很多，很难在一本教科书中概括它的全貌。

作为离散数学的一个重要内容，本书主要围绕与计算机科学有关的图论知识介绍一些基本的图论概论、定理和研究内容，同时也介绍一些与实际应用有关的基本图类和算法，为应用、研究和进一步学习提供基础。

第4-1章 无向图和有向图学习要求：仔细领会和掌握图论的基本概论、术语和符号，对于图论研究的一些最基本的课题，如道路问题、连通性问题和着色的问题等，应掌握主要的定理内容和证明方法以及基本的构造方法，以便为下一章研究提供理论工具。

学习本章要用到集合和线性代数矩阵运算的知识，特别是集合数和矩阵秩的概念。

§4-1-1 图的基本概念图是用于描述现实世界中离散客体之间关系的有用工具。

在集合论中采用过以图形来表示二元关系的办法，在那里，用点来代表客体，用一条由点a 指向点b 的有向线段来代表客体a 和b 之间的二元关系aRb ，这样，集合上的二元关系就可以用点的集合V 和有向线的集合E 构成的二元组（V ，E ）来描述。