离散数学第八章(第1讲)课件.ppt

1、图论的应用图论的应用n图论是一门应用性很强的学科。图论是一门应用性很强的学科。2020世纪世纪6060年代以来，它在年代以来，它在许多领域，如许多领域，如物理学、生物学、计算机科学、信息论、运物理学、生物学、计算机科学、信息论、运筹学筹学以及以及语言学、社会科学语言学、社会科学等有着广泛的应用。等有着广泛的应用。n图论在计算机科学中的应用：图论在计算机科学中的应用：最短通路、最小生成树、最最短通路、最小生成树、最大匹配、中国邮递员问题和旅行售货员等问题大匹配、中国邮递员问题和旅行售货员等问题的算法和计的算法和计算机实现。算机实现。第八章第八章 图图8.1 图的基本概念图的基本概念8.2 路与图

2、的连通性路与图的连通性8.3 图的矩阵表示图的矩阵表示8.4 赋权图及最短路径赋权图及最短路径8.5 特殊的图特殊的图8.18.1 图的基本概念图的基本概念n离散数学所研究的图是不同于几何图形、机械图形的另一离散数学所研究的图是不同于几何图形、机械图形的另一种数学结构种数学结构,不关心图中不关心图中顶点的位置、边的长短和形状顶点的位置、边的长短和形状,只只关心关心顶点与边的联结关系。顶点与边的联结关系。n如下图（如下图（a）和（）和（b）可以认为是同一个图形。）可以认为是同一个图形。abcde1e2e6e4e3e5（a）abcde1e6e2e4e3e5（b）abcde1e2e6e4e3e5（1

3、）图的定义图的定义:一个图一个图G可用一个二元组可用一个二元组表示表示,其中其中V(G)为顶点集合为顶点集合,E(G)是边的集合。是边的集合。讨论定义：讨论定义：(a)V(G)=V1，V2，Vn为有限非空集合为有限非空集合,Vi称为顶点。称为顶点。(b)E(G)=e1，em为有限的边集合为有限的边集合,ei称为边称为边。可用可用 e 或或e(vi,vj)来表示图的边。来表示图的边。（2）无向图，有向图无向图，有向图 每一条边都是无向边的图称无向图。每一条边都是无向边的图称无向图。每一条边都是有向边的图称有向图。每一条边都是有向边的图称有向图。bcdabcda例：将右图用二元组表示为：例：将右图

4、用二元组表示为：，其中其中a，b，c，d ,则：则：，=a，b，c，d，,（3）邻接点，孤立结点邻接点，孤立结点 邻接点：邻接点：在一个图中，若两个结点有一条有向边或者一条在一个图中，若两个结点有一条有向边或者一条无向边关联无向边关联,则这两个结点称为邻接点。则这两个结点称为邻接点。孤立结点：孤立结点：在一个图中不与任何结点相邻接的结点，称为在一个图中不与任何结点相邻接的结点，称为孤立结点。如下图中结点孤立结点。如下图中结点v5。v1v2v3v4v5（4）零图，平凡图零图，平凡图 零图：零图：仅由孤立结点构成的图称为零图。如图仅由孤立结点构成的图称为零图。如图(a)平凡图：平凡图：仅由一个孤立

5、结点构成的图称为平凡图。如图仅由一个孤立结点构成的图称为平凡图。如图(b)(a)(b)（5）邻接边：邻接边：关联于同一结点的两条边称为邻接边。关联于同一结点的两条边称为邻接边。（6）自回路（环）：自回路（环）：关联于同一结点的一条边称为自关联于同一结点的一条边称为自 回路。回路。如下图，如下图，e4=是自回路（环）。是自回路（环）。e3e4（7）度数：度数：在图在图G=中，与结点中，与结点v（v V）关）关 联的联的边数，称为该结点的度数，记作边数，称为该结点的度数，记作deg（v）。）。约定：约定：每个环在其对应结点上的度数增加每个环在其对应结点上的度数增加2。ABCED最大度最大度,记为：

6、记为：(G)(G)=maxd(v)|v V最小度最小度,记为：记为：(G)(G)=mind(v)|v Vn定理定理1(握手定理握手定理)：每个图中，结点度数的总和等于边每个图中，结点度数的总和等于边数的两倍。即数的两倍。即 证：证：每条边必关联两个结点，而一条边给于关联的每每条边必关联两个结点，而一条边给于关联的每个结点的度数为个结点的度数为1。故上述定理成立。故上述定理成立。deg()2v VvE例：例：在一次在一次10周年同学聚会上，想统计所有人握手的周年同学聚会上，想统计所有人握手的次数之和，应该如何建立该问题的图论模型？次数之和，应该如何建立该问题的图论模型？解：将每个同学分别作为一个

7、节点，如果两个人握过一次手就在相应的两个节点之间画一条无向边，于是得到一个无向图。一个人握手的次数就是这个节点与其他节点所连接的边的条数，进而可得出所有人握手的次数之和。n例：例：无向图无向图G G有有6 6条边，各有一个条边，各有一个3 3度和度和5 5度节点，其度节点，其余均为余均为2 2度节点，求度节点，求G G的阶数。的阶数。解解:设图设图G有有x个节点度数为个节点度数为2，则，则G的阶数为的阶数为x+1+1=x+2。根据握手定理有：根据握手定理有：3+5+2x=12于是于是x=2，所以，所以G的阶数为的阶数为2+2=4。定理定理2：在任何图中，度数为奇数的结点必定是偶数个。在任何图中

8、，度数为奇数的结点必定是偶数个。例：例：是否是否存在一个无向图，其度数序列分别存在一个无向图，其度数序列分别为为：(1)5，4，4，3，3，2，2 (2)4，4，3，3，2，2，2，2n例：例：设无向图设无向图G有有10条边，条边，3度和度和4度节点各度节点各2个，其个，其余节点的度数均小于余节点的度数均小于3，则，则G至少有多少个节点？在至少有多少个节点？在最少节点的情况下，求出最少节点的情况下，求出G的度数序列、最大度的度数序列、最大度 和和最小度最小度。（8）入度，出度：入度，出度：在有向图中，射入一个结点的边数称为该在有向图中，射入一个结点的边数称为该结点的入度。由一个结点射出的边数称

9、为该结点的出度。结点的入度。由一个结点射出的边数称为该结点的出度。结点的出度与入度结点的出度与入度和和是该结点的度数。是该结点的度数。BCDADeg+（A）=2,Deg-（A）=3Deg+（B）=3,Deg-（B）=2Deg+（C）=1,Deg-（C）=1Deg+（D）=1,Deg-（D）=1例：例：一个一个3阶有向图的度序列是阶有向图的度序列是2，2，4，入度序列是，入度序列是2，0，2，出度序列是，出度序列是 .bcda证：因为每一条有向边必对应一个入度和出度，若一个结点具有一个入度或出度，则必关联一条有向边，所以，有向图中各结点入度和等于边数，各结点出度和也是等于边数，因此，任何有向图中

10、，入度之和等于出度和。定理3：在任何有向图中，所有结点的入度和等于所有结点的出度之和。（9）平行边，多重图，简单图平行边，多重图，简单图 连接于同一对结点间的多条边称为是平行边。连接于同一对结点间的多条边称为是平行边。含有平行边的任何一个图称为多重图。含有平行边的任何一个图称为多重图。不含有平行边和环的图称作简单图。不含有平行边和环的图称作简单图。a abc（b）a abc（a）e1e2（10）无向完全图：无向完全图：简单图简单图G=中，若每一对结中，若每一对结点间都有无向边存在，则称该图为无向完全图。点间都有无向边存在，则称该图为无向完全图。定理定理4：n个结点的无向完全图的边数为：个结点的

11、无向完全图的边数为：证明：在有证明：在有n个结点的无向完全图中，任意两点间都有边个结点的无向完全图中，任意两点间都有边连接，连接，n个结点中任意取两点的组合为：个结点中任意取两点的组合为：故有故有n个结点的无向完全图的边数为个结点的无向完全图的边数为21(1)2nCn n1(1)2En n1(1)2n n例：有例：有9个结点的无向完全图个结点的无向完全图K9的边数为？的边数为？（11）补图：补图：给定一个图给定一个图G，由，由G中所有结点和所有能使中所有结点和所有能使G成为完全图的添加边组成的图，称为成为完全图的添加边组成的图，称为G 相对于完全图相对于完全图的补图，或简称为的补图，或简称为G

12、的补图。记作。的补图。记作。如下图，（如下图，（a）和（）和（b）互为补图。）互为补图。G（a）v1v2v5v3v4（b）v1v2v3v4v5例：例：对于对于n阶简单无向图阶简单无向图G，若其边数为，若其边数为m，试计算，试计算G的补图的补图 的边数。的边数。（12）子图：子图：设图设图G=，如果有图，如果有图G=，且且EE，VV，则称，则称 G 为为 G 的子图。的子图。如下图，（如下图，（b）、（）、（c）都是（）都是（a）的子图。）的子图。（a）bcdhgafe（b）bcdhgfe（c）bcdhgaf（13）生成子图：生成子图：如果如果G的子图包含的子图包含G的所有结点，则称的所有结点，

13、则称该子图为该子图为G的生成子图。的生成子图。如下图，（如下图，（b）、（）、（c）都是（）都是（a）的生成子图。）的生成子图。（a）（c）（b）v2v4v2v3v1v1v3v4v1v4v2v3例：设G=与G1=是两个图，若 _,则G1为G的生成子图。（14）图同构图同构 设图设图G=及图及图G=，如果存在一双射函，如果存在一双射函数数g：viv i且且e=（vi，vj）是）是G的一条边，当且仅当的一条边，当且仅当 e=（g（vi），），g（vj）是）是 G 的一条边，则称的一条边，则称G与与G 同同构，记作构，记作G G。两个图同构的充要条件是：两个图的结点和边分别存在两个图同构的充要条件是

14、：两个图的结点和边分别存在着一一对应的关系，且保持关联关系。着一一对应的关系，且保持关联关系。dbea（a）u3u4u2u1（b）例：存在着一双射函数例：存在着一双射函数g：g(a)=u3，g(b)=u1，g(e)=u4，g(d)=u2，且有：且有：,分别与分别与,一一对应一一对应所以图所以图(a)与图与图(b)是同构的关系。是同构的关系。两图同构的一些两图同构的一些必要条件必要条件：（1）结点数目相同。）结点数目相同。（2）边数相等。）边数相等。（3）度数相同的结点数目相同）度数相同的结点数目相同 这几个条件不是两个图同构的充分条件。下列两图，满足上这几个条件不是两个图同构的充分条件。下列两图，满足上述三个条件，但并不同构。述三个条件，但并不同构。例：例：说明说明以下两组图不同构。以下两组图不同构。（1）（2）例：画出例：画出4阶阶3条边的所有非同构的无向简单图条边的所有非同构的无向简单图.1,1,1,31,1,2,20,2,2,2解 总度数为6,分配给4个顶点,最大度为3,且奇度顶点数为偶数,有下述3个度数列:(1)1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.