资源描述：
《离散数学第7章+图论1图的基本概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第7章图论胡敏合肥工业大学计算机与信息学院计算机应用研究所第七章图论引言7.1图的基本概念7.2路与连通7.3图的矩阵表示7.4最短路径问题7.5图的匹配8.1Euler图和Hamilton图8.2树8.3生成树8.4平面图目的(1)掌握图论的基本问题、理论与方法(3)了解图论在信息学科中的应用以及在数学竞赛、数学建模中的应用(2)初步掌握运用图论的理论和方法解决实际问题的能力为什么要学习图论？图论——计算机问题求解的描述工具。可以采用图论的成果和方法；最重要的是：可以培养我们思考问题和解决问题的能
2、力。引言实际问题数学模型求解算法（算法）编程实现用大量数据验证抽象求解测试应用背景图论在现代科学技术中有着广泛的应用，如：网络设计、计算机科学、信息科学、密码学、DNA的基因谱的确定和计数、工业生产和企业管理中的优化方法等都广泛的应用了图论及其算法。计算机网络引言某学校网络架构图应用背景计算机网络电路模拟引言例：Pspice、Cadence、ADS…..PspiceCadence应用背景计算机网络电路模拟交通网络引言航空网络!捷運路線图！引言应用背景有向图有单行道的街道！行程表！引言应用背景Soci
3、alNetworkHighSchoolDatingcorporatee-mailReference:Bearman,MoodyandStovel,2004imagebyMarkNewmanReference:AdamicandAdar,2004引言应用背景TheInternetTheInternetasmappedbyTheOpteProjecthttp://www.opte.orgnet,ca,uscom,org,mil,gov,edujp,cn,tw,aude,uk,it,pl,frbr,kr,
4、nl引言MoreApplicationsHypertexts网页包含到其他网页的超链接。整个Web是一个图.搜索引擎需要图处理算法。Matching职位招聘，如何有效将职位与应聘者匹配？Schedules工程项目的任务安排，如何满足限制条件，并在最短时间内完成？Programstructure大型软件系统，函数（模块）之间调用关系。编译器分析调用关系图确定如何最好分配资源才能使程序更有效率。引言图论的产生和发展1.哥尼斯堡七桥问題(BridgesofKoenigsberg)[问题]能否从某一块陆地出
5、发，走遍每一座桥，且每一座桥只能走一次，最后回到出发点。引言欧拉路径：解決哥尼斯保七桥问題数学家欧拉(Euler,1707-1783)于1736年严格的证明了上述哥尼斯堡七桥问题无解，并且由此开创了图论的典型思维方式及论证方式原來是一笔画问题啊！转化Euler1736年图论中讨论的图问题：是否能从四块陆地中的任一块开始，通过每座桥恰好一次再回到起点？是否能从任意一个顶点开始，通过每条边恰好一次再回到起点？转化包含两个要素：对象（陆地）及对象间的二元关系（是否有桥连接）引言2.四色猜想在任何平面或球面
6、上的地图，只用四种颜色涂色，就可使得相邻区域涂上不同颜色。1976年，Appel,Haken和Koch利用计算机辅助证明了四色猜想，但其数学证明仍不理想。引言3.Hamilton周遊世界问題哈密頓路径至今尚无有效方法來解決！正十二面体有二十个顶点表示世界上20个城市各经每个城市一次最后返回原地投影至平面反映到图论上就是判断一个给定的图是否存在一条含所有顶点的回路。引言4.最短路径问題(ShortestPathProblem)最快航線最快的routing引言最短路径算法Dijkstra算法可以求出
7、從某一点到图上其他任一点的最短路径引言5.走迷宫与深度优先搜索(Depth-FirstSearch)老鼠走迷宮深度优先搜索一直往前走碰壁就回头換条路找沿途要记录下走过的路线两点之间有无道路可通？有多少条道路可通？哪条路最短？引言图论的重要地位图论在计算机科学领域中有着重要地位操作系统进程演变状态图和目录树搜索。人工智能图搜索策略和知识的表示数据结构的二大类非线性结构：树和图数据库系统的实体-联系模型和文件组织自动机理论引言图论的发展1847年基尔霍夫运用图论解决了电路理论中求解联立方程的问题，引进
8、了“树”概念。1857年Cayley非常自然在有机化学领域发现了一种重要的图，称为“树”，解决了计算饱和氢化物同分异构体的数目。1936年,哥尼格的第一本图论专著问世,才使得图论成为一门独立的数学学科.1946年,随着世界上第一台计算机的问世,使图论的发展突飞猛进.引言图论相关的交叉研究代数图论拓扑图论化学图论算法图论随机图论极值图论网络图论模糊图论超图论以往数学家习惯将纯数学应用于其它学科，Gowers将图论和组合数学中的Ramsey理论应用于泛函分析的研究，获得了
