文档介绍：程序设计领域里,每一个人都想飞。
但是,还没有学会走之前,连怕跑都别想!
勿在浮沙筑高台!
19 八月 2017
19 八月 2017
图论基础知识讲解
该材料用于图论第1讲课图论基础知识讲解环节
图论
图论是组合和离散数学最重要的分支之一,也是计算机基础理论科学的重要部分。它以图为研究对象。在理论计算机科学、运筹学、系统科学和数学中都有重要的地位。
而信息科学和生物科学已成为当今科学和经济发展的核心和主要动力,也因此大大推动了以研究离散和组合问题为主要对象的图论的发展
图论
一个图就是一个离散的拓扑结构,经常用于描述和研究许多领域中的各种问题。
随着计算机科学的飞速发展,图论组合和算法的研究在近代也成为计算机科学和数学中发展最快的基础学科之一,也受到国际上的学术界和高新技术企业方面特别重视。
图论
理论计算机科学中的算法理论经典问题(图中点对之间最短路,货郎担问题,图重抅问题,HAMILTON 问题,P-NP问题等),通信网络通讯(网络设计, 通讯速度和容量, 网络可靠性和容错性等) ;
在基础理论方面的著名四色定理和各种染色问题,极值理论及树、路和圈问题,HAMILTON理论等);
网络流、组合最优化等运筹学问题;任务人员安排等管理科学和系统科学的问题以及在物理,化学,社会学,语言学,生物学等领域的大量应用问题。
图论
图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。
图论本身是应用数学的一部份,因此,历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中,他所考虑的原始问题有很强的实际背景
图论
图论起源于著名的哥尼斯堡七桥问题。
欧拉证明了这个问题没有解,并且推广了这个问题,给出了对于一个给定的图可以某种方式走遍的判定法则。
这项工作使欧拉成为图论〔及拓扑学〕的创始人。
图论
1859年,英国数学家哈米尔顿发明了一种游戏:用一个规则的实心十二面体,它的20个顶点标出世界著名的20个城市,要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路,即「绕行世界」。
用图论的语言来说,游戏的目的是在十二面体的图中找出一个生成圈。这个问题后来就叫做哈密顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题,从而引起广泛的注意和研究。
图论
在图论的历史中,还有一个最著名的问题——四色猜想。
这个猜想说,在一个平面或球面上的任何地图能够只用四种颜色来着色,使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成,而两个国家相邻是指它们有一段公共的边界,而不仅仅只有一个公共点。四色猜想有一段有趣的历史。
图论
每个地图可以导出一个图,其中国家都是点,当相应的两个国家相邻时这两个点用一条线来连接。所以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。
四色猜想的提出来自英国。1852年,,发现了一种有趣的现象:“看来,每幅地图都可以用四种颜色着色,使得有共同边界的国家都被着上不同的颜色。