PDF《离散数学基础：图论》

离散数学基础:图论 Fundamentals of Discrete Mathematics: Graph Theory 周晓聪(isszxc@zsu.

edu.cn) 中山大学计算机科学系, 广州510275

2008 年12 月26 日2版权所有,翻印必究 目录 目录 i

第一章 图的基本概念

1 1.1 图的基本定义

1 1.2 道路与回路

6 1.3 图的连通性

8 1.4 邻接矩阵与可达矩阵

12

第二章 树的基本概念

19 2.1 树的基本定义

19 2.2 生成树

21 2.3 根树

26 2.4 哈夫曼树

31

第三章 路径问题

41 3.1 最短路径

41 3.2 最小生成树

47 3.3 关键路径

49

第四章 平面图与着色

55 4.1 平面图及其性质

55 4.2 图的着色

58

第五章 支配集、覆盖集、独立集和匹配

65 5.1 支配集、点独立集和点覆盖集

65 5.2 边覆盖与匹配

67 5.3 二部图中的匹配

73

第六章 欧拉图与哈密顿图

77 6.1 欧拉图

77 6.2 哈密顿图

77 i ii 目录 参考文献

79

第一章 图的基本概念 这一章介绍有关图论的一些基本概念,包括无向图(有向图)的定义、顶点与边之间的关系、顶 点度数、握手定理、图的道路与回路等. 1.1 图的基本定义 定义 1.1.1 (无向)图(graph)是二元组G = (V, E),其中V = ?是图G的顶点(vertex)集,其中的 元素称为G的顶点(vertex),E是图G的边(edge)集,其中的元素称为G的边(edge),且满足,对图G的 任意边e∈E,都有且仅有两个顶点u, v∈V 与e关联,称为e的两个端点,通常将e记为e = (u, v)或e = (u, v). 对于边e = (u, v),这里u, v没有顺序,因此边e = (u, v)和e = (v, u)是同一条边.我们只考虑有 限图G = (V, E),也即其顶点集V 和边集E都是有限集.上面的定义是说,在定义一个图的时候,要 给出它的顶点集和边集,并说明每一条边的两个端点是那两个顶点.通常,我们可以对图作最为直 观的理解,则画出这个图,并用V 和E中的元素对这个图进行标记. 例子 1.1.2 下面是一个图的直观表示: ? v1 e2 e3 e1 e4 e5 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ?v2 e6 e7 ppppppppppppppppppppppppppppp ? v3 e8 ? e9 v4 若将这个图用比较严格的数学形式给出来,则是:图G = (V, E),其中: V = { v1, v2, v3, v4 } E = { e1 = (v1, v3), e2 = (v1, v3), e3 = (v1, v3), e4 = (v1, v2), e5 = (v1, v4), e6 = (v2, v4), e7 = (v2, v3), e8 = (v3, v4), e9 = (v4, v4) } 有时为了简便,我们可能在给出图的直观形式时,没有对其顶点和边进行标记,例如下面是上 面的图不带标记的形式:

1 2

第一章 图的基本概念 ? x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ? ppppppppppppppppppppppppppppp ? ? 这通常是因为我们这时只关注整个图的性质,不关心图的顶点或边的性质.如果需要关心某些顶点 或边的性质时,我们也可能将某些顶点和边标记,而不标记其他顶点和边. 定义 1.1.3 (有向)图(directed graph, 或简称digraph)是二元组G = (V, E),其中V = ?是图D的顶点(vertex)集,其中的元素称为G的顶点(vertex),E是图G的边(edge)集,其中的元素称 为G的边(edge),且满足,对图G的任意边e∈E,都有一个顶点u∈V 是e的起点,同时有一个顶点v∈ V 是e的终点,通常将e记为e = u, v . 类似,我们也只考虑有限有向图,有向图与无向图的区别,在于有向图中与每一条边相关联的 两个顶点区分为起点和终点. 例子 1.1.4 下面是一个有向图的直观表示: ? yy v1 e2 e3 e1 oo e4 gg x x x x x x x x x x x x x x x x x x x x e5 x x x x x x x x x ? v2 e6 wwppppppppp e7 pppppppppppppppppppp ? GG v3 e8 ? ff e9 v4 若将这个有向图用比较严格的数学形式给出来,则是:图G = (V, E),其中: V = { v1, v2, v3, v4 } E = { e1 = v1, v3 , e2 = v3, v1 , e3 = v1, v3 , e4 = v2, v1 , e5 = v4, v1 , e6 = v2, v4 , e7 = v2, v3 , e8 = v3, v4 , e9 = v4, v4 } 对于无向图或有向图,还有下面一些简单概念和规定: 1. 通常使用G表示无向图,D表示有向图,但有时用G泛指无向或有向图的,不过D总是表示有 向图;