图的基本定义和相关概念（一）

什么是图？

图是顶点与边的集合。一般表示为一个二元组，即：图 G=(V，E)。

• 数据对象 V:是具有相同特性的顶点的非空有限集合,顶点通常代表数据元素;

• 数据关系 E:是边的有限集合，边代表两个顶点间的关系。E={VR }，VR={< v,w>}

• 基本操作 P:13 个

例如下图：G=(V，E)

V={V1，V2，V3，V4}

E ={ e1, e2,e3, e4,e5}

图分为有向图和无向图。

无向图

无向图如果一个个图中的边都没有方向，则称该图为无向图。图中的边称为无向边。一般用一对圆括号括起来的顶点无序偶表示一条无向边。无向边代表对称、相等与兄弟关系。一条无向边相当于互相指向的两条有向边。

有向图

如果，图中每条边都有固定的方向， 则称该图为有向图。有向图中的边称为有向边(Directed edge)，一条有向边是用一对尖括号括起来的顶点有序偶表示的。有向边代表不对称、不相等或父子关系。

如上图中 e1=<v1 v2>≠〈v2 v1 〉，E={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}对于含有 n 个顶点，e 条边的有向图，设 ei 为一条有向边表示为:ei=<vi, vj>≠<vj,vi>; vi,vj ∈v; ei∈ E;称顶点 vi 为(有向边)弧 ei 的尾顶点;称顶点 vj 为 ei 的头顶点或称为终端顶点。

出度和入度

有向边的顶点度分为入度与出度。

称 ei 是与顶点 vi,vj 相关联的边.称自顶点 vi 邻接至顶点 vj。顶点 vi 的度 是与顶点 vi 相关联的边的条数。

顶点 vi 的入度是以顶点 v 为头的弧的条数。表示为 id(vi)

顶点 vi 的出度是以顶点 v 为尾的弧的条数。表示为 od(vi)

所以顶点的度:Td(vi)=id(vi)+od(vi)

例如上图中:id(v1)=1; od(v1)= 2; id(v3)=1; od (v3) =1；Td(v1) = id (v1)+od(v1)= 3。