|
图的概念
1.图的定义2.图的分类3.图的基本术语4. 图的表示
1.图的定义
图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为： G=(V，E) （G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。） 注意：线性表中元素个数为0，为空表；树中结点个数为0，为空树；图中顶点个数不能为0，但可以没有边。
2.图的分类
按边有无方向分类： 仅由无向边（任意两个顶点之间都是无向边）构成的图为无向图；仅由有向边构成的图为有向图。 按边数分类： 边数很多的图为稠密图；边数很少的图为稀疏图。 按有无平行边分类：含有平行边的图称多重图；非多重图称为线图；无环的线图称为简单图。 有向图中，两结点之间（包括结点自身）若有相同始点和相同终点的几条边，则这几条边称为平行边；无向图中，两结点a,b之间相互平行的边的条数称为(a,b)或的重数。 按边或结点是否含权分类： 赋权图。
3.图的基本术语
邻接、依附： 无向图中，任意两个顶点vi和vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，称边(vi，vj)依附于顶点vi和顶点vj。有向图同理，若存在弧，称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，称弧依附于顶点vi和顶点vj，称vj是vi的邻接点。 （线性结构中，数据元素之间只有线性关系；树结构中，结点之间有层次关系；图结构中，任一两个顶点之间都可能有关系）度： 无向图中，顶点的度是指依附于该顶点的边数，通常记为TD (v)。所有顶点度数之和等于边数的2倍。有向图中，顶点的入度指以该顶点为弧头的弧的数目，记为ID (v)，顶点的出度指以该顶点为弧尾的弧的数目，记为OD (v)。所有顶点的入度等于所有顶点的出度等于图的边数。无向完全图： 指任意两个顶点之间都存在边的无向图。 有向完全图： 指任意两个顶点之间都存在方向相反的两条弧的有向图。 （含有n个顶点的无向完全图有n×(n-1)/2条边。；含有n个顶点的有向完全图有n×(n-1)条边。）路径： 在无向图G=(V, E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2, …, vim=vq)，其中，(vij-1,vij)∈E（1≤j≤m）。若G是有向图，则路径也是有方向的，顶点序列满足∈E。一般图的路径是不唯一的。 路径长度： 非带权图：路径上边的数目；带权图：路径上个边的权之和。 简单路径： 序列中顶点不重复出现的路径。回路： 第一个顶点和最后一个顶点相同的路径。 简单回路： 除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。子图： 若图G=（V，E），G’=（V’，E’），如果V’属于V 且E’ 属于 E ，则称图G’是G的子图。连通图： 无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。 连通分量： 非连通图的极大连通子图称为连通分量。 （极大连通子图：含有极大顶点数，依附于这些顶点的所有边）。连通分量是对无向图的一种划分。强连通图： 在有向图中，对图中任意一对顶点vi和vj (i≠j)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。 **强连通分量：**非强连通图的极大强连通子图。生成树： n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。 生成森林： 在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。
4. 图的表示
邻接矩阵：设图G=，其中V={v1,v2,…vn}，假定结点已经有了从v1到vn的次序，则n阶方阵AG=(aij)n*n称为G的邻接矩阵。其中：若(vi,vj)∈E或∈E时，aij=1，否则aij=0.邻接表：顺序存储与链式存储相结合的表示图的一种方法。
|