关于k-优美图的一些问题的-研究

《关于k-优美图的一些问题的-研究》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、哈尔滨T程大学硕十学位论文第1章绪论1．1图论的发展历史及应用1．1．1图论的发展历史图论的历史可以追溯到1736年瑞士数学家欧拉解决哥尼斯堡七桥问题．18世纪的哥尼斯堡城(现在叫加里宁格勒)中流过一条河，河上有七座桥连结着河的两岸和河中的两个小岛，如图1．1所示．图1．1哥尼斯堡桥一个游者怎样才能一次连续走过这七座桥而每座桥只走一次，回到原出发点?当时没有人想出这种走法，又无法说明走法不存在，这就是著名的“七桥"难题．瑞士数学家欧拉将这个问题归结为如图1．2所示的问题．他用四个点表示河的两岸和小岛，用两点间的连线

2、表示桥．七桥问题变为从四个点中的任意一个点出发，能否通过每条边一次且仅一次，再回到该点?图1．2七桥问题简图欧拉在1736年发表了一篇题为“依据几何位置的解题方法"的论哈尔滨T程人学硕十学位论文文，有效地解决了哥尼斯堡七桥难题，在这篇论文中，欧拉证明了走法是不存在的，并给出了这类问题的一般结论，这是有记载的第一篇图论论文，欧拉被公认为图论的创始人．但在随后的两百年里，图论的发展非常缓慢．这一时期，图论的研究主要集中在两个方面：一是如四色问题和Hamilton问题等一些图论难题；二是以图为工具去解决其它领域的问题．在

3、此期间，最具代表性的成果是Kirchhoff(1847年)和Cayley(1857年)分别用树的概念去研究电网络方程组和有机化合物的分子结构．进入二十世纪三十年代，图论出现了许多新理论和结果，如Menger定理(1927年)，Kuratowski定理(1930年)和Ramsey定理(1930年)等．这些理论和结果为图论的发展奠定了基础．1936年，匈牙利数学家O．K6nig出版了第一本图论专著《有限图和无限图理论》，标志着图论作为一个新的数学分支己经基本形成．1．1．2图论的应用图论作为数学领域罩一个新兴的分支，在

4、近几十年里发展十分迅速．它广泛应用于运筹学、计算机与信息科学、网络理论、生物化学、经济管理及社会科学等多个领域，例如运筹学中的“中国邮路问题”：一个邮递员从邮局出发要走遍他所负责的每条街道去送信，问如何选择适当的路线可使所走的总路程最短．这个问题就与欧拉回路有密切的关系．同时，图论与数学的其它分支，如群论、矩阵理论、概率论、数值分析等都有着密切联系．图论使用图解式的方法为包含二元关系的系统提供了一个数学模型，具有一种直观的、符合美学的外形，因而受到数学界和工程技术界，乃至经营决策管理者的极度重视，形成了图论迅猛发展

5、的局面．图的结构性质作为图论研究的一个主要内容，具有重要的理论及应用价值．如：大规模集成电路(LSI)的分析与设计，印刷电路板的设计与柿线，传递网络和通讯网络稳定性与可靠性研究等，都是利用图的结构性质指导实际工程技术．在计算机等电子设备中，大量2哈尔滨T程大学硕十学位论文使用着集成电路和大规模集成电路，在这样复杂的大规模电子线路的分析中，人们利用图论的相关理论使电路设计实现了程序化，还有，在电路设计中，图论也起了作用．在电路描述中，如果用有向图表示元件的连接关系及其电压、电流的方向和数值，贝0可以使得电路方程式的求

6、解得以简化．图论也被应用于配置、安装零件的印刷电路板的设计与布线问题中．例如，在底板的板面上，线不能交叉，这就是图论中图的可平面性．图的可平面性的判定算法起着有效的作用．由于交通、通讯网的飞速发展，整个世界变得非常密切、便利，同时也更复杂更多样化起来．电话线路网、计算机网络、管道网、交通网等所谓网络流问题都随着对图论的研究的发展而发展．在通讯网中，图论中的割集起着重要的作用．例如，两顶点间流动的最大量(端子间容量)，用图论中的割集便可完全确定(最大流一最小割定理)．在组合电路和顺序电路中，也广泛应用了图论．把变量与

7、图的边对应，用图的连接矩阵来表示开关电路，对开关电路进行分析；把变量与项点相对应而表示数字电路，既能求出它的拓扑性质，又能进行分析，甚至还能应用于设计．在电路的故障诊断中更依赖于图形的建立．信号流图是表示信号在整个线路(信道)中传输状态的图，信号通过线路进入中继站(局)沿通向其他各站(局)所有线路传输．这种图能很好地表现出线性系统的物理意义，故在系统研究中被广泛使用．信号流图不仅有助于联立方程组的求解，对于分析由一阶线性微分方程组的状态方程的过渡过程和自动控制问题同样有效．现代社会的政治、经济、工业等领域，无论哪一

8、个领域，都有复杂化和大规模化的趋向．在这样的背景下，以种种条件和制约为基础的效果的规划、运用、管理和买卖等的技巧发展起来了．运筹学、博弈论、用于工程管理的计划鉴定检查法、关键工序路线法、线性规划等科学手法也陆续出现了．然而，在这些方法中都引入了图论的相关理论，例如，若把复杂的工程用有向图表示，由于最长路径决定着整个工程所需3哈尔滨T程大学硕+学何论文要的天数