1、完全图
在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向图有n(n-1)/2条边。
在有向图中,如果任意两个顶点之间都存在方向相反的两条弧,则称该图为有向完全图。含有n个顶点的有向完全图有n(n-1)条有向边。
2、连通、连通图和连通分量
在无向图中,若从顶点v到顶点W有路径存在,则称v和w是连通的。
若图G中任意两个顶点都是连通的,则称图G为连通图。
无向图中的极大连通子图称为连通分量。
如果一个图中有n个顶点,并且有小于n-1条边,则此图必是非连通图。
首先要区分极大连通子图和极小连通子图,极大连通子图是无向图的连通分量,极大即要求该连通子图包含其所有边;
极小连通子图是既要保持图连通,又要使得边数最小的子图。
3、强连通图、强连通分量
在有向图中,若从顶点v到顶点w和从顶点w到顶点v之间都有路径,则称这两个顶点是强连通的。
若图中任何一对顶点都是强连通的,则称该图为强连通图。
有向图中的极大强连通子图称为有向图的强连通分量。
注意:强连通图,强连通分量只是针对有向图而言。一般在无向图中讨论连通性,在有向图中考虑强连通性。
4、生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n,则它的生成树含有n-1条边。对于生成树而言,若砍去它的一条边,则会变成非连通图,若加上一条边则会形成一个回路。在非连通图中,连通分量的生成树构成了非连通图的生成森林。
注意:包含有向图中全部顶点的极小连通子图,只有生成树满足条件,因为砍去生成树的任一条边,图将不再连通。
5、顶点的度、入度和出度
图中每个顶点的度定义为该顶点一个端点的边的数目。
对于无向图,顶点v的度是指衣服与该顶点的边的条目,记为TD(v).
在具有n个顶点e条边的无向图中,有连加TD(v)=2e。即无向图的全部顶点的度之和等于边数的两倍,这是因为每条边和两个顶点相互关联。
对于有向图,顶点v的度分为入度和出度,入度是以顶点v为终点的有向边的数目,记为ID(v);而出度是以顶点v为起点的有向边的数目,记为OD(v)。顶点v的度等于其入度和出度之和,即TD(v)=ID(v)+OD(v).
在具有n个顶点e条边的有向图中,有连加ID(Vi)=OD(Vi)=e,即有向图的全部顶点的入度之和出度之和相等并且等于边数。这是因为每条有向边都有一个起点和终点。
6、路径、路径长度和回路
顶点Vp到顶点Vq之间的一条路径是指顶点序列Vp,Vi1,Vi2,……,Vim,Vq。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。如果一个图有n个顶点,并且有大于n-1条边,则此图一定有环。
7、简单路径、简单回路
在路径序列中,顶点不重复出现的路径称为简单路径。
除第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路称为简单回路。
8、距离
从顶点u出发到顶点v的最短路径若存在,则该路径的长度称为从u到v的距离,若从u到v根本不存在路径,则记该距离为无穷。
9、有向树
有一个顶点的入度为0,其余顶点的入度均为1的有向图称为有向树。
10、简单图
一个图G如果满足:
①不存在重复边。
②与存在顶点到自身的边,则称图G为简单图。