文档介绍：图的定义与相关概念
图G也是由数据元素集合V与边的集合E构成的。在图中,数据元素通常称为顶点(Vertex)。其中,顶点集合V不能为空,边表示顶点之间的关系。
若<x,y>∈E,则<x,y>表示从顶点x到顶点y存在一条弧(Arc),x称为弧尾(tail)或起始点(initial node),y称为弧头(head)或终端点(terminal node)。这样的图被称为有向图(digraph)。
如果<x,y>∈E且有<y,x>∈E,即E是对称的,则用无序对(x,y)代替有序对<x,y>和<y,x>,表示x与y之间存在一条边(edge),这样的图称为无向图(undigraph)。。
图的定义与相关概念
图G的形式化定义为:G=(V,E),其中,V={x|x∈数据元素集合},E={<x,y>|Path(x,y)/\(x∈V,y∈V)}。Path(x,y)表示<x,y>的意义或信息。
,有向图G1可以表示为G1=(V1,E1),其中,顶点的集合为V1={a,b,c,d},边的集合为E1={<a,b>,<a,d>,<b,c>,<c,a>,<c,b>,<d,c>}。无向图G2可以表示为G2=(V2,E2),其中,顶点的集合为V2={a,b,c,d},边的集合为E2={(a,b),(a,c),(a,d),(b,c),(c,d)}。
图的定义与相关概念
对于无向图G=(V,E),若边(vi,vj)∈E,则称vi和vj互为邻接点(adjacent),即vi和vj相邻接。边(vi,vj)依附于顶点vi和vj,或者说(vi,vj)与顶点vi、vj相关联。对于有向图G=(V,A),若弧<vi,vj>∈A,则称顶点vi邻接到顶点vj,顶点vj邻接自顶点vi。弧<vi,vj>和顶点vi、vj相关联。
无向图G2的边的集合为E={(a,b),(a,c),(a,d),(b,c),(c,d)},顶点a和b互为邻接点,边(a,b)依附于顶点a和b。顶点c和d互为邻接点,边(c,d)依附于顶点c和d。有向图G1的弧的集合为A={<a,b>,<a,d>,<b,c>,<c,a>,<c,b>,<d,c>},顶点a邻接到顶点b,弧<a,b>与顶点a和b相关联。顶点c邻接自顶点d,弧<d,c>与顶点d和c相关联。
图的定义与相关概念
对于无向图,顶点v的度是指与v相关联的边的数目,记作TD(v)。对于有向图,以顶点v为弧头的数目称为顶点v的入度(indegree),记作ID(v)。以顶点v为弧尾的数目称为v的出度(outdegree),记作OD(v)。顶点v的度(degree)为TD(v)=ID(v)+OD(v)。
无向图G2中顶点a的度为3,顶点b的度为2,顶点c的度为3,顶点d的度为2。有向图G1的弧的集合为A={<a,b>,<a,d>,<b,c>,<c,a>,<c,b>,<d,c>},顶点a、b、c和d的入度分别为1、2、2和1,顶点a、b、c和d的出度分别为2、1、2和1,顶点a、b、c和d的度分别为3、3、4和2。
若图的顶点的个数为n,边数或弧数为e,顶点vi的度记作TD(vi),则顶点的度与弧或者边数满足关系:e=
图的定义与相关概念
无向图G中,从顶点v到顶点v’的路径(path)是从v出发,经过一系列的顶点序列到达顶点v’。如果G是有向图,则路径也是有向的,路径的长度是路径上弧或边的数目。第一个顶点和最后一个顶点相同的路径称为回路或环(cycle)。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点外,其他顶点不重复出现的回路,称为简单回路或简单环。
,顶点序列a→d→c→a构成了一个简单回路。在无向图G2中,从顶点a到顶点c所经过的路径为a,d和c(或a、b、c)。
图的定义与相关概念
假设存在两个图G={V,E}和G’={V’,E’},若G’的顶点和关系都是V的子集,即有V’V,E’E,则G’为G的子图。。
图的定义与相关概念
对于无向图G,如果从顶点vi到顶点vj存在路径,则称vi到vj是连通的。如果对于图中任意两个顶点vi、vj∈V,vi和vj都是连通的,则称G是连通图(connected graph)。无向图中的极大连通子图称为连通分量。。
图的定义与相关概念
对于有向图G,如果对每一对顶点vi和vj,且vi≠vj,从vi到vj和vj到vi都存在路径,则G为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。有向图G4与