图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系(边)集合
|V|表示图G中顶点的个数，也称图G的阶；|E|表示图G中边的条数
无向图和有向图：
简单图和多重图：
在图中，权通常是对边赋予的有意义的数值量，边上带权的图称为带权图或网图：
完全图：
稠密图、稀疏图
顶点的度：以该顶点为一个端点的边的数目
无向图顶点v的度为以v为端点的边的个数，记为TD(v)；n顶点、e条边的无向图中度的总数为2e
有向图：出度指以v为起点的有向边的条数，记OD(v)；入度指以v为终点的有向边的条数，记ID(v)；TD(v)=OD(v)+ID(v)；n顶点、e条边的有向图中出度、入度为e
有向树：一个顶点的入度为0，其余顶点的入度均为1的有向图
路径：图中顶点v到顶点w的顶点序列，序列中顶点不重复的路径称为简单路径
路径长度：路径上边的数目，若该路径最短则称其为距离
回路：第一个顶点和最后一个顶点相同的路径
除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为简单回路
子图：设有两个图G=(V,E)和G’=(V’,E’)，若V’是V的子集，且E’是E的子集，则称G’为G的子图；且若V(G)=V(G’)则称G’为G的生成子图
无向图只有连通：若从顶点v到顶点w有路径存在，则称v和w是连通【连通图：任意两个结点之间都是连通的】【连通分量：极大连通子图】
有向图只有强连通：若从顶点v到顶点w和顶点w到顶点v都有路径存在，则称v和w是强连通【强连通图：任意两个结点之间都是强连通的】【强连通分量：极大强连通子图】
对于G的一个(强)连通子图G’，如果不存在G的另一个(强)连通子图G’’，使得G’属于G’’，则称G’为G的(强)连通分量
极小连通子图：连通子图且包含的边最少
生成树：连通图包含全部顶点的一个极小连通子图(n个顶点图的生成树有n-1条边)
生成森林：非连通图所有连通分量的生成树组成连通森林