离散数学教学课件：第7章 图的基本概念

图论简介图论是一个古老的数学分支，它起源于游戏难题的研究。图论的内容十分丰富，应用得相当广泛，许多学科，诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等，都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展，图论在以上各学科中的作用越来越大，同时图论本身也得到了充分的发展。本课程在第七，八，九各章中介绍与计算机科学关系密切的图论的内容。

第七章

图的基本概念

第一节

无向图及有向图

内容：有向图，无向图的基本概念。重点：1、有向图，无向图的定义，

2、图中顶点，边，关联与相邻，顶点度数等基本概念，3、各顶点度数与边数的关系及推论，内容：有向图，无向图的基本概念。5、图的同构的定义。重点：4、简单图，完全图，子图，补图的概念，一、图的概念。1、定义。无序积无向图中元素为无向边，简称边。，有向图中元素为有向边，简称边。，一、图的概念。1、定义。无序积2、图的表示法。有向图，无向图的顶点都用小圆圈表示。无向边——连接顶点的线段。有向边——以为始点，以为终点的有向线段。例1、(1)无向图，图形表示如右：图形表示如右：例1、(2)有向图，3、相关概念。(1)有限图——都是有限集的图。阶图——的图。零图——的图。特别，若又有，称平凡图。(2)关联

(边与点关系)——设边(或)，则称与(或)关联。3、相关概念。(2)3、相关概念。(2)孤立点——无边关联的点。环——一条边关联的两个顶点重合，称此边为环

(即两顶点重合的边)。3、相关概念。(2)悬挂点——只有一条边与其关联的点，所对应的边叫悬挂边。(3)平行边——关联于同一对顶点的若干条边称为平行边。平行边的条数称为重数。多重图——含有平行边的图。简单图——不含平行边和环的图。如例1的(1)中，与关联的次数均为1，与关联的次数为2，边都是相邻的，为孤立点，为悬挂点，为悬挂边，为环，为平行边，重数2，

为多重图。4、完全图设为阶无向简单图，若中每个顶点都与其余个顶点相邻，则称

为阶无向完全图，记作。若有向图的任一对顶点，既有有向边又有有向边，则称为有向完全图。例如：二、顶点的度数，握手定理。1、顶点的度数

(简称度)。无向图的度数记，指与，相关联的边的条数。有向图的度数，二、顶点的度数，握手定理。1、顶点的度数

(简称度)。最大度

最小度对有向图相应地还有，，，。如例1的(2)中，，。设为图的顶点集，称

为的度数序列。2、握手定理。定理1：设图为无向图或有向图，为边数)，，(则定理2：设为有向图，，则，。2、握手定理推论：任何图中，度为奇数的顶点个数为偶数。

例2、(1)能成为图的度数

，序列吗？为什么？(2)已知图中有10条边，4个3度顶点，其余顶点的度数均小于3，问中至少有多少个顶点？为什么？三、子图，补图。1、子图定义：设是两个图，若，，且，则称是的子图，是的母图，记作。真子图——且(即或)。生成子图——且。三、子图，补图。导出子图——非空，以为顶点集，以两端均在中的边的全体为边集的的子图，称的导出子图。——非空，以为边集，以中边关联的顶点的全体为顶点集的的子图，称的导出子图。例3、上图中，(1)－(6)都是(1)的子图，其中(2)－(6)为真子图，(1)－(5)为生成子图。2、补图定义。设为无向完全图，，为无向简单图，其中，，则称，相对于互为补图，记，。如例3中，四、图的同构。定义：设两个无向图，，若存在双射函数，使得对于任意的，当且仅当并且与重数相同，则称与同构，记作。例4、例5、(1)画出4个顶点，3条边的所有非同构的无向简单图。解：只有如下3个图：例5、(2)画出3个顶点，2条边的所有非同构的有向简单图。解：只有如下4个图：第二节

通路，回路，图的连通性

内容：图的通路，回路，连通性。重点：1、通路，回路，简单通路，回路，初级通路，回路的定义，2、图的连通性的概念，3、短程线，距离的概念。一、通路，回路。1、通路

(回路)中顶点和边的交替序列——，其中(无向图)，或(有向图)，——始点，——终点，称为到的通路。当时，为回路。一、通路，回路。2、简单通路，简单回路。简单通路

(迹)简单回路

(闭迹)复杂通路

(回路)一、通路，回路。3、初级通路，初级回路。初级通路

(路径)初级回路

(圈)初级通路

(回路)简单通路

(回路)，但反之不真。4、通路，回路的长度——中边的数目。例1、(1)图(1)中，从的通路有：到…………长度3长度6长度6例1、(1)图(1)中，从的通路有：到…………初级通路简单通路复杂通路例1、(2)…………长度3长度4长度7图(2)中过)有：的回路

(从到例1、(2)…………初级回路(圈)初级回路(圈)复杂回路图(2)中过)有：的回路

(从到5、图中最短的回路。如图：6、性质。定理：阶图中，若从顶点到存在通路，则从到存在长度小于等于在一个的通路。推论：阶图中，若从顶点到存在通路，则从到存在长度小于等于在一个的初级通路。6、性质。定理：阶图中，若到自身存在回路，则从到自身存在长度小于等于的回路。在一个推论：阶图中，若到自身存在一个简单回路，则从到自身存在长度小于等于的初级回路。在一个6、性质。由以上定理可知，在阶图中，任何一条初级通路的长度任何一条初级回路的长度二、图的连通性。1、连通，可达。无向图中，从到存在通路，称到是连通的(双向)。有向图中，从到存在通路，称可达(注意方向)。2、短程线，距离。短程线——连通或可达的两点间长度最短的通路。距离——短程线的长度，记无向图有向图2、短程线，距离。若之间无通路(或不可达)，规定距离满足：(1)，时，等号成立。

(2)若是无向图，还具有对称性，。3、无向图的连通。为连通图——是平凡图，或都是连通的。中任两点为非连通图——中至少有两点不连通。3、无向图的连通。设是一个无向图，是中顶点之间的连通关系，则是等价关系。设将划分成个等价类：，由它们导出的子图称为的连通分支，其个数记为4、有向图的连通。——中任一对顶点都互相可达(双向)——中任一对顶点至少一向可达——略去中有向边的方向后得到的无向图连通连通强连通单向连通弱连通强连通单向连通弱连通例2、强连通单向连通例2、单向连通弱连通非连通图第三节

图的矩阵表示内容：关联矩阵，邻接矩阵，可达矩阵。重点：1、有向图，无向图的关联矩阵，2、有向图的邻接矩阵。了解：有向图的可达矩阵。一、无向图的关联矩阵。1、设无向图，，，的关联矩阵，例1、无向图(下图所示)，求。解：2、性质。(1)(2)(3)握手定理(4)，当且仅当为孤立点。2、性质。(5)若第列与第列相同，则说明与为平行边。二、有向图的关联矩阵。1、设无环有向图，，，的关联矩阵，其中例2、有向图(下图所示)，求。解：2、性质。(1)(2)(3)三、有向图的邻接矩阵。1、设有向图，，的邻接矩阵，，其中指邻接到的边的条数

(非负整数)。例3、有向图(下图所示)，求。解：2、性质。(1)(2)(3)(4)为中环的个数。3、求中长度为的通路数和回路数。(1)令矩阵乘法其中表示从到长度为2的通路数或回路数。3、求中长度为的通路数和回路数。考虑，简记为。其中表示从到长度为或回路数。的通路数中长度为为的通路总数，其中为中长度为的回路总数。3、求中长度为的通路数和回路数。(2)设则中元素为中到长度小于等于的通路总数，为中长度小于等于的通路总数，其中为中长度小于等于的回路总数。例4、在例3的有向图中求，，。解：，，四、有向图的可达性矩阵。(了解)设为有向图，，令，四、有向图的可达性矩阵。(了解)可达性矩阵其中元素可由求得：第七章

小结与例题一、无向图与有向图。1、基本概念。有向图与无向图的定义；关联与邻接(相邻)；顶点的度数；零图与平凡图；简单图与多重图；完全图；子图，补图；图的同构。一、无向图与有向图。2、运用。(1)灵活运用握手定理及其推论，(2)判断两个图是否同构，(3)画出满足某些条件的子图，补图等。二、通路，回路，图的连通性。1、基本概念。通路和回路；无向图和有向图中顶点之间的可达关系；短程线，距离；有向图连通的分类。二、通路，回路，图的连通性。2、运用。(1)判断有向图或无向图中通路(回路)的类型。(2)求短程线和距离。(3)判断有向图连通的类型。三、图的矩阵表示。1、基本概念。无向图的关联矩阵，有向图的关联矩阵和邻接矩阵。2、运用。(1)关联矩阵的行和、顶点度数间的关系。(2)由有向图的邻接矩阵的次幂求从一顶点到另一顶点的长度为的通路数。例1、设图，其中，分别由下面给出。判断哪些是简单图，哪些是多重图？(1)(2)(3)简单图多重图不是例1、设图，其中，分别由下面给出。判断哪些是简单图，哪些是多重图？(4)(5)(6)简单图多重图不是例2、下列各序列中，可以构成无向简单图的度数序列的有哪些？(1)可以(2)不可以(3)可以(4)不可以(5)不可以例3、右图所示的无向图中，分别求：不同的初级通路(路径)。(1)之间所有解：有7条，分别为，，，，和，。(2)之间的短程线。(3)。解：。解：。例4、(1)画出完全图的所有非同构的生成子图。解：例4、(1)画出完全图的所有非同构的生成子图。解：例4、(1)画出完全图的所有非同构的生成子图。(2)的生成子图有几个是连通图？解：有6个：例5、下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？强连通单向连通弱连通例5、下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？单向连通强连通强连通例6、已知图的邻接矩阵，，(1)例6、已知图的邻接矩阵，，(2)从到长度为2的通路数。解：因，所以从到长度为2的通路数为2。例6、已知图的邻接矩阵，，(3)从到长度为3的通路数。解：因，所以从到长度为3的通路数为5。例6、已知图的邻接矩阵，，(4)过长度为3的回路数。解：因，所以过长度为3的回路数为3。例7、下列各图中各有多少个顶点。(1)16条边，每个顶点的度数均为2。解：设顶点数为，由握手定理，有，解得。解：设顶点数为，解得。(2)21条边，3个度数为4的顶点，其余顶点的度数均为3。有，由握手定理，例7、下列各图中各有多少个顶点。(3)24条边，每个顶点的度数均相同。解：设顶点数为，由握手定理，设每个顶点的度数均为，其正整数解有：，，，，，，，。，则有例7、下列各图中各有多少个顶点。(3)24条边，每个顶点的度数均相同。