离散数学——图论.ppt

《离散数学——图论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四篇图论本篇包括第八章、第九章。主要内容有图的基本理论、欧拉图、哈密尔图、树等。图论是一个古老而又年轻的数学分支，它诞生于18世纪，它是用图的方法研究客观世界的一门科学，为任何一个包含二元关系的系统提供了一个直观而严谨的数学模型，因此物理系、化学、生物学、工程科学、管理科学、计算机科学等各个领域都有图论的足迹。图论的发展图论的产生和发展经历了二百多年的历史，从1736年到19世纪中叶是图论发展的第一阶段。第二阶段大体是从19世纪中叶到1936年，主要研究一些游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。一些图论中的著名问题如四色问题(1852年)和哈密尔顿环

2、游世界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫(G.R.Kirchoff)将树的概念和理论应用于工程技术的电网络方程组的研究。1857年英国的凯莱(A.Cayley)也独立地提出了树的概念，并应用于有机化合物的分子结构的研究中。1936年匈牙利的数学家哥尼格(D.Konig)发表了第一部集图论二百年研究成果于一书的图论专著《有限图与无限图理论》，这是现代图论发展的里程碑，标志着图论作为一门独立学科。现在图论的主要分支有图论、超图理论、极值图论、算法图论、网络图论和随机图论等。第三阶段是1936年以后。由

3、于生产管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现，大大促进了图论的发展。现代电子计算机的出现与广泛应用极大地促进了图论的发展和应用。目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域都有应用。。在计算机科学中计算机科学的核心之一就是算法的设计与理论分析，而算法是以图论与组合数学为基础；图论与组合数学关系也非常密切，已正式成为计算机诸多分支中一种有力的基础工具。因而，作为计算机专业人员，了解和掌握图论的基本原理和方法是必要的。图论交叉地运用了拓扑学、群论和数论知识，其定理证明难度高低不等，有

4、的简单易懂，有的难于理解，但其每一步证明都需要技巧，每一个定理都像艺术平一样值得品味与推敲。因此，尽管本教材介绍的是较为基础的图论内容，但阅读理解与完成习题是学习图论必不可少的步骤。图是人们日常生活中常见的一种信息载体，其突出的特点是直观、形象。图论，顾名思义是运用数学手段研究图的性质的理论，但这里的图不是平面坐标系中的函数，而是由一些点和连接这些点的线组成的结构。在图形中，只关心点与点之间是否有连线，而不关心点具体代表哪些对象，也不关心连线的长短曲直，这就是图的概念。当研究的对象能被抽象为离散的元素集合和集合上的二元关系时，用关系图表示和处理十分方便。§8.1图的基

5、本概念图论的起源可以追溯到1736年由瑞士数学家欧拉(LeonhardEuler，1707-1783)撰写的一篇解决“哥尼斯堡七桥问题”的论文。哥尼斯堡七桥问题把四块陆地用点来表示，桥用点与点连线表示。欧拉将问题转化为：任何一点出发，是否存在通过每条边一次且仅一次又回到出发点的路？欧拉的结论是不存在这样的路。显然，问题的结果并不重要，最为重要的是欧拉解决这个问题的中间步骤，即抽象为图的形式来分析这个问题。这是一种全新的思考方式，由此欧拉在他的论文中提出了一个新的数学分支，即图论，因此，欧拉也常常被图论学家称为图论之父。欧拉欧拉是著作较多的著名数学家之一，曾发表了886

6、篇论文，出版了近90本书。在数学界的许多分支如数论、几何、组合数学等领域的很多定理和公式都以欧拉命名的。欧拉简介图的基本概念定义8.1图（Graph）G包括一个非空的对象的集合V={v1,v2,…,vn}与有限的V中两个对象构成的无序对构成的集合E={e1,e2,…,em}，前者称为结点集(Vertexset)，后者称为边集（Edgeset）。一般用G=表示图。例子：教材116页例8.1，例8.2根据图中边的方向，分为有向图、无向图。边关联：有向边lk=(vi,vj)，其中vi称为起点，vj称为终点。无论边是否有向，称lk与vi,vj相关联。邻接：边lk=(

7、vi,vj)，称vi,vj是邻接的点，若干条边关联同一个结点，则称边是邻接的。环：边lk=(vi,vj)，vi与vj是同一个点。孤立点：不与任何点相邻接的点。定义图的子图子图：设G=，G’=，若V’是V的子集，E’是E的子集，则G’是G的子图。真子图：若V’是V的子集，E’是E的真子集。生成子图：V’=V，E’是E的子集。举例说明一个图的子图。定义（n,m）图(n,m)图：由n个结点，m条边组成的图。零图：m=0。即（n,0）图，有n个孤立点。平凡图：n=1,m=0。即只有一个孤立点。完全图：一个（n,m）图G，其n个结点中每