下载文档原格式
中国矿业大学软件开发基础实践报告姓名： xxs 学号： bbaa0edf 专业：计算机科学与技术指导教师： sjc 职称： js(仅供徐海计算机参考哈哈哈哈)2012 年 6 月 20 徐州目录第一章实验概述 (3)1.1实验目的 (3)1.2实验内容 (3)1.3实验环境 (3)第二章实验原理和实现过程 (4)2.1实验原理 (4)2.1.1建立图的邻接矩阵，判断图是否连通 (4)2.1.2 计算任意两个结点间的距离 (4)2.1.3对不连通的图输出其各个连通支 (5)2.2实验过程（算法描述） (5)2.2.1 程序整体思路 (5)2.2.2具体算法流程 (5)第三章实验数据及结果分析 (7)3.1建立图的邻接矩阵并判断图是否连通的功能测试及结果分析 (7)3.1.1输入无向图的边 (7)3.1.2建立图的连接矩阵 (8)3.2其他功能的功能测试和结果分析 (9)3.2.1计算节点间的距离 (9)3.2.2判断图的连通性 (9)3.2.3输出图的连通支 (10)3.2.4退出系统 (10)第四章实验收获和心得体会 (11)4.1实验收获 (11)4.2心得体会 (12)第五章实验源程序清单 (13)5.1程序代码 (13)第一章实验概述1.1 实验目的理解图论的基本概念，图的矩阵表示，图的连通性，图的遍历，以及求图的连通支方法。
通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算，培养逻辑思维；通过实验提高学生编写实验报告、总结实验结果的能力，提高理论联系实际的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。
1.2 实验内容以偶对的形式输入一个无向简单图的边，建立该图的邻接矩阵，判断图是否连通（A），并计算任意两个结点间的距离（B），对不连通的图输出其各个连通支（C）。
注意：题目类型分为A，B，C三类，其中A为基本题，完成A类题目可达到设计的基本要求，其他均为加分题，并按字母顺序分数增加越高。
离散数学图论（图、树）常考考点知识点总结图的定义和表示1.图：一个图是一个序偶＜V , E ＞，记为G =< V ，E >，其中：① V ={V1,V2,V3,…, Vn}是有限非空集合，Vi 称为结点，V 称为节点集② E 是有限集合，称为边集，E中的每个元素都有V中的结点对与之对应，称之为边③与边对应的结点对既可以是无序的，也可以是有序的表示方法集合表示法，邻接矩阵法2.邻接矩阵：零图的邻接矩阵全零图中不与任何结点相邻接的结点称为孤立结点，两个端点相同的边称为环或者自回路3.零图：仅有孤立节点组成的图4.平凡图：仅含一个节点的零图无向图和有向图5.无向图：每条边都是无向边的图有向图：每条边都是有向边的图6.多重图：含有平行边的图(无向图中，两结点之间包括结点自身之间的几条边；有向图中同方向的边)7.线图：非多重图8.重数：平行边的条数9..简单图：无环的线图10.子图，真子图，导出子图，生成子图，补图子图：边和结点都是原图的子集，则称该图为原图的子图真子图（该图为原图的子图，但是不跟原图相等）11.生成子图：顶点集跟原图相等，边集是原图的子集12.导出子图：顶点集是原图的子集，边集是由顶点集在原图中构成的所有边构成的图完全图（任何两个节点之间都有边）13.完全图：完全图的邻接矩阵主对角线的元素全为0，其余元素都是114.补图：完全图简单图15.自补图：G与G的补图同构，则称自补图16.正则图：无向图G=<V,E>,如果每个顶点的度数都是k，则图G称作k-正则图17.结点的度数利用邻接矩阵求度数：18.握手定理：图中结点度数的总和等于边数的两倍推论：度数为奇数的结点个数为偶数有向图中，所有结点的入度=出度=边数19.图的度数序列：出度序列+入度序列20.图的同构：通俗来说就是两个图的顶点和边之间有双射关系，并且每条边对应的重数相同（也就是可任意挪动结点的位置，其他皆不变）21.图的连通性及判定条件可达性：对节点vi 和vj 之间存在通路，则称vi 和vj 之间是可达的22.无向图的连通性：图中每两个顶点之间都是互相可达的23..强连通图：有向图G 的任意两个顶点之间是相互可达的判定条件：G 中存在一条经过所有节点至少一次的回路24.单向连通图：有向图G 中任意两个顶点之间至少有一个节点到另一个节点之间是可达的判定条件：有向图G 中存在一条路经过所有节点25.弱连通图：有向图除去方向后的无向图是连通的判定条件：有向图邻接矩阵与转置矩阵的并是全一的矩阵26.点割：设无向图G=<V,E>为联通图，对任意的顶点w  V,若删除w及与w相关联的所有边后，无向图不再联通，则w称为割点；27.点割集：设无向图G=<V,E>为连通图，若存在点集 ，当删除 中所有顶点及与V1顶点相关联的所有边后，图G不再是联通的；而删除了V1的任何真子集 及与V2中顶点先关的所有边后，所得的子图仍是连通图，则称V1是G的一个点割集设无向图G=<V,E>为连通图，任意边e  E,若删除e后无向图不再联通，则称e 为割边，也成为桥28.边割集：欧拉图，哈密顿图，偶图（二分图），平面图29.欧拉通路（回路）：图G 是连通图，并且存在一条经过所有边一次且仅一次的通路（回路）称为拉通路（回路）30.欧拉图：存在欧拉通路和回路的图31.半欧拉图：有通路但没有欧拉回路32.欧拉通路判定：图G 是连通的，并且有且仅有零个或者两个奇度数的节点欧拉回路判定：图G 是连通的，并且所有节点的度数均为偶数有向欧拉图判定：图G 是连通的，并且所有节点的出度等于入度33.哈顿密图：图G 中存在一条回路，经过所有点一次且仅一次34..偶图：图G 中的顶点集被分成两部分子集V1,V2，其中V1nV2= o ,V1UV2= V ，并且图G 中任意一条边的两个端点都是一个在V1中，一个在V2中35.平面图：如果把无向图G 中的点和边画在平面上，不存在任何两条边有不在端点处的交叉点，则称图G 是平面图，否则是非平面图36.图的分类树无向树和有向树无向树：连通而不含回路的无向图称为无向树生成树：图G 的某个生成子图是树有向树：一个有向图，略去所有有向边的方向所得到的无向图是一棵树最小生成树最小生成树：设G -< V . E 是连通赋权图，T 是G 的一个生成树，T 的每个树枝所赋权值之和称为T 的权，记为W ( T . G 中具有最小权的生成树称为G 的最小生成树最优树（哈夫曼树）设有一棵二元树，若对所有的树叶赋以权值w1,w2… wn ，则称之为赋权二元树，若权为wi 的叶的层数为L ( wi )，则称W ( T )= EWixL ( wi ）为该赋权二元树的权，W ）最小的二元树称为最优树。
离散数学有向图的路径表示方法有向图是离散数学中的一个重要概念，它由一组顶点和一组有向边组成。
在有向图中，每条边都有一个方向，表示从一个顶点指向另一个顶点。
有向图可以用于表示不同实际问题中的关系和流程，因此了解有向图的路径表示方法对于解决问题至关重要。
在离散数学中，有向图的路径表示方法有多种，以下将介绍三种常见的方法，分别是邻接矩阵表示法、邻接表表示法和关联矩阵表示法。
1. 邻接矩阵表示法：邻接矩阵是一个二维矩阵，用于表示有向图中各顶点之间的关系。
矩阵的行和列代表图中的顶点，矩阵中的元素表示对应顶点之间是否存在直接连接的边。
如果两个顶点之间存在边，则对应的矩阵元素为1；如果两个顶点之间不存在边，则对应的矩阵元素为0。
例如，对于一个有向图G，如果存在一条从顶点A到顶点B的边，则在邻接矩阵中的第A行第B列的元素为1。
邻接矩阵表示法可以通过矩阵的行、列索引来表示有向图中的路径，路径上的顺序即为顶点在矩阵中的索引顺序。
2. 邻接表表示法：邻接表是一种更加紧凑的表示有向图的方法。
它由一个顶点数组和一个边链表组成。
顶点数组中的每个元素表示图中的一个顶点，边链表中的每个节点表示从该顶点出发的边。
邻接表使用链表的方式记录每个顶点所连接的边，其中链表的节点保存了边的终点以及指向下一条边的指针。
在邻接表表示法中，可以通过遍历链表来获取某个顶点的所有直接连接的顶点，从而表示有向图中的路径。
遍历链表的顺序即为顶点与顶点之间路径的顺序。
3. 关联矩阵表示法：关联矩阵是一个二维矩阵，用于表示有向图中顶点和边之间的关系。
矩阵的行代表顶点，矩阵的列代表边，矩阵中的元素表示对应顶点与边之间的连接关系。
关联矩阵表示法可以将有向图中的路径转化为矩阵中的非零元素组成的向量。
矩阵中的每一列表示一条边，矩阵中的每一行表示一个顶点。
如果某个顶点在路径上通过某条边，则对应的矩阵元素为-1；如果某个顶点是路径的起点，则对应的矩阵元素为1；如果某个顶点是路径的终点，则对应的矩阵元素为-1。
命题：称能判断真假的陈述句为命题。
命题公式：若在复合命题中，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是一个二元关系。
