大话数据结构十七：图的一些概念

大话数据结构十七：图的一些概念2014-12-30图的基本术语：

1）图（Graph）：图G由两个集合V和E组成，记为G=（V,E），这里V是顶点的有穷非空集合，E是边（或弧）的集合，而边（或弧）是V中顶点的偶对。

顶点（Vertex）：图中的结点又称为顶点。

边（Edge）：相关顶点的偶对称为边。

2）有向图（Digraph）：若图G中的每条边都是有方向的，则称G为有向图。

弧（Arc）：又称为有向边。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。

弧尾（Tail）：边的始点。

弧头（Head）：边的终点。

3）无向图（Undigraph）：若图G中的每条边都是没有方向的，则称G为无向图。

无向完全图（Undirected Complete Graph）：恰好有n（n-1）/2的无向图。

有向完全图（Directed Complete Graph）：恰好有n（n-1）条弧的有向图。

邻接点（Adjacent）：若（vi,vj）是一条无向边，则称顶点vi和vj互为邻接点。

4）度（Degree）：无向图中顶点v的度是关联于该顶点的边的数目，记为TD（v）。

入度（Indegree）：若G为有向图，则把以顶点v为终点的边的数目，称为v的入度，记为ID（v）。

出度（Outdegree）：若G为有向图，则把以顶点v为始点的边的数目，称为v的出度，记为OD（v）。

如图①：A的度为3。

如图②：A的入度为2，出度为1，所以A的度为3。