图论的论文开题报告

本文首发于 2017-11-14 19:07 原地址： 区块链当中一个重要分支就是密码学。而密码学当中涉及到相当的数学知识。密码学和数学的关系可谓深之又深，甚至可以说信息安全的很大基石就是数学（密码学是信息安全中的一部分）。图论（Graph Theory）是数学的一个分支，属于应用数学，其以图为研究对象。 区块链当中一个重要分支就是密码学。而密码学当中涉及到相当的数学知识，比如：数论、初等数学、代数学、组合数学以及概率论等。若没有一点数学基础的话，密码学的研究将是进行不通的。密码学和数学的关系可谓深之又深，甚至可以说信息安全的很大基石就是数学（密码学是信息安全中的一部分）。学习和掌握一些数学知识是必要的，在此我主要分享一些有关于密码学的数学知识。 图论 （Graph Theory）是数学的一个分支，属于 应用数学 ，其以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定的关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论的概念和结果来源非常广泛，既有来自生产实践的问题，也有来自理论研究的问题。历史上参与研究图论问题的人既有著名的数学家也有普通的业余爱好者。 谈到图论不得不提的就是著名的 哥尼斯堡七桥问题 。在贯穿古普鲁士哥尼斯堡城的普瑞格尔河上有七座桥连接两岸及河中的两个小岛，当地居民都很喜欢去岛上游玩，但有一个问题困扰着当地居民了很长的时间。在1736年，该市的一位市民向大数学家 欧拉 （Euler）提出了此问题。该问题是，从家里出发，七座桥每座桥都恰好通过一次，然后再回到家里，是否可以办到。事实上，当地居民以前曾反反复复试验了多次，不论怎么样行走，都不能成功的实现每座桥恰好只经过一次，但却没有人严格证明过。 欧拉将两岸分别用B和C两点进行表示，两岛分别用A和D来表示，A、B、C、D各点的位置并不重要，仅当两块陆地之间有桥时，把每座桥用连接对应点的一条边代替，每条边的曲直长短也不重要，于是欧拉将上图的实际场景抽象为下图，并且将此图形称为 图 （graph）。为了解决这个具体的问题，欧拉提出了判定一般图存在这种走法的充要条件，并给出了必要性证明，开创了图论（ 一维拓扑 ）的研究。这个结果发表于1736年，其把问题归结为一笔画问题，证明了从家里出发，七座桥每座桥都恰好通过一次，然后再回到家里，是不可以办到的。此论文被公认为第一篇图论文章，欧拉本人也被尊崇为图论和拓扑学之父。欧拉在解决此问题的同时给出了连通图可以一笔画的充要条件是：奇点的数目不是0个就是2个（连接到一点的数目如果是奇数条，就称为奇点，如果是偶数条就称为偶点，要想一笔画成必须中间点均是偶点，也就是说来去必须有对应，奇点只可能在两端，因此任何图如果要一笔画成，奇点要么没有要么在两端） 当时的数学界起初并未对欧拉解决七桥问题的意义有足够的认识，甚至有些人仅仅当其为一个数学游戏。图论诞生后并未及时获得足够的发展，直到200年后的1936年，匈牙利数学家科尼希出版了《有限图与无限图理论》，此为图论的第一部专著，其总结了图论200年的成果，是图论发展的第一座里程碑。此后，图论进入发展与突破的阶段，又经过了半个多世纪的发展，现已成长为数学科学的一个独立的重要学科。而且其分支很多，例如图论、算法图论、极值图论、代数图论、随机数图论、模糊图论、超图论等。特别值得一说的是，由于现代科学尤其是大型计算机的迅猛发展，使得图论大有用武之地，无论是数学、物理、化学、地理、生物等基础科学，还是信息、交通、战争、经济乃至社会科学的众多问题，都可以应用图论方法予以解决。当然， 图论也是计算机科学最重要的基础之一 。 注：一笔画        1）凡是由偶点组成的连通图，一定可以一笔画成。画时可以将任意一偶点作为起点，最后一定可以以此点为终点画完此图。        2）凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须将一个奇点作为起点，而另一个奇点将为终点。 3）其它情况的图都不能一笔画出。 // 奇点数除以二便可以算出此图需要几笔才能画成。 注： 欧拉通过对七桥问题的研究，不仅解决了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们将之称为 欧拉定理 。对于一个连通图，通常把某点出发        一笔画所经过的路线叫 欧拉路 ，同时将一笔画成又回到出发点的欧拉路称为 欧拉回路 ，而具有欧拉回路的图被称为 欧拉图 。 于中阳 Mercina-zy

方案名称：智能排课系统。方案目的：利用计算机替代传统的繁琐的手工排课方法。方案阐述：本系统受游戏设计中A星算法中的广度搜索法启发，结合手中的文献，总结出来的一种排课方式。本方案先采用采用信息收集的方式，收集信息。然后利用回逆算法进行智能排课。最后，再进行适当的人为调整，即可生成符合要求的课表。方案详解：当需要生成课表时，用户需先设定排课条件。基本条件有：周课时设置，课程信息，班级信息，教师信息，场地信息，教学计划（即那些老师教那些班级、可以选择的空教室、是否有合班课等信息）。将所有信息存入数据库。自动排课，即系统自动调用数据库收集的信息然后利用设定的算法进行排课。最后，将系统生成的课表进行差错检查，分别在班级信息，教师信息，场地信息表中检测其有无冲突。然后进行查看和手工调课。最后生成所需求的课表。算法详解：回溯是一种优先搜索法。它按优先条件向前搜索，以达到目标，但当搜索到某一步时，发现原先的选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回的技术为回溯法，而满足回溯条件的某个状态点称之为回溯点。具体到计算机智能排课系统中，选优条件即为排课数学模型中的约束条件群（需求集中的元素特征与资源集中的元素特征相互作用形成的数学关系）。换言之，若不满足约束条件群，该选择即为不优或达不到目标。当遍历该步骤的所有可能仍未满足约束条件群，则该状态满足了回溯条件，该状态点即为回溯点。下图即为回溯算法排课流程。值得指出的是，当得到第一次满足选优条件的排课结果后，可以将课表输出到屏幕上，由系统管理员直接审视排课结果，若感觉不满意，则可回到第一次得出的排课结果，将该状态设为回溯点，继续运行该算法，可以得到另一种排课结果，直至程序管理员满意为止。当然，也有可能使用该法遍历了所有的可能，仍无满足选优条件之排课结果，此时，计算机就根据反馈的结果，自动放宽约束条件，重新进行排课。该排课系统已在实际应用，排课结果较为理想，并且充分发挥了运算速度快的特点。 计算机自动排课也需要进行人工干预，以便可以使得各个高校能够根据自己的具体要求对排课算法中的一些参数进行设置和调整，并对计算机排出的课表进行调整．本算法所设计的人工干预过程有：等价类划分中参数的设置，教室类型的设置，时间模式库的设置，优先级函数中参数的设置．用户可以根据自己的具体要求对这些参数和库进行设置．另外，对于计算机排出的课程表，用户也可以通过人机交互进行适当调整，从而得到用户满意的课程表．参考文献：《高校智能排课系统文献综述》 作者，日期不详。 《以代理人为基础的中学排课系统研究》台湾高雄师大学 杨锦潭 欧文性PS: 本人经过几天了解和获得老师的指点，觉得该系统如何能使用数据结构图和离散数学中的图论解决会能具有可操作性和智能性。另外，本人认为可以设计一个信息采集的接口，用于采集一些教师的需求信息（例如：不想上某个时段的课程。）这样可以使整个信息更加人性化，但实现起来也比较有难度。知识水平有限，只能在我所能想到的范围进行思考。

可行性分析 近年来，网络管理技术的不断丰富和发展，为本课题的研究奠定了坚实的理论背景和相关技术支持。比如，web service理论在网络管理中的应用，使网络管理中的一些功能的开发实现变得简单易行。同时XML在网络管理中也有很多应用，其中XML schema作为网络接口的大数据量的传输载体，就可以应用到本项目中来存储网络配置信息。 总的来说，在此基础上，根据上述实验方案进行设计研究，思路是清晰的，研究方法是可行的。 四、本研究课题可能的创新之处(不少于500字) 本课题研究主要是为了解决在虚拟化网络管理中网络拓扑的构建问题、网络配置信息的生成问题，以及对虚拟网络可能出现故障及其引起的告警信息效果的模拟。本课题为实现此目标，在策略思想和关键技术上的创新点主要有以下几点。 1、首先，对于网络拓扑结构的生成，这里要研究的是根据网路的一组简单信息，模拟生成出一个网络可能的拓扑结构，这是非常有创新意义的。这里需要提出一个能够根据这些简单信息生成网络拓扑结构的算法，这一算法与现有的网络拓扑生成算法是有很大不同的。 2、在网络配置信息的生成过程中，是根据基本的信息模型，自动生成一组符合信息模型的网络配置信息数据，并且这些数据的关键字段都具有关联关系上的真实性和有效性。这里自动生成一组网络配置信息，破除了网络配置信息生成的局限性，降低了生成的复杂性，是虚拟网络配置信息的生成变得简单，充实而且准确。 3、故障信息的模拟中，可以根据故障，设定了一套衍生规则逻辑，来影响网络的运行效果。这一套逻辑，需要将模拟故障转化成负面的效果，体现在网络中。这需要建立新的仿真模拟的逻辑，提出合理有效的参数比较判断方法。 4、使用面向接口的方法编程仿真，更具灵活性。 综上所述，本课题的研究内容在思想和关键技术上主要有这四点创新之处。 五、研究基础与工作条件(1.与本项目相关的研究工作积累基础 2.包括已具备的实验条件，尚缺少的实验条件和拟解决途径)(不少于500字) 1、研究工作积累基础 本人所在实验室研究组的主要研究内容为web service接口技术在网络管理中的应用，在学习过程中，我在充分了解、学习了WSDL接口的定义，XML scheme信息模型的定义，有充分的理论知识储备。 另外，本人在研究组的网络管理原型系统构建的项目中，承担过一些涉及网络拓扑构建，网络配置信息呈现，以及网络故障告警信息的模拟检测和呈现工作。具备进行课题研究仿真的实践经验。 对如何进行原型系统开发进行了深入的学习，学习了开发时所需要用到的编程语言，比如java、JSP、XML等语言，为将来的课题模拟的开发工作打下了一定的基础。 所以，对于本课题的提出研究内容和方向，本人具备研究和建立原型系统进行仿真验证的能力。 2、已具备的实验条件及缺少的实验条件和拟解决途径 本课题研究，需要查找网络拓扑生成和故障仿真的相关资料和论文，学校的图书馆和网络资料数据库为此提供强大的支持。另外，对于课题需要仿真的工作，本人可以利用所在实验室研究组的服务器资源，进行实验环境的仿真构建和仿真原型系统的开发，本人所在研究组具备相关研究所用的仿真硬件环境。同时，实验室研究组的老师和同学们，也可以为本课题研究的内容做一些支持和帮助。 但是由于之前缺乏一些对网络拓扑生成算法相关图论知识的深入学习，需要进一步的了解和学习。本人有决心和能力做好这方面的学习和研究。 工科开题报告范文篇3： 基于仿真理论及虚拟化技术的虚拟覆盖网络模型研究 一、立题依据(包括研究目的、意义、国内外研究现状和发展趋势，需结合科学研究发展趋势来论述科学意义;或结合国民经济和社会发展中迫切需要解决的关键科技问题来论述其应用前景。附主要参考文献目录)(不少于800字) 研究目的 现有 Internet 网络功能强大，服务类型多样，但是随着网络规模指数型的增大，以及应用需求的多样化，我们也逐渐开始意识到Internet 正逐渐步入僵化。本文正是在这样的背景下提出了一个基于仿真理论及虚拟化技术的虚拟覆盖网络模型。 研究意义 对虚拟化覆盖网络的研究意义主要在于 Internet 的僵化已经不能适应网络指数级的增长以及用户的多样化服务需求。与此相反，虚拟化覆盖网络却能建立起一个更独立、更安全、更灵活、并能支持地理位置与用户身份分离的网络体系模型。这样，网络能够为用户提供更多的私有网络服务，包括应用层和应用层以下的各种服务。 国内外研究现状和发展趋势 在网络规模日益膨胀的今天，Internet架构已经开始出现僵化，当网络规模增大时，对硬件资源的消耗越来越厉害，而且当用户的需求变得多样化时比如，用户可能需要提供自己的私有服务，或者用户想建立自己的测试环境等，Internet 已不能很好地满足用户的需求。 本文提出的基于仿真理论及虚拟化技术的虚拟覆盖网络模型仍处于研究阶段，只是一个研究的模型。虽然对该网络进行了初步的仿真及性能参数评估，并探讨了该网络模型的实际应用，但要将其真正应用实际生活和科研中，或让其能应用于更多的系统，支持更多的网络新技术，还需要在多方面对虚拟覆盖网络模型进行完善。 二、研究内容和目标(说明课题的具体研究内容，研究目标和效果，以及拟解决的关键科学问题。此部分为重点阐述内容)(不少于2500字) 论文拟研究的方向，主要是为了解决Internet架构逐渐僵化问题、满足用户更多的需求。以仿真理论与虚拟技术为基础，对上述问题进行研究和编程测试，以期构建虚拟覆盖网络模型，以用于信息安全公共服务平台建设。 研究内容 本文首先对现有 Internet 体系结构进行了深入研究，既看到了 Internet 存在的意义，同时也看到了它的局限性，在网络规模日益膨胀的今天，Internet架构已经开始出现僵化，当网络规模增大时，对硬件资源的消耗越来越厉害，而且当用户的需求变得多样化时比如，用户可能需要提供自己的私有服务，或者用户想建立自己的测试环境等，Internet 已不能很好地满足用户的需求。 其次，本文对仿真理论进行了研究，并讨论了现有的一些主流网络仿真工具。 这对本文所提出的网络模型的仿真提供了有力的理论基础和实践手段，也是验证该网络模型可行性的必要前提。 由于虚拟化技术是本文的核心技术，因此，在第三章中还对网络虚拟化技术进行了详细讨论。对该技术的研究，有助于充分利用各种虚拟化技术的优势，建立一个合理的虚拟化网络模型。 在以上的这些研究的基础上，本文在第四章中提出了一个基于仿真理论及虚拟化技术的虚拟覆盖网络模型并给出了详细设计方案。该网络模型旨在使用户能够尽可能多地拥有对自己私有网络的控制权，使他们成为自己的“服务提供商”. 该网络模型能够为用户建立起一个具有更高独立性、安全性、灵活性，并具有物理位置与用户身份分离特性的网络，这使得用户能够在自己的私有网络中提供或享用更多种多样的个人网络服务，这些服务不但包括应用层各项服务，还包含了应用层以下的各种服务。该模型的核心主要是基于虚拟化技术建立起来的，其中用到的虚拟化技术包括虚拟路由器技术、虚拟网卡技术、虚拟拓扑技术等等。虚拟设备技术是一种对硬件设备功能的软件仿真技术，而虚拟拓扑技术是指现实网络拓扑在虚拟网络环境中的虚拟映射技术，它能够提供给用户控制自己网络拓扑的接口。 在第五章中本文还讨论了该网络模型的实际应用。它的应用范围十分广泛，既可以用于个人用途，也可以用于组织机构建设网络的情况，还可以用于给网络研究人员对前沿的 网络技术 进行方便而灵活的实验和仿真。特别地，本文在对现有信息安全公共服务平台体系结构进行研究的基础上，给出了该网络模型在该平台中的应用，提出了新一代信息安全公共服务平台体系框架，为进一步发挥信息安全公共服务平台的优越性奠定了基础。 最后，本文采用 ns2 仿真技术对该网络模型进行了仿真，得出了对该网络性能参数的评估。同时还结合利用了 Planetlab 测试床，对该网络模型的系统参数也进行了评估，验证了该网络模型的可行性。 研究目标和效果 本课题的研究目标对应研究内容分为四部分： 首先，讨论了网络仿真技术，包括其研究背景和现有的一些主流网络仿真技术。 然后，着重介绍了虚拟化技术，并对网络虚拟化技术的实际应用进行了深入阐述。 接着，提出了虚拟覆盖网络模型体系结构，详细描述了其中的关键技术、网络模型的建立与实现机制，并给出了具体的网络通信实例。 另外，对该网络模型进行了仿真，并对相关指标进行了性能测试。结合现有的信息安全公共服务平台，提出了新一代信息安全公共服务平台体系结构。 拟解决问题 Internet 的优势是明显的，就是它能够为用户提供大量的服务，但是我们也不得不承认， Internet 的体系结构正使得它变得开始僵化。 首先，随着网络规模不断地增大，对硬件资源的消耗也逐渐开始呈指数级递增，于是即使是对 Internet 架构的很小改动，都会使得部署相当困难。例如，IPv6 虽然已经进入人们的视野很久了，但是由于技术上的原因，IPv6 迟迟不能推广使用。因此，Internet 不利于新型网络架构的研究及部署，它不但对需要大量的硬件资源消耗，而且部署周期相当长。 另外，用户的需求已不仅限于现有的 Internet 服务，他们的服务需求已变得越来越多样化。例如，Internet 的尽力包传送服务并不能满足商业中的关键服务或一些实时应用程序的需求。因此，Internet 已远远不能满足用户多样化的个人网络服务需求。 此外，Internet 的服务由 ISP 服务提供商进行管理和维护，这将使得有时对它的使用变得很不灵活。用户往往希望能够根据自己的需求建立起自己的网络拓扑，提供自己的私有网络服务等等。因此，Internet 不能向用户提供开放式的管理和竞争平台 .促使我们去寻求更好的网络架构解决方案，而虚拟覆盖网络模型能够很好的解决这些问题。 三、研究方案设计及可行性分析(包括：研究方法，技术路线，理论分析、计算、实验方法和步骤及其可行性等)(不少于800字)。 研究方案设计 1.研究方法 针对本课题的研究内容和特性，达到研究目标和完成毕业论文，采用如下的研究方法： (1)理论知识准备：采用文献调查法，利用学校图书馆、网上相关学术数据库等资源，来进一步了解具体的仿真理论和虚拟化技术主要内容;(2)改进技术和主要研究点确定：以生成虚拟覆盖网络模型为主要研究点，辅以该模型的模拟仿真研究;(3)技术调研：对课题中涉及的虚拟化技术相关基本原理，以及仿真理论进行学习，然后针对具体的技术方案进行技术调研，确定实现方式;(4)设计技术方案：在理论准备和技术调研的基础上，确定基于仿真理论及虚拟化技术确定技术实现方案;(5)实现并测试：理论与实践相结合，根据设计出的技术方案，对需要改进的关键部分进行仿真，验证方案的可行性;(6)完成论文：整理文献资料、代码和数据等，完成论文。 2、技术路线 首先介绍几种相关的虚拟技术，基于这些虚拟技术，将给出虚拟覆盖网络模型的架构。然后将会进一步讨论具体的设计和实现机制。另外，还给出了两个实例用于说明一个用户组内两个用户成员间的通信过程。 可行性分析 近年来，网络虚拟化技术的不断丰富和发展，为本课题的研究奠定了坚实的理论背景和相关技术支持。比如，虚拟设备技术的应用，这包括虚拟路由器技术(或虚拟交换机技术)和虚拟网卡技术。同时虚拟拓扑技术应用，实现了从现实世界向虚拟世界的映射。 总的来说，在此基础上，根据上述实验方案进行设计研究，思路是清晰的，研究方法是可行的。 四、本研究课题可能的创新之处(不少于500字) 本课题研究主要是为了解决在虚拟化技术下虚拟覆盖网络模型的构建问题，以及对虚拟覆盖网络模型的模拟仿真。本课题为实现此目标，在策略思想和关键技术上的创新点主要有以下几点。 (1)在深入分析现有Internet架构、和主流虚拟化技术的基础上，提出了具有更高独立性、安全性、灵活性，并具有物理位置与用户身份分离特性的虚拟覆盖网络模型，并给出了模型的框架和设计细节。该模型具有很广泛的应用前景。 (2)对现有信息安全公共服务平台体系结构的关键技术及其发展趋势和需求进行了深入分析，结合了本文中提出的虚拟覆盖网络模型，提出了新一代信息安全公共服务平台框架。 综上所述，本课题的研究内容在思想和关键技术上主要有这两点创新之处。 五、研究基础与工作条件(1.与本项目相关的研究工作积累基础 2.包括已具备的实验条件，尚缺少的实验条件和拟解决途径)(不少于500字) 1、研究工作积累基础 本人所在实验室研究组的主要研究内容为网络虚拟技术的应用开发，在学习过程中，我在充分了解、学习了虚拟化技术的定义，仿真理论的定义，有充分的理论知识储备。 另外，本人在研究组的网络原型系统构建的项目中，承担过一些涉及网络拓扑构建，网络配置信息呈现，以及网络信息的模拟检测和呈现工作。具备进行课题研究仿真的实践经验。 对如何进行原型系统开发进行了深入的学习，学习了开发时所需要用到的编程语言，比如java、JSP、XML等语言，为将来的课题模拟的开发工作打下了一定的基础。 所以，对于本课题的提出研究内容和方向，本人具备研究和建立原型系统进行仿真验证的能力。 2、已具备的实验条件及缺少的实验条件和拟解决途径 本课题研究，需要查找网络虚拟化技术和仿真的相关资料和论文，学校的图书馆和网络资料数据库为此提供强大的支持。另外，对于课题需要仿真的工作，本人可以利用所在实验室研究组的服务器资源，进行实验环境的仿真构建和仿真原型系统的开发，本人所在研究组具备相关研究所用的仿真硬件环境。同时，实验室研究组的老师和同学们，也可以为本课题研究的内容做一些支持和帮助。 但是由于之前缺乏一些对网络拓扑生成算法相关图论知识的深入学习，需要进一步的了解和学习。本人有决心和能力做好这方面的学习和研究。 主要参考文献 [1]喻健坤，杨树堂，陆松年，李铎峰，支持多用户并发访问控制的虚拟网络模型研究，信息技术，2007年第8期，1~2页。 [2] IEEE Std , Draft Standard for Virtual Bridge Local Area Networks,May 16, 1997. [3] IEEE Std , 2003 Edition IEEE Standards for Local and metropolitanarea networks Virtual Bridged Local Area Networks, May 7, 2003. [4] Dr. V. Rajaravivarma, North Carolina A&T State University, Virtual Local AreaNetwork Technology and Applications, System Theory, 1997., Proceedings of theTwenty-Ninth Southeastern Symposium on 9-11 March 1997 Page(s)：49 - 52. [5] P. Ferguson, G. Huston, What is a ?, Technical Report, Cisco Systems, March1998. [6] Stanford High-Performance Networking Group,Stanford Virtual NetworkSystem(VNS)。 [7] Martin Casado, Nick Mc Keown. The Virtual Network System, ACM SIGCSEBulletin, 2005, Volume 37, Pages 76 - 80. [8]王涛，用Net Sim组建虚拟网络实验室，长沙通信职业技术学院学报，2005年4卷3期，46-48页。 [9] Galan F., Fernandez D., Ruiz J., Walid O., Use of virtualization tools in computernetwork laboratories, Information Technology Based Higher Education andTraining, 2004. ITHET 2004. Proceedings of the FIfth International Conferenceon 31 May-2 June 2004, Page(s)：209 - 214. [10] L. Peterson, T. Roscoe, The design principles of Planetlab, ACM OperatingSystems Review, 40(1)， Jan. 2006.