离散数学课件 第五章 图

离散数学

Discrete

Mathematics第五章图5.1图5.2通路、回路和图的连通性5.3图的矩阵表示5.4图的应用25.1图第5章图

图的定义和有关术语顶点的度数完全图子图与补图图的同构3离散数学5.1.1图的定义和有关术语4

离散数学5离散数学

图5.1无向图示例

6离散数学

图5.2有向图示例7离散数学

8离散数学

图5.1无向图示例

例

图5.2有向图示例

9离散数学5.1.2顶点的度

注：有向图中，每条有向边产生2度，即一个始点的出度，一个终点的入度，顶点v上的一条环对顶点v产生出度和入度各1度。无向图中，每条边也产生2度，顶点v上的一条环与该顶点关联2次。10离散数学例5.3

写出图5.2中各顶点的出度、入度和度。

图5.2有向图示例顶点出度入度度

11离散数学例5.3

写出图5.2中各顶点的出度、入度和度。

图5.2有向图示例顶点出度入度度235112314123

各顶点度数之和为14，正好是边数的2倍。12离散数学

在有向图中，上式还可以写成13离散数学

14离散数学

图5.1无向图示例

图5.2有向图示例图5.1的度数序列为2，4，2，4，3，1。图5.2的度数序列为5，2，4，3。15离散数学

证明在计算顶点的度时，任何一条有向边都会提供1个出度和1个入度，因此，任意有向图所有顶点的入度之和等于所有顶点的出度之和，且等于边数。

图5.2有向图示例顶点出度入度23113112

16离散数学

17离散数学5.1.3完全图定义5.4含有平行边的有向图或无向图叫多重图。无环、不含平行边的有向图或无向图称为简单图。图5.1为无向多重图，图5.2中有环，但不含平行边，所以既不是多重图，也不是简单图。

18离散数学

图5.4有4个顶点的有向完全图19离散数学

20离散数学5.1.4子图与补图

21离散数学

22离散数学

23离散数学

课堂练习求图5.6（a）、5.6（b）、5.6（c）的补图。

（a）（b）（c）分析一个图的补图的顶点集与之相同，边集是以完全图的边集为全集的补集。解题思路可以先补充一些边使原图变成完全图，然后再删除掉原图中的边，得到的就是原图的补图。注意孤立点不要漏掉。24离散数学

（a）（b）（c）

补图补图补图25离散数学5.1.5图的同构

26离散数学

图5.8同构的图

证明构造顶点之间的双射函数如下：

27离散数学例5.8（1）画出具有4个顶点3条边的所有非同构的无向简单图。解4个顶点3条边的所有非同构的无向简单图只有图5.9（a）、图5.9（b）、图5.9（c）。其中图5.9（a）与图5.9（b）互为补图，图5.9（c）是自补图。图5.9具有4个顶点3条边的所有非同构的无向简单图（a）（b）（c）离散数学例5.8（2）画出具有3个顶点2条边的所有非同构的有向简单图。解3个顶点2条边的所有非同构的有向简单图只有图5.10（a）、图5.10（b）、图5.10（c）和图5.10（d）。图5.10具有3个顶点2条边的所有非同构的有向简单图（a）（b）（c）（d）迄今为止，还没有找到一种简单而有效的方法来判断两个图是否同构。要证明两个图同构，只能根据定义，寻找顶点之间满足条件的双射函数。5.2通路、回路和图的连通性第5章图

通路与回路顶点的度数无向图的连通性有向图的连通性29离散数学5.2.1通路与回路30离散数学

31离散数学

图5.12无向图的通路

32离散数学

图5.13有向图的通路33离散数学

34离散数学5.2.2无向图的连通性

35离散数学图5.14连通图图5.15非连通图图5.14所示的图是连通图，有1个连通分支。图5.15所示的图是非连通图，有2个连通分支。36离散数学

37离散数学

38离散数学5.2.3有向图的连通性

强连通图单向连通图弱连通图5.3图的矩阵表示第5章图

无向图的关联矩阵有向图的关联矩阵无向图的邻接矩阵有向图的邻接矩阵有向图的可达矩阵39离散数学40离散数学5.3.1无向图的关联矩阵

例5.9

求图5.18所示无向图的关联矩阵。

41离散数学

42离散数学5.3.2有向图的关联矩阵

例5.10

求图5.19所示有向图的关联矩阵。

43离散数学

44离散数学5.3.3无向图的邻接矩阵

例5.11写出图5.20所示无向图的邻接矩阵。

45离散数学

46离散数学5.3.4有向图的邻接矩阵

例5.12写出图5.21所示有向图的邻接矩阵。

47离散数学

48离散数学

49离散数学例5.13

求图5.21所示有向图中的通路。

解通过计算可得：

50离散数学5.3.5有向图的可达矩阵

51离散数学

52离散数学

例5.14计算图5.21所示有向图的可达矩阵。53离散数学

可以类似定义无向图的可达矩阵。实际上，可以把无向图看作有向图的特殊情况，即把每条无向边看作一对方向相反的有向边。5.4图的应用第5章图

拓扑排序的概念拓扑排序算法步骤54离散数学55离散数学问题引入一个计算机专业的学生必须学习一系列基本课程（见表5.2），其中有些课程是基础课，如“高等数学”；而另一些课程必须在学完先修课程的基础上才能开始学习，比如“数据结构”的学习必须在学习完“程序设计基础”和“离散数学”之后，这些先决条件定义了课程之间的优先关系。56离散数学课程编号课程名称先修课程C1程序设计基础无C2离散数学C1C3数据结构C1,C2C4汇编语言C1C5算法分析与设计C3,C4C6计算机组成原理C11C7编译原理C3,C5C8操作系统C3,C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C1,C9,C10表5.2计算机专业的必修课及其关系

图5.22课程之间的优先关系图57离散数学5.4.1拓扑排序的概念

一个无回路的有向图称作有向无圈图（DirectedAcyclineGraph），简称DAG图。通常把计划、施工过程、生产流程、程序流程等都当成一个工程。58离散数学拓扑排序的主要特点：（1）线性排序：将图中的顶点排列成一个线性序列。（2）依赖性保持：如果存在一条从顶点𝑢指向顶点𝑣的边，则在排序结果中𝑢必须在𝑣之前。（3）无圈性：拓扑排序适用于没有回路的有向图，即图中不存在从某个顶点出发经过一系列边最终回到该顶点的路径。59离散数学

5.4.2拓扑排序的算法步骤60离散数学例5.14设某工程可分为7个子工程，若用顶点表示子工程，用有向边表示子工程间的约束关系，工程的施工流程如图5.23所示，如果同一个时间只能够进行一项子工程，求一种可行的线性执行序列，即求子工程的一个拓扑序列。

图5.