[关闭]
@guoxs 2016-01-01T12:34:10.000000Z 字数 2507 阅读 2075

数据结构之图的定义

数据结构与算法


图的定义

: 图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。
图的定义与线性表定义的对比:

1.1 各种图定义

无向边: 若顶点vi到vj之间的边没有方向,则称这条边为无向边(Edge),用无序偶对(vi,vj)来表示。
无向图: 如果图中任意两个顶点之间的边都是无向边,则称该图为无向图(Undirected graphs)。
对于无向图G1来说,G1=(V1,{E1}),其中顶点集合V1={A,B,C,D};边集合E1={(A,B),(B,C),(C,D),(D,A),(A,C)}。
无向图
有向边: 若从顶点vi到vj的边有方向,则称这条边为有向边,也称为弧(Arc)。用有序偶来表示,vi称为弧尾(Tail),vj称为弧头(Head)。
有向图: 如果图中任意两个顶点之间的边都是有向边,则称该图为有向图(Directed graphs)。
对于下有向图G2来说,G2=(V2,{E2}),其中顶点集合V2={A,B,C,D};弧集合E2={,,,}。
有向图

无向边用小括号“()”表示,而有向边则是用尖括号“<>”表示。

简单图: 在图中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。
无向完全图: 在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。

含有n个顶点的无向完全图有n(n-1)/2条边。

有向完全图: 在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。

含有n个顶点的有向完全图有n×(n-1)条边。

对于具有n个顶点和e条边数的图,无向图,有向图

稀疏图与稠密图: 有很少条边或弧的图称为稀疏图,反之称为稠密图。这里稀疏和稠密是模糊的概念,都是相对而言的。
: 有些图的边或弧具有与它相关的数字,这种与图的边或弧相关的数叫做权(Weight)。这些权可以表示从一个顶点到另一个顶点的距离或耗费。
: 带权的图通常称为网(Network)。
子图: 设有两个图G=(V,{E})和G'=(V',{E'}),如果$V'∈V且E'∈E,则称G'为G的子图(Sub-graph)。

1.2 图的顶点与边间关系

邻接点: 对于无向图G=(V,{E}),如果边(v,v')∈E,则称顶点v和v'互为邻接点(Adjacent),即v和v'相邻接。

边(v,v')依附(incident)于顶点v和v',或者说(v,v')与顶点v和v'相关联

: 顶点v的度(Degree)是和v相关联的边的数目,记为TD(v)。

对于有向图G=(V,{E}),如果弧∈E,则称顶点v**邻接到**顶点v',顶点v'**邻接自**顶点v。弧和顶点v,v'相关联。以顶点v为
头弧的数目称为v的入度(InDegree),记为ID(v);以v为尾的弧的数目称为v的出度(OutDegree),记为OD(v);顶点v的度为TD(v)=ID(v)+OD(v)。

路径: 无向图G=(V,{E})中从顶点v到顶点v'的路径(Path)是一个顶点序列。如果G是有向图,则路径也是有向的,顶点序列应满足

路径的长度是路径上的边或弧的数目。

回路: 第一个顶点和最后一个顶点相同的路径称为回路或环(Cycle)。
简单路径: 序列中顶点不重复出现的路径称为简单路径。
简单回路: 除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环。

1.3 连通图相关术语

连通: 在无向图G中,如果从顶点v到顶点v'有路径,则称v和v'是连通的。
连通图: 如果对于图中任意两个顶点vi、vj∈V,vi和vj都是连通的,则称G是连通图(Connected Graph)。
连通分量: 无向图中的极大连通子图称为连通分量。连通分量的概念强调:

强连通图: 在有向图G中,如果对于每一对vi、vj∈V、vi≠vj,从vi到vj和从vj到vi都存在路径,则称G是强连通图。
强连通分量: 有向图中的极大强连通子图称做有向图的强连通分量。
下图左边的并不是强连通图,因为顶点A到顶点D存在路径,而D到A就不存在。右边就是强连通图,而且显然图2是图1的极大强连通子图,即是它的强连通分量。
强连通分量
连通图的生成树: 所谓的一个连通图的生成树是一个极小的连通子图,它含有图中全部的n个顶点,但只有足以构成一棵树的n-1条边。
比如下图中图1是一普通图,但显然它不是生成树,当去掉两条构成环的边后,比如图2或图3,就满足n个顶点n-1条边且连通的定义了。它们都是一棵生成树。
连通图的生成树

如果一个图有n个顶点和小于n-1条边,则是非连通图,如果它多于n-1边条,必定构成一个环,因为这条边使得它依附的那两个顶点之间有了第二条路径。比如图2和图3,随便加哪两顶点的边都将构成环。不过有n-1条边并不一定是生成树,比如图4。

有向树: 如果一个有向图恰有一个顶点的入度为0,其余顶点的入度均为1,则是一个有向树。

对有向树的理解比较容易,所谓入度为0其实就相当于树中的根结点,其余顶点入度为1就是说树的非根结点的双亲只有一个。

有向图的生成森林: 一个有向图的生成森林由若干棵有向树组成,含有图中全部顶点,但只有足以构成若干棵不相交的有向树的弧。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注