图的术语

图的定义：

• 图（Graph）是由顶点的有穷非空集合和顶点之间的边和集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，如下图所示。
• 线性表中把数据元素叫做元素，树中将数据元素叫做结点，在图中数据元素，将其称之为顶点（Vertex）。
• 线性表可以没有数据元素，称为空表。树中可以没有结点，叫做空树。图中不能没有顶点。
• 线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图中，任意两个顶点之间都可能有关系，顶点之间的关系用边来表示，边集可以是空的。
  图

各种图定义

• 无向边：若顶点vi到vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对（vi,vj）来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图，上图左图即为一个无向图（Undirected graphs）。
• 有向边：若从顶点vi到vj的边有方向，则称这条边为有向边，也称为弧(Arc)，用有序偶<vi,vj>来表示，vi称为弧尾，vj称为弧头。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。
• 在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图，下图中的两个图就不是简单图，我们介绍简单图。
  
• 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边。
• 在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。如下图所示。
  完全图
• 有很少条边或弧的图称为稀疏图，反之称为稠密图。
• 有些图的边或弧具有与它相关的的数字，这种与图的边或弧相关的数叫做权（Weight）。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常为网（Network）。如下图所示。
  网

• 假设有两个图G=(V,{E})和G’=(V’,{E’}),如果V’属于V，且E’属于E，则称G’为G的子图（SubGraph）。如下图所示，右图中各个图为左图的子图。

  
  子图

图的顶点与边的关系：

• 对于无向图G=(V,{E}),如果边（v,v’）属于E，则称顶点v和v’互为邻接点（Adjacent）,即v和v’相邻接。边（v,v’）依附（incident）于顶点v和v’，或者说（v,v’）与顶点v和v’相关联。顶点v的度（Degree）是和v相关联的边的数目，即为TD(v)。如上图中的无向图中，顶点A和B互为邻接点，边（A,B）依附于顶点A与B上，顶点A的度为3。
• 对于有向图G=(V,{E}),如果弧<v,v’>属于E，则称顶点v邻接到顶点v’，顶点v’邻接自顶点v。弧<v,v’>和顶点v,v’相关联。以顶点v为头的弧的数目称为v的入度（InDegree）,记为ID(v);以v为尾的弧的数目称为v的出度（OutDegree）,记为OID(v);顶点v的度为TD(v)=ID(v)+OD(v)。如上图中的有向图中，顶点A的入度为1（从B到A的弧），出度为2（A到E的弧，A到D的弧），所以度为3=1+2。
• 无向图G=(V,{E})中从顶点v到v’的路径（Path）是一个顶点序列（v=vi,0,vi,1,…,vi,m=v’）,其中(vi,j-1,vi,j)属于E，1<=j<=m.
• 如果G为有向图，则路径也是有向的，顶点序列满足<vi,j-1,vi,j>属于E，1<=j<=m。下图分别表示了无向图和有向图中从顶点B到顶点D的路径。
• 树中根节点到任意结点的路径是唯一的，但是图中顶点与顶点之间的路径不是唯一的。
  路径
• 路径的长度是路径上的边或弧的数目。
• 第一个顶点到最后一个顶点相同的路径称为回路或者环（cycle）。序列中顶点不重复的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或者简单环。下图中的无向图和有向图的粗线构成环，且都为简单环。最右边的图就不是简单环了，由于顶点B重复出现。
  环

连通图：

• 在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是连通的。如果对于图中任意两个顶点vi,vj属于V，vi和vj都是连通的，则称G是连通图（Connected Graph）。下图左图中，顶点A到B、C、D都是连通的，但A与E、F无路径，因此不是连通图。而右图就是连通图。

  
  连通图

• 无向图中的极大连通子图称为连通分量。即它需要满足：
  （1）是子图；
  （2）子图为连通图；
  （3）连通子图含有极大顶点数；
  （4）具有极大顶点数的连通子图包含依附于这些顶点的所有边。
  下图左图是一个无向非连通图，但是它有两个连通分量，如下图中间的两个图，而右图尽管是左图的子图，但是不满足连通子图的极大顶点数，因此它不是左图的连通分量。

  
  连通分量

• 在有向图G中，如果对于每一对vi、vj属于V、vi不等于vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。下图左图不是强连通图，因为顶点B到顶点C存在路径，而D到A就不存在。右图就是强连通图，且右图是左图的极大强连通子图，即是它的强连通分量。

  
  强连通分量
• 一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。
  下图1不是生成树，去掉两条构成环的边后，如图2和图3，就满足n个顶点n-1条边且连通的定义，它们都是生成树。故一个图有n个顶点和小于n-1条边，则是非连通图，如果多于n-1条边，必定构成一个环，因为这条边使得它依附的两个顶点有了第二条路径，图2和图3随便加两个顶点的边都会构成环，不过有n-1条边也不一定是生成树，如图4。
  生成树

• 如果一个有向图恰有一个顶点的入度为0，其余顶点的入度为1，则是一棵有向树。入度为0的其实就相当于树的根节点，其余顶点入度为1就是说树的非根节点的双亲只有一个。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。
  下图图1是一棵有向树，去掉一些弧后，可以分为两棵有向树图2和图3，这两棵树就是图1有向图的生成森林。

  
  生成森林