1 定义

图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。
图论 (Graph theory) 是数学的一个分支，图是图论的主要研究对象。
表达式：G=(V, E)
V：顶点（数据元素）的有穷非空集合。
E：边的有穷集合。
Graph = (Vertex, Edge)

2 基本术语

1、无向图：顶点之间相连的线我们称为边，每条边都是无方向的。

无向图
2、有向图：顶点之间相连的线我们称为弧，每条弧都是有方向的。

有向图
3、完全图：任意两点都有一条边相连。
（1）无向完全图：n个顶点，n(n-1)/2条边。

无向完全图
（2）有向完全图：n个顶点，n(n-1)条边。

有向完全图
4、稀疏图：有很少边或弧的图。
5、稠密图：有较多边或弧的图。
6、网：边/弧带权值的图。
7、邻接：有边/弧相连的两个顶点之间的关系。
（1）对于无向图来说，存在边(vi, vj)，则称vi和vj互为邻接点；
（2）对于有向图来说，存在弧<vi, vj>，则称vi邻接到vj，vj邻接于vi。
8、关联（依附）：边/弧与顶点之间的关系。
存在(vi, vj)/<vi, vj>，则称该边/弧关联于vi和vj。
9、顶点的度：与该顶点相关联的边的数目，记为TD(v)。（total degree）
在有向图中，顶点的度等于该顶点的入度和出度之和。
顶点v的入度是以v为终点的有向边的条数，记作ID(v)。（in degree）
顶点v的出度是以v为始点的有向边的条数，记作OD(v)。（out degree）
问：当有向图中仅1个顶点的入度为0，其余顶点的入度均为1，此时是何形状？（树）
10、路径：连续的边/弧构成的顶点序列。
11、路径长度：路径上边或弧的数目/权值之和。
12、回路（环）：第一个顶点和最后一个顶点相同的路径。
13、简单路径：除路径起点和终点==可以==相同外，其余顶点均不相同的路径。
14、简单回路（简单环）：除路径起点和终点相同外，其余顶点均不相同的路径。
15、连通图（强连通图）：在无（有）向图G=(V, {E})中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）。
16、权与网：图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网。
17、子图：设有两个图G=(V, {E})、G1=(V1, {E1})，若V1⊆V，E1⊆E，则称G1是G的子图。
18、连通分量（强连通分量）：
（1）无向图G的极大连通子图称为G的连通分量。（极大连通子图：该子图是G的连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。）
如下图所示：顶点a、b、c、d构成了该无向图的极大连通子图，也就是连通分量，但e、f任何一个顶点加入都会造成不连通。