当前位置：网站首页>图的基本定义和相关概念（一）

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

2022-07-20 10:53:00 【InfoQ】

什么是图？

图是顶点与边的集合。一般表示为一个二元组，即：图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的头顶点或称为终端顶点。