西安电子科技大学出版社：面向21世纪高等学校计算机类专业系列教材《离散数学》课程教学资源（PPT课件讲稿）第8章 图的基本概念

第8章图的基本概念 第8章图的基本概念 8.1图的定义及相关术语 8,2通路回路图的连通性 83图的矩阵表示 8.4例题选解 习题八 dBac

第8章 图的基本概念 第8章 图的基本概念 8.1 图的定义及相关术语 8.2 通路回路图的连通性 8.3 图的矩阵表示 8.4 例题选解 习 题 八

第8章图的基本概念 8.1图的定义及相关术语 图 图论作为数学的分支给出了图的严格的数学定义, 为此我们首先给出无序积的概念。 A、B是任意两个非空集合,A与B的无序积记为 A&B,即 A&B={(a,b)k∈A,b∈B} 性质 (a,b)=(b,a)

第8章 图的基本概念 8.1 图的定义及相关术语 1.图 图论作为数学的分支给出了图的严格的数学定义， 为此我们首先给出无序积的概念。 A、B是任意两个非空集合，A与B的无序积记为 A&B,即 A&B={（a，b）|a∈A，b∈B} 性质: （a，b）=（b，a）

第8章图的基本概念 【例81.1】4={a,b,c},B={1,2},求A&B、 B&A和B&B。 解8B={(a,1),(an,2),(b,1) (b,2),(c,1),(c,3)}=B&A B&B={(1,1),(1,2),(2,2)}

第8章 图的基本概念 【例8.1.1】 A={a，b，c}，B={1，2}，求A&B、 B&A和B&B。 解 A&B={（a,1）,（a,2）,（b,1）, （b,2）,（c,1）,（c,3）}=B&A B&B={（1,1），（1,2），（2,2）}

第8章图的基本概念 定义81.1图是一个二元组G=〈V,E〉,其中V (⑧是顶点集,E是边集。当E是无序积&的多 重子集时,其元素为无向边,图G为无向图。当E是有 序积V×T的多重子集时,其元素为有向边,图G为有 向图。 所谓多重子集是指集中元素可以重复

第8章 图的基本概念 定义8.1.1 图是一个二元组G=〈V，E〉，其中V （V≠ ）是顶点集，E是边集。当E是无序积V&V的多 重子集时，其元素为无向边，图G为无向图。当E是有 序积V×V的多重子集时，其元素为有向边，图G为有 向图。 所谓多重子集是指集中元素可以重复。 

第8章图的基本概念 【例8.1.2】图8.1.1中(a)、(b)是无向图,图 (c)是有向图 图81.1(b)的v1、v2、v3、v4、v,这样的图称为 标定图。同时也可对边进行标定,这里e1=(v1,v2), 4 2,vs), es=(v2,"s),e6=(V4,v)。当e=(v,v)时,称 和v是e的端点,并称e与v和v相关联,当e=(v,v 是有向边时,又称v是e的起点,v是e;的终点。如果图 的顶点集V和边集E均是有穷集,则称图为有限图,本 书所讨论的均是有限图

第8章 图的基本概念 【例8.1.2】 图8.1.1中（a）、（b）是无向图，图 （c）是有向图。 图8.1.1（b）的v1、v2、v3、v4、v5，这样的图称为 标定图。同时也可对边进行标定，这里e1 =（v1，v2）， e2 =（v1，v4），e3 =（v1，v5），e4 =（v2，v5）， e5 =（v2，v5），e6 =（v4，v5）。当ei =（vj，vk）时，称 vj和vk是ei的端点，并称ei与vj和vk相关联，当ei =〈vj，vk〉 是有向边时，又称vj是ei的起点，vk是ei的终点。如果图 的顶点集V和边集E均是有穷集，则称图为有限图，本 书所讨论的均是有限图

第8章图的基本概念 图8.1.1

第8章 图的基本概念 图 8.1.1 (a) (b) (c) e 1 e2 e 3 e 4 e 5 e6 1 2 4 3 5

第8章图的基本概念 下面介绍一些图的基本概念和常用术语 邻接点同一条边的两个端点 孤立顶点没有边与之关联的顶点。 零图顶点集V非空但边集E为空集的图。 平凡图1,=m=0的图 邻接边关联同一个顶点的两条边。 环关联同一个顶点的一条边((ν,ν)或(ν,v〉)

第8章 图的基本概念 下面介绍一些图的基本概念和常用术语。 邻接点 同一条边的两个端点。 孤立顶点 没有边与之关联的顶点。 零图 顶点集V非空但边集E为空集的图。 平凡图 |V|=1，|E|=m=0的图。 邻接边 关联同一个顶点的两条边。 环 关联同一个顶点的一条边（（v，v）或〈v，v〉）

第8章图的基本概念 平行边关联一对顶点的m条边(m≥2,称重数,若 是有向边则应方向相同)。 多重图含有平行边(无环)的图 简单图不含平行边和环的图。 完全图每对顶点间均有边相连的无向简单图。n阶 完全图记作Kn 竞赛图在K的每条边上任取一个方向的有向图。 有向完全图每对顶点间均有一对方向相反的边相 连的有向图

第8章 图的基本概念 平行边 关联一对顶点的m条边（m≥2，称重数，若 是有向边则应方向相同）。 多重图 含有平行边（无环）的图。 简单图 不含平行边和环的图。 完全图 每对顶点间均有边相连的无向简单图。n阶 完全图记作Kn。 竞赛图 在Kn的每条边上任取一个方向的有向图。 有向完全图 每对顶点间均有一对方向相反的边相 连的有向图

第8章图的基本概念 由完全图的定义易知,无向完全图K的边数为 E(K =Ch=n(n-1) 有向完全图G的边数为 E(G)=n(n-1)

第8章 图的基本概念 由完全图的定义易知，无向完全图Kn的边数为 2 1 ( ) ( 1) 2 E K C n n n n = = − 有向完全图G的边数为 E G n n ( ) ( 1) = −

第8章图的基本概念 顶点的度数顶点所关联的边数。顶点v的度数记 作d(ν)。在有向图中,以顶点ν为起点的边数称顶点 v的出度,记作d(v);以顶点v为终点的边数称顶点v 的入度,记作a(v)

第8章 图的基本概念 顶点的度数 顶点所关联的边数。顶点v的度数记 作d（v）。在有向图中，以顶点v为起点的边数称顶点 v的出度，记作d +（v）;以顶点v为终点的边数称顶点v 的入度，记作d -（v）