由顶点集V和边集E组成,记为G = (V,E),顶点集V非空,边集E可以是空
有向边(弧)
弧的表示,v到w的弧或称v邻接到w
弧尾、弧头
无向边(边)
无向边的表示(v,w)
邻接点、依附、相关联
简单图:不存在重复边,且不存在顶点到自身的边的图
有向完全图:满边(含有n(n-1)条边)
无向完全图:满边(含有n(n-1)/2条边)
注意首先必须是图,其次子图G'的顶点集和边集分别是图G的顶点集和边集的子集
在无向图中,若顶点v和w之间有路径存在,则称v和w是连通的
若图中任意两个顶点都是连通的,则称图为连通图
无向图的极大连通子图(包含所有边)称为连通分量
无向图
在有向图中,如果有一对顶点v和w,从v到w和w到v都有路径,则称这两个顶点是强连通的
若图中任意一对顶点都是强连通的,则称此图为强连通分量
有向图中的极大强连通子图称为有向图的强连通分量
连通图的生成树是包含图中全部顶点的一个极小连通子图(包含所有顶点但边数最少),若图中顶点数为n,那么它的生成树含有n-1条边
在非连通图中,连通分量的生成树构成了非连通图的生成森林
顶点的度、入度、出度
每条边都可以标上具有某种含义的数值,该数值称为该边上的权值
边上带权值的图称为带权图,也称网
边数很少的图称为稀疏图,反之,边数很多的称为稠密图
路径上边的数目称为简单路径
第一个顶点和最后一个顶点相同的路径称为回路或环
顶点不重复出现的路径称为简单路径
除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单回路
两顶点之间最短路径的长度
一个顶点的入度为0,其余顶点的入度为1的有向图,称为有向树