第四篇 图论--第9章_图

电子科技大学离散数学课程组——国家精品课程

离散数学电子科技大学计算机科学与工程学院

示 范 性 软 件 学 院

2013年7月29日星期一

电子科技大学离散数学课程组——国家精品课程

第四篇 图论图论是一门很有实用价值的学科，它在自然科 学、社会科学等各领域均有很多应用。自上世纪中 叶以来，它受计算机科学蓬勃发展的刺激，发展极 其迅速，应用范围不断拓广，已渗透到诸如语言学、 逻辑学、物理学、化学、电讯工程、计算机科学以 及数学的其它分支中。特别在计算机科学中，如形 式语言、数据结构、分布式系统、操作系统等方面 均扮演着重要的角色。

2013-7-29

143-2

电子科技大学离散数学课程组——国家精品课程

引言1 2 七桥问题 欧拉

游戏、博弈问题 克希荷夫定律 树 凯莱

34 5

四色猜想

62013-7-29

高速数字计算机143-3

电子科技大学离散数学课程组——国家精品课程

教学目标图是一类具有广泛实际问题背景的数学模型， 有着极其丰富的内容，是数据结构等课程的先修内 容。学习时应掌握好图论的基本概念、基本方法和 基本算法，善于把实际问题抽象为图论的问题，然 后用图论的方法去解决。 图论作为一个数学分支，有一套完整的体系和 广泛的内容，本篇仅介绍图论的初步知识，其目的 在于今后对计算机有关学科的学习和研究时，可以 以图论的基本知识作为工具。2013-7-29 143-4

电子科技大学离散数学课程组——国家精品课程

第9章 图我们所讨论的图(Graph)与人们通常所熟悉的图， 例如圆、椭圆、函数图表等是很不相同的。图论中 所谓的图是指某类具体离散事物集合和该集合中的 每对事物间以某种方式相联系的数学模型。如果我 们用点表示具体事物，用连线表示一对具体事物之 间的联系。那么，一个图就是由一个表示具体事物 的点的集合和表示事物之间联系的一些线的集合所 构成，至于点的位置和连线的长短曲直是无关紧要 的。2013-7-29 143-5

电子科技大学离散数学课程组——国家精品课程

9.0 内容提要1 2 图的基本概念 图的表示、分类 图的性质 通路与回路 图的连通性

34 5

62013-7-29

图的应用143-6

电子科技大学离散数学课程组——国家精品课程

9.1 本章学习要求重点掌握 一般掌握 了解

11. 图的概念 2. 特殊图 3. 图论的基本定 理 4. 通路与回路 5. 图的连通性 2013-7-29

2

3

1. 图的同构 2. 图的构成与证 明

图论中的应用

143-7

电子科技大学离散数学课程组——国家精品课程

9.2 图的基本概念9.2.1 图的定义例9.2.1(1)考虑一张航线地图，图中用点表示城 市，当两个城市间有直达航班时，就用

一条线将相 应的点连接起来。这种航线地图的一部分如下图所 示；北京 长春

成都

武汉

上海

2013-7-29

143-8

电子科技大学离散数学课程组——国家精品课程

例9.2.1(2)假设有4台计算机，分别标记为A、B、C和D, 在计算机A和B、C和D以及B和C之间有信息流。这种 情形可用下图表示，通常称这种图为通信网络；

A

B

C

D

2013-7-29

143-9

电子科技大学离散数学课程组——国家精品课程

例9.2.1(3)假设有一群人和一组工作，这群人中的某些人 能够做这组工作中的某些工作。例如，有3个人A、 B和C,3件工作D、E和F,假设A只能做工作D, B能 做工作E和F, C能做工作D和E。则这种情形可用下 图表示，其中，在人和这个人能够做的工作之间画 有线。A B D E

C2013-7-29

F143-10

电子科技大学离散数学课程组——国家精品课程

基本思想用图形表示一组对象，其中有些对象对是有联 系的。当然，这几个图形也可以表示其它的含义。 例如在(3)的图中点A、B、C、D、E和F分别表示6 家企业，如果某两家企业有业务往来，则其对应的 点之间用线连接起来，这时的图形又反映了这6家 企业间的业务关系。

对于这种图形，我们感兴趣的只是有多少个点 和哪些结点之间有线连接，至于连线的长短曲直和 结点的位置却无关紧要，只要求每一条线都起始于 一个点，而终止于另一个点。2013-7-29 143-11

电子科技大学离散数学课程组——国家精品课程

定义9.2.1一个图(Graph)是一个序偶<V, E>,记为G = <V, E>,其中： (1)V = {v1, v2, …, vn}是有限非空集合，vi称 为结点(Nodal Point),简称点(Point),V称为结 点集(Nodal Set)。 (2)E是有限集合，称为边集(Frontier Set)。E 中的每个元素都有V中的结点对与之对应，称之为 边(Edge)。

2013-7-29

143-12

电子科技大学离散数学课程组——国家精品课程

与边相关的几个概念定义9.2.1中的结点对即可以是无序的，也可以 是有序的。A D 若边e与无序结点对(u,v)相对应，则称e为无向 边(Undirected Edge),记为eE = (u, v) = (v, u), B 这时称u、v是边e的两个端点(End point)。

若边e与有序结点对<u, v>相对应，则称e为有向 边(Directed Point)(或弧),记为e = <u, v>,这时 称u为e的始点(Initial Point)(或弧尾),v为e的终 点(terminal Point)(或弧头),统称为e的端点。2013-7-29 143-13

C

F

电子科技大学离散数学课程组——国家精品课程

9.2.2 图的表示对于一个图G,如果将其记为G = <V, E>,并 写出V和E的集合表示，这称为图的集合表示。 而为了描述简便起见，在一般情况下，往往只 画出它的图形：用小圆圈表示V中的结点，用由u指 向v的有向线段或曲线表示有向边<u, v>,无向线 段或曲线

表示无向边(u, v),这称为图的图形表示。

2013-7-29

143-14

电子科技大学离散数学课程组——国家精品课程

例9.2.2设图G = <V, E>,这里V = {v1, v2, v3, v4, v5},E = {e1, e2, e3, e4, e5, e6},其中e1 = (v1, v2) , e2 = <v1, v3> , e3 = (v1, v4) , e4 = (v2, v3),e5 = <v3, v2>,e6 = (v3, v3)。试画出图G的 图形，并指出哪些是有向边，哪些是无向边？

2013-7-29

143-15

电子科技大学离散数学课程组——国家精品课程

例9.2.2 分析分析 由于V中有5个结点，因此要用5个小圆圈 分别表示这5个结点，点的具体摆放位置可随意 放。而对E中的6条边，圆括号括起的结点对表示 无向边，直接用直线或曲线连接两个端点，尖括 号括起的结点对表示有向边，前一个是始点，后 一个始终点，用从始点指向终点的又向直线或曲 线连接。

2013-7-29

143-16