对于弧(来讲在关系中a称 为有序对中的第一个元素b称 的点而为第二个元素。 音神O点 在图论中,称a为起点,b为终 b c)b称a与弧(a,b)关联,b与弧(a,b) 关联。 g弧(c,c),f,这种起点与终点相 同的弧就称为自环 在图中,g与E中任何元素(弧) 都不关联,称为孤立点。 例如有向图G=(V,E,V={a,b,d,e,fg}, °E={(a,b),(a,c),(b,c),(c,a),(c,c),(c,e),(d,a,(d2c),(f,e) (f,)}, 弧(a,b表示从顶点a到顶点b的一条带箭头的线
• 例如有向图G=(V,E),V={a,b,c,d,e,f,g}, • E={(a,b),(a,c),(b,c),(c,a),(c,c),(c,e),(d,a),(d,c),(f,e), (f,f)}, • 弧(a,b)表示从顶点a到顶点b的一条带箭头的线。 对于弧(a,b)来讲,在关系中a称 为有序对中的第一个元素,b称 为第二个元素。 在图论中，称a为起点，b为终 点。 称a与弧(a,b)关联，b与弧(a,b) 关联。 弧(c,c),(f,f)这种起点与终点相 同的弧就称为自环。 在图中，g与E中任何元素(弧) 都不关联，称为孤立点
b称为弧(a,b)的端点,a ()音 对应的孤④,b称为自 一中任何弧都不关联 9点。与一条弧相关联 接的或相邻的。一顶 d3这些弧是弧邻接或弧 相邻。 例如上图中a与b相邻;c与d相邻;(a,b)与(b,c) 弧相邻
• 定义5.2：顶点a和b称为弧(a,b)的端点,a 为起点,b为终点。称a和b与弧(a,b)关联。 若顶点a和b相同,则对应的弧(a,b)称为自 环。若V中某顶点与E中任何弧都不关联, 则该顶点称为孤立点。与一条弧相关联 的两个顶点称为邻接的或相邻的。一顶 点关联于几条弧,称这些弧是弧邻接或弧 相邻。 例如上图中a与b相邻;c与d相邻;(a,b)与(b,c) 弧相邻
察它的顶点与弧的连接关 有的性质。至于各顶点之 长短曲直都是无关紧要的 的元素都是有序对,若改 eV面介绍的无向图。 个非空集,E是以中两 3 集为元素的集合,称有 4 7 该图的 15V23495 6},E={{v1,V2,{v1,w5,{v2,V2}, {v2v3},{v2,V4},{v2,v53,v2,v53,{v32V4,{v4,v5} 边{v1,V2}关联于顶点a,b, 而{v2V2}这种关联的两个顶点是相同的称为自环。 而v不关联任何边,也称为孤立点。 顶点v同时关联边{v2,V4},{v3,V4},{v4,vs},称这些边为边邻接另外 在上图中,边{v2Vs}出现了两次,象这种两个顶点之间出现不止 一条的边称为多重边
• 在研究有向图时,只考察它的顶点与弧的连接关 系以及整个图形所具有的性质。至于各顶点之 间的相对位置及弧的长短曲直都是无关紧要的。 • 对于有向图，弧集中的元素都是有序对，若改 成无序对，则就是下面介绍的无向图。 • 定义5.3：设V是一个非空集,E是以V中两 个元素组成的多重集为元素的集合, 称有 序 对 ( V,E)为 无向图 ,也记为 G=(V,E)或 G(V,E)。V中的元素称为顶点或点,V称为 顶点集, E中的元素称为边,E称为边集。 • E中元素现在也是集合，由于可能出现{a,a} 这种情况，所以说E中元素是V中两个元 素组成的多重集。 该 图 的 V={v1 ,v2 ,v3 ,v4 ,v5 ,v6 }，E={{v1 ,v2 },{v1 ,v5 ,}，{v2 ,v2 }, {v2 ,v3 },{v2 ,v4 },{v2 ,v5 },{v2 ,v5 },{v3 ,v4 },{v4 ,v5 }}， 边{v1 ,v2 }关联于顶点a,b， 而{v2 ,v2 }这种关联的两个顶点是相同的称为自环。 而v6不关联任何边，也称为孤立点。 顶点v4同时关联边{v2 ,v4 },{v3 ,v4 },{v4 ,v5 }，称这些边为边邻接另外 在上图中，边{v2 ,v5 }出现了两次，象这种两个顶点之间出现不止 一条的边称为多重边
定义57:若图G=(V,E)中,连结两个顶点 之间的边可以不止一条这些边称为多重 边,则图G称为多重图。无自环的非多重 图称为简单图。边集为空集的图称为零 图。只有一个顶点的图称为平凡图。若 G中每两个顶点之间恰有一条边,则称G 为完全图。n个顶点的完全图记为Kn 在定义5.7中零图是指没有边的图,其每 个顶点为孤立点但顶点集V不能是空集。 同样在有向图中,也可定义多重弧,多 重有向图和简单有向图
• 定义5.7：若图G=(V,E)中, 连结两个顶点 之间的边可以不止一条这些边称为多重 边,则图G称为多重图。无自环的非多重 图称为简单图。边集为空集的图称为零 图。只有一个顶点的图称为平凡图。若 G中每两个顶点之间恰有一条边, 则称G 为完全图。n个顶点的完全图记为Kn。 • 在定义5.7 中,零图是指没有边的图,其每 个顶点为孤立点,但顶点集V不能是空集。 • 同样在有向图中，也可定义多重弧，多 重有向图和简单有向图
为了叙述方便起见简称无向图为图如果 在图(有向图)中顶点标以名称如上图中顶 点标a,b,c,d,e,f,这样的图(有向图称为标 定图有向图,否则称为非标定图(有向图) 下面主要考虑标定图。 如果一个图的顶点集和边集是有限的则称 该图为有限图,类似地定义有限有向图 我们这里讨论的图和有向图是指有限图和 有限有向图。 图(有向图的最本质的内容就是顶点与边 (弧)的关联关系。为了描述这一关系现在 引进一个重要的概念,即顶点的度数
• 为了叙述方便起见,简称无向图为图,如果 在图(有向图)中顶点标以名称,如上图中顶 点标a,b,c,d,e,f,g,这样的图(有向图)称为标 定图(有向图),否则称为非标定图(有向图)。 下面主要考虑标定图。 • 如果一个图的顶点集和边集是有限的,则称 该图为有限图, 类似地定义有限有向图。 我们这里讨论的图和有向图是指有限图和 有限有向图。 • 图(有向图)的最本质的内容就是顶点与边 (弧)的关联关系。为了描述这一关系,现在 引进一个重要的概念, 即顶点的度数