8.1图 图的基本概念 图:由结点集合及结点间的关系集合组成的一种数据结构 记为G=(V,E),其中:是顶点集合,是有穷非空集;E 是的边集合,是有穷集。 2、有向图:图G中的每条边都是有方向的; 3、无向图:图G中的每条边都是无方向的; 4、完全图:图G任意两个顶点都有一条边相连接; 若n个顶点的无向图有m(n-1)2条边,称为无向完全图 若n个顶点的有向图有n(m-1)条边,称为有向完全图 v2 53 (a)有向图(b)有向图(c)无向完全(d2 ８.1 图 一、图的基本概念 １、图：由结点集合及结点间的关系集合组成的一种数据结构。 记为G＝( V, E )，其中：V是G的顶点集合，是有穷非空集；E 是G的边集合，是有穷集。 v1 v2 v3 v4 v5 v1 v2 v3 v4 2、有向图：图G中的每条边都是有方向的； ３、无向图：图G中的每条边都是无方向的； ４、完全图：图G任意两个顶点都有一条边相连接； ❖若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图 ❖若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图 (a)有向图 (b)有向图 (c)无向完全图 (d)有向完全图 1 2 3 1 4 2 3 4