- 1、本文档共92页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
离散数学——图论课件.ppt事业单位模拟考试试题
离散数学——图论
v 图论是一个古老而又年轻的数学分支,它诞生于18世纪,它是用图的方法研究客观世界的一门科学,为任何一个包含二元关系的系统提供了一个直观而严谨的数学模型,因此物理系、化学、生物学、工程科学、管理科学、计算机科学等各个领域都有图论的足迹。
图论的发展v 图论的产生和发展经历了二百多年的历史,从1736年到19世纪中叶是图论发展的第一阶段。v 第二阶段大体是从19世纪中叶到1936年,主要研究一些游戏问题:迷宫问题、博弈问题、棋盘上马的行走线路问题。
v 一些图论中的著名问题如四色问题(1852年)和哈密尔顿环游世界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。v 1847年德国的克希霍夫(G.R.Kirchoff)将树的概念和理论应用于工程技术的电网络方程组的研究。v 1857年英国的凯莱(A.Cayley)也独立地提出了树的概念,并应用于有机化合物的分子结构的研究中。
v 1936年匈牙利的数学家哥尼格(D.Konig) 发表了第一部集图论二百年研究成果于一书的图论专著《有限图与无限图理论》,这是现代图论发展的里程碑,标志着图论作为一门独立学科。v 现在图论的主要分支有图论、超图理论、极值图论、算法图论、网络图论和随机图论等。
v 第三阶段是1936年以后。由于生产管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现,大大促进了图论的发展。现代电子计算机的出现与广泛应用极大地促进了图论的发展和应用。v 目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域都有应用。。
v 在计算机科学中计算机科学的核心之一就是算法的设计与理论分析,而算法是以图论与组合数学为基础;图论与组合数学关系也非常密切,已正式成为计算机诸多分支中一种有力的基础工具。v 因而,作为计算机专业人员,了解和掌握图论的基本原理和方法是必要的。
v 图论交叉地运用了拓扑学、群论和数论知识,其定理证明难度高低不等,有的简单易懂,有的难于理解,但其每一步证明都需要技巧,每一个定理都像艺术平一样值得品味与推敲。v 因此,尽管本教材介绍的是较为基础的图论内容,但阅读理解与完成习题是学习图论必不可少的步骤。
v 图是人们日常生活中常见的一种信息载体,其突出的特点是直观、形象。图论,顾名思义是运用数学手段研究图的性质的理论,但这里的图不是平面坐标系中的函数,而是由一些点和连接这些点的线组成的结构 。
v 在图形中,只关心点与点之间是否有连线,而不关心点具体代表哪些对象,也不关心连线的长短曲直,这就是图的概念。v 当研究的对象能被抽象为离散的元素集合和集合上的二元关系时,用关系图表示和处理十分方便。
§8.1图的基本概念v 图论的起源可以追溯到1736年由瑞士数学家欧拉(Leonhard Euler,1707-1783)撰写的一篇解决“哥尼斯堡七桥问题”的论文。
哥尼斯堡七桥问题v 把四块陆地用点来表示,桥用点与点连线表示。
v 欧拉将问题转化为:任何一点出发,是否存在通过每条边一次且仅一次又回到出发点的路?欧拉的结论是不存在这样的路。显然,问题的结果并不重要,最为重要的是欧拉解决这个问题的中间步骤,即抽象为图的形式来分析这个问题 。v 这是一种全新的思考方式,由此欧拉在他的论文中提出了一个新的数学分支,即图论,因此,欧拉也常常被图论学家称为图论之父。
欧拉v 欧拉是著作较多的著名数学家之一,曾发表了886篇论文,出版了近90本书。在数学界的许多分支如数论、几何、组合数学等领域的很多定理和公式都以欧拉命名的。
欧拉简介
图的基本概念v 定义8.1图(Graph)G包括一个非空的对象的集合V={v ,v ,…,v }n1 2与有限的V中两个对象构成的无序对构成的集合E={e ,e ,…,e },m1 2前者称为结点集(Vertex set),后者称为边集(Edgeset)。一般用G=V,E表示图。
v 例子:教材116页例8.1,例8.2
v 根据图中边的方向,分为有向图、无向图。v 边关联:有向边l =(v ,v ),其中v 称为起点,v 称k为终点。无论边是否有向,称l 与v ,v 相关联。i jijki jv 邻接:边l =(v ,v ),称v ,v 是邻接的点,若干条k边关联同一个结点,则称边是邻接的。i ji jv 环:边l =(v ,v ), v 与v 是同一个点。ki jijv 孤立点:不与任何点相邻接的点。
定义图的子图v 子图:设G=V,E, G’=V’,E’,若V’是V的子集,E’是E的子集,则G’是G的子图。v 真子图:若V’是V的子集,E’是E的真子集。v 生成子图:V’=V,E’是E的子集。v 举例说明一个图的子图。
定义(n,m)图v
文档评论(0)