图论与代数实验报告.docx

《图论与代数实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论与代数实验报告学号：姓名：实验内容：根据离散数学第八章，解决欧拉回路问题和TSP问题。实验环境：VC++。实验过程与结果：一、问题简介：1、欧拉回路问题简介：欧拉回路要求通过图中每条边一次且仅一次,并且过每一顶点的回路。而判别一个图是否存在欧拉回路需要满足:1、图是连通的;2、图中的所有点均为偶度顶点。而对有向的欧拉图来说存在欧拉回路的条件为:图是连通的,并且图中的所有顶点的入度与出度相等。2、TSP问题简介：给出一个n个城市集合的图，给出城市间的距离。是否存在从某个城市出发，沿交通线经过每个城市一次，最后回到出发的城市。二、算法框图：1、欧拉回路：Fleury算法求

2、出欧拉回路判定各点度数是否为偶数广度优先搜索，判定是否连通创建图不是连通图否不是欧拉图否2、TSP问题：创建图建立回路矩阵便宜算法找到回路一、实验结果：1、欧拉回路实验：2、TSP回路实验：二、实验分析与总结：通过本次实验，实践了将算法通过编程实现，对于欧拉回路程序的编写过程中采用了矩阵的存储形式，首先对图进行了连通性检验，然后进行了是否是欧拉图的检验，最后用Flery算法求解出一条欧拉回路，程序的缺点是对同一个图所能求解的欧拉回路是相同的。对于TSP问题，也是采用的矩阵存储形式，然后对图进行便宜算法处理，最后的最短哈密顿回路用矩阵的方式给出，程序的缺点是变量过多，只接受

3、任意两个顶点有路径的图，适用性不高。