第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)