Faster, Higher, Stronger
更快,更高,更强

图的概念 度、有向图、无向图、路径、连通图

在图结构中,对节点的前驱和后继的个数都不加限制,结点和结点之间的关系可以是任意的。在图中,结点习惯地称为顶点(vertex)。

图G由两个集合V和E组成,记做G=(V, E),其中V是顶点(vertex)的非空有穷集合,E是边(edge)的有穷集合,而边是V中的顶点偶对。通常,也把图G中的顶点集和边集记作V(G)和E(G)。

若图G中表示每一条边的顶点的偶对都是无序的,则称此图为无向图(undirected graph)。在无向图中,边的顶点偶对通常用圆括号括起来。(Vi, Vj)与(Vj, Vi)这两个顶点偶对表示着同一条边。

若图G中表示每一条边的顶点的偶对都是有序的,则称此图为有向图(directed graph)。在有向图中,边的顶点偶对通常用尖括号括起来,<Vi, Vj>表示一条有向边,Vi称为边的始点,Vj称为边的终点。<Vi, Vj>与<Vj, Vi>这两个顶点偶对表示着两条不同的边。

在下面的讨论中,我们考虑顶点到其自身的边,即若(Vi, Vj)或<Vi, Vj>是图G的一条边,则要求Vi≠Vj。此外,也不允许一条边在图中重复出现。即,这里只考虑简单的图。

按上述规定,容易得到以下结论。

  1. 任何一个具有n个顶点的无向图,其边数小于等于n(n-1)/2。我们把边数等于n(n-1)/2的无向图称为无向完全图(undirected complete graph),简称完全图。在一个具有n个顶点的有向图中,其边数小于等于n(n-1)。边数恰好等于n(n-1)的有向图称为完全有向图(directed complete graph)。
  2. 若(Vi, Vj)∈E,则称Vi、Vj是相邻顶点(adjacent vertex),或称Vi与Vj相邻接;而边(Vi, Vj)则是与Vi和Vj相关联的边。若<Vi, Vj>是有向图中的一条边,则称顶点Vi邻接到顶点Vj,顶点Vj邻接与顶点Vi,而边<Vi, Vj>是与顶点Vi和Vj相关联的。
  3. 顶点v的度(degree)是与该顶点相关联的边的数目,基座D(v)。若G为有向图,则把以顶点v为始点的边的数目,称为v的出度(out degree),记作OD(v);把以顶点v为终点的边的数目,称为v的入度(in degree),记作ID(v)。显然,D(v) = OD(v) + ID(v)。

设图G有n个顶点,e条边,它们和顶点的度数有如下关系:

设有两个图G = (V, E)和G’ = (V’, E’),若V’∈V,E’∈E,则称图G’是图G的子图(subgraph)。

在图G = (V, E)中,如果存在顶点序列Vp, Vi1, Vi2, …, Vim, Vq,使得(Vp, Vi1), (Vi1, Vi2), …, (Vim, Vq)均在E(G)中(若对于有向图,则使得<Vp, Vi1>, <Vi1, Vi2>, …, <Vim, Vq>均在E(G)中),则称从顶点Vp到顶点Vq存在一条路径(path)。路径长度定义为该路径上边的数目。若一条路径上除顶点Vp和Vq可以相同外,其他顶点均不相同,则称此路径为简单路径。起点和终点重合(Vp = Vq)的路径称为回路或环(circle)。起点和终点重合(Vp = Vq)的简单路径称为简单回路或简单环。

在一个有向图中,若存在一个顶点V0,从该顶点有路径可以达到图中其他所有顶点,则称此图为有根的有向图,V0称作图的根。

在无向图G = (V, E)中,如果从顶点Vi到顶点Vj有路径(显然从顶点Vj到顶点Vi也一定存在路径),则称顶点Vi和Vj是连通的。若图G中任何一对顶点Vi和Vj(Vi ≠ Vj)都是连通的,则称此图是连通图(connected graph)。无向图的极大连通子图称为此图的连通分支。无向图的极大连通子图称为此图的连通分支。连通分支又称为连通分量(connected component)。

在有向图G = (V, E)中,若对于G中的任何两个不同的顶点Vi和Vj,都存在Vi到Vj及Vj到Vi的(有向)路径,则称图G是强连通图(strongly connected graph)。有向图的极大强连通子图称为此图的强连通分支(量)。

连通图的生成树(spanning tree)是它的极小连通子图,对于n各顶点的连通图,它的生成树含有n-1条边。

给图的每一条边添加上一个数字作为权,则称为带权的图。带权的连通图又称为网络(network)。通常权是具有某种意义的数,比如他们可以表示两个顶点之间的距离、行车的时间等,一般可理解为与实际问题相关的代价或耗费。

赞(0) 打赏(金额可任意指定)
未经允许不得转载:峰间的云 » 图的概念

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏