下载此文档

第5章 图的基本理论.ppt


文档分类:医学/心理学 | 页数:约131页 举报非法文档有奖
1/131
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/131 下载此文档
文档列表 文档介绍
离散数学吴明芬教授五邑大学计算机学院2014年9月图论图论是一门很有实用价值的学科,它在自然科学、社会科学等各领域均有很多应用。自上世纪中叶以来,它受计算机科学蓬勃发展的刺激,发展极其迅速,应用范围不断拓广,已渗透到诸如语言学、逻辑学、物理学、化学、电讯工程、计算机科学以及数学的其它分支中。特别在计算机科学中,如形式语言、数据结构、分布式系统、操作系统等方面均扮演着重要的角色。2020/7/9图是一类具有广泛实际问题背景的数学模型,有着极其丰富的内容,是数据结构等课程的先修内容。学****时应掌握好图论的基本概念、基本方法和基本算法,善于把实际问题抽象为图论的问题,然后用图论的方法去解决。图论作为一个数学分支,有一套完整的体系和广泛的内容,第5、6章仅介绍图论的初步知识,其目的在于今后对计算机有关学科的学****和研究时,可以以图论的基本知识作为工具。2020/7/9第5章图的基本理论我们所讨论的图(Graph)与人们通常所熟悉的图,例如圆、椭圆、函数图表等是很不相同的。图论中所谓的图是指某类具体离散事物集合和该集合中的每对事物间以某种方式相联系的数学模型。如果我们用点表示具体事物,用连线表示一对具体事物之间的联系。那么,一个图就是由一个表示具体事物的点的集合和表示事物之间联系的一些线的集合所构成,至于点的位置和连线的长短曲直是无关紧要的。2020/7/9内容提要图的应用6通路与回路、(1)考虑一张航线地图,图中用点表示城市,当两个城市间有直达航班时,就用一条线将相应的点连接起来。这种航线地图的一部分如下图所示;长春北京成都武汉上海2020/7/(2)假设有4台计算机,分别标记为A、B、C和D,在计算机A和B、C和D以及B和C之间有信息流。这种情形可用下图表示,通常称这种图为通信网络;(3)假设有一群人和一组工作,这群人中的某些人能够做这组工作中的某些工作。例如,有3个人A、B和C,3件工作D、E和F,假设A只能做工作D,B能做工作E和F,C能做工作D和E。则这种情形可用下图表示,其中,在人和这个人能够做的工作之间画有线。ACFDBE基本思想用图形表示一组对象,其中有些对象对是有联系的。对于这种图形,我们感兴趣的只是有多少个点和哪些结点之间有线连接,至于连线的长短曲直和结点的位置却无关紧要,只要求每一条线都起始于一个点,而终止于另一个点。(Graph)是一个序偶<V,E>,记为G=<V,E>,其中:(1)V={v1,v2,…,vn}是有限非空集合,vi称为结点,简称点,V称为结点集。(2)E是有限集合,称为边集。E中的每个元素都有V中的结点对与之对应,称之为边。

第5章 图的基本理论 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数131
  • 收藏数0 收藏
  • 顶次数0
  • 上传人独角戏
  • 文件大小1.90 MB
  • 时间2020-07-09