第三章图与遍历算法 §1图的基本概念和术语 ●无向图( undirected graph) 哥尼斯堡七桥 Euler 图 无向图,简称图,是一个用线(边)连接在一起的节点(顶点)的集合。严 格地说,图是一个三元组G=(V,E,I),其中,V是顶点的集合,E是边的集 合,而I是关联关系,它指明了E中的每条边与V中的每个顶点之间的关联关 系:每条边必定连接两个而且只有两个顶点,它们称为该边的端点。连接顶点v 的边的条数称为v的度,记做d(v).图G=(V,E,I)中顶点的度与边数有如下 关系 ∑d(v)=2|E (3.1.1) 由公式(1)可知,图中奇度顶点的个数一定是偶数。 没有重边的图称为简单图,n阶完全图是指具有n个顶点而且每两个顶点之 间都有边连接的简单图,这样的图的边数为n(n-1)/2.以下是1-4阶的完全图第三章 图与遍历算法 §1 图的基本概念和术语 z 无向图(undirected graph) 哥尼斯堡七桥 Euler 图 无向图，简称图，是一个用线（边）连接在一起的节点（顶点）的集合。严 格地说，图是一个三元组 G=( V, E, I ), 其中，V 是顶点的集合，E 是边的集 合，而 I 是关联关系，它指明了 E 中的每条边与 V 中的每个顶点之间的关联关 系：每条边必定连接两个而且只有两个顶点，它们称为该边的端点。连接顶点 v 的边的条数称为 v 的度，记做 d(v). 图 G=( V, E, I )中顶点的度与边数有如下 关系 d(v) 2 | E | v V ∑ = ∈ （3.1.1） 由公式（1）可知，图中奇度顶点的个数一定是偶数。 没有重边的图称为简单图，n 阶完全图是指具有 n 个顶点而且每两个顶点之 间都有边连接的简单图，这样的图的边数为 n(n-1)/2.以下是 1－4 阶的完全图：