图结构-图的相关概念

图结构-图的相关概念

图的基本定义

图(Graph)由顶点(Vertex)和边(Edge)组成。图中的元素叫顶点,图不能为空
在图中,任意两个元素之间都可能有关系,顶点之间的关系通过边来表示。图可以表示为 G(V,E),其中 G 表示图,V 表示顶点的集合,E 表示边的集合。


其中字母标识的节点就是图的顶点,节点之间的连线就是图的边。

无向图与有向图

无向图:全部由无向边构成的图称为无向图(Undirected Graph).
有向图: 全部由有向边(也叫弧)构成的图称为有向图(Directed Graph).


权和网

权: 在图的边或弧中给出相关的数(非负),称为权.
这种带权的图通常称作网。
同样网分为有向网和无向网.


无向完全图:无向图,边的取值范围是0到n(n-1)/2;边数达到最大值n(n-1)/2条边的无向图称为无向完全图

有向完全图: 有向图,边的取值范围是0到n(n-1);边数达到最大值n(n-1)条弧的有向图称为有向完全图

稀疏图和稠密图

在具有n个顶点,e条边的图G中,如果含有的边较少,则称图G为稀疏图,否则为稠密图
邻接点: 假若顶点v 和顶点w 之间存在一条边(或弧), 则称顶点v 和w 互为邻接点。

顶点的度(Degree):是图中与该顶点相关联边的数目, 顶点V的度记为D(V)

入度和出度: 在有向图中,以顶点V为终点的弧称为入度,记为 ID(V);以顶点V为起点的弧称为出度,记为 OD(V);该顶点V的度为D(V) = ID(V) + OD(V)

所有顶点度和与边数e的关系:所有顶点度的和为所有边数的两倍

路径:在一个图中,路径是从顶点u到顶点v所经过的顶点序列,即{u=v0,v1,...,vi=v}

路径长度: 路径上的边数或弧的数目

回路(环): 第一个顶点和最后一个顶点相同的路径

初等路径: 序列中顶点不重复出现的路径

初等回路(环):除第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路

连通图(Connected Graph): 在无向图中,从顶点u到到顶点v有路径,则称顶点u与顶点v连通,图中任意两个顶点连通,则称该图为连通图


子图: 假设有两个图G=(V,{E}),和G' = (V',{E'}),如果V' 属于V,E'属于E,则称G' 为G的子图


强连通图:在有向图 G 中,对于每一对顶点,如果相互之间都存在路径,则 G 是强连通图。示例有向图不是强连通图,因为 A 到 D 存在路径,而 D 到 A 不存在。


图的应用场景

图的应用场景很多,比如社交网络中用户之间的关系,网络设备之间的拓扑结构,以及现实生活中形形色色的网:公路网、铁路网、地铁网等,都可以通过图来表示。