东北农业大学《离散数学》课件-第十章（第十一周）.pdfVIP

第四篇 图论 东北农业大学离散数学第十章 什么是图论 定义  图论（Graph Theory）是数学的一个分支。它以图为研究对象。  图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形 通常用来描述某些事物之间的某种特定关系；用点表示事物，用连接两 点的线表示相应两个事物间的关系。  从一般意义而言，它描述了客观世界中的拓扑结构。 东北农业大学离散数学第十章 什么是图论  人们常称1736年是图论历史元年，因为在这一年瑞士数学家欧拉 （Euler）发表了图论的首篇论文—— 《哥尼斯堡七桥问题无解》，所 以人们普遍认为欧拉是图论的创始人。  1936年，匈牙利数学家寇尼格（Konig）出版了图论的第一部专著 《有 限图与无限图理论》，这是图论发展史上的重要的里程碑，它标志着图 论将进入突飞猛进发展的新阶段。 东北农业大学离散数学第十章 哥尼斯堡七桥问题 18 世纪在哥尼斯堡城( 今俄罗斯加里宁 格勒) 的普莱格尔河上有7 座桥，将河中的两 个岛和河岸连结，如图所示。城中的居民经常 沿河过桥散步，于是提出了一个问题：能否一 次走遍7 座桥，而每座桥只许通过一次，最后 仍回到起始地点。这就是著名的哥尼斯堡七桥 问题。 东北农业大学离散数学第十章 图论的应用 计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、 社会科学以及经济管理、军事、国防、工农业生产等方面都得到广泛的应 用。 1936年，匈牙利数学家寇尼格（Konig）出版了图论的第一部专著 《有限图与无限图理论》，这是图论发展史上的重要的里程碑，它标志着 图论将进入突飞猛进发展的新阶段。 东北农业大学离散数学第十章 图论的知识体系概图 东北农业大学离散数学第十章 第十章 图的基本概念 东北农业大学离散数学第十章 本章各节间的关系概图 东北农业大学离散数学第十章 图的基本概念在计算机科学技术相关领域的应用 东北农业大学离散数学第十章 第四篇 图论 东北农业大学离散数学第十章 10.1 图的定义 预备知识：  有序积: AB={ x,y |xAyB} 有序对: x,yy,x  无序积: AB={ (x,y) |xAyB} 无序对: (x,y)=(y,x)  多重集: {a,a,a,b,b,c}{a,b,c} 重复度: a的重复度为3, b的为2, c的为1 东北农业大学离散数学第十章 10.1 图的定义 定义10.1无向图 G = V,E, 其中 (1) V  为顶点集，元素称为顶点 (2) E为VV 的多重集，其元素称为无向边，简称边 实例 设V = {v , v , …,v }, 1 2 5 E = {(v ,v ), (v ,v ), (v ,v ), 1 1 1 2 2 3 (v ,v ), (v ,v ), (v ,v ), (v ,v )