图
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合
- 在图中数据元素，我们称之为顶点（Vertex）
- 在图结构中，不允许没有顶点。在定义中，若V是顶点的集合，则强调了顶点集合V有穷非空。
- 在图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的
无向边：若顶点vi到vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对(vi,vj)来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图（Undirected graphs）
有向边：若从顶点vi到vj的边有方向，则称这条边为有向边，也称为弧（Arc），用有序偶对<vi,vj>来表示，vi称为弧尾（Tail），vj称为弧头（Head）。如果图中任意两个顶点之间的边都是有向边，则称为该图为有向图（Directed graphs）
在图中，若不存在顶点到其自身的边，且同一边不重复出现，则称这样的图为简单图。
在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。
在有向图中，如果任意两个顶点都存在方向互为相反的两条弧，则称该图为有向完全图。
有很少条边或弧的图称为稀疏图，反之称为稠密图。
与图的边或弧相关的数叫做权（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）
对于有向图G=(V,{E})，如果弧<v,v’>∊E，则称顶点v邻接到顶点v’，顶点v’邻接自顶点v。弧<v,v’>和顶点v，v’相关联。以顶点v为头的弧的数目称为v的入度（InDegree），记为ID（v）；以v为尾的弧的数目称为v的出度（OutDegree），记为OD（v）；顶点v的度为TD（v）=ID（v）+OD（v）
无向图G=(V,{E})中从顶点v到顶点v’到路径（Path）是一个顶点序列（v=vi,0,vi,1, … , vi,m=v’）其中(vi,j-1,vi,j)∊E，1<=j<=m
路径的长度是路径上的边或弧的数目
第一个顶点到最后一个顶点相同的路径称为回路或环（Cycle）。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环
连通图相关术语
在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是连通的。如果对于图中任意两个顶点vi、vj∊E，vi和vj都是连通的，则称G是连通图（Connected Gragh）
无向图中的极大连通子图称为连通分量
- 要是子图
- 子图要是连通的
- 连通子图含有极大顶点数
- 具有极大顶点数的连通子图包含依附于这些顶点的所有边
在有向图G中，如果对于每一对vi、vj∊V、vi⧧vj，从vi到vj和vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。
一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条
如果一个有向图恰好有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。
一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。
图的定义与术语总结
图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点弧构成。弧有弧尾和弧头之分。
图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边叫简单图。
图中顶点之间邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。
图上的边或弧上带权则称为网。
图中顶点存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称强连通分量。
无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入度为0其余项点入度为1点叫有向树。一个有向图由若干棵有向树构成生成森林。
参考资料：
