6.1 概述

  • 「图 graph」 GG 由两个集合组成:一个由 「顶点 vertex」 构成的有穷非空集合和一个由 「边 edge」 构成的有穷集合。V(G)V(G)E(G)E(G) 分别表示图 GG 的顶点集和边集,有时也用 G=(V,E)G = (V, E) 表示图。
  • 「无向图 undirected graph」 是表示边的两个顶点之间没有次序关系的图。例如,顶点对 (v0,v1)(v_0, v_1)(v1,v0)(v_1, v_0) 表示同一条边。
  • 「有向图 directed graph」 是表示边的顶点对有方向的图。例如,顶点对 <v0,v1><v_0, v_1> 表示以顶点 v0v_0「尾 tail」,而以顶点 v1v_1「头 head」 的边。因此,在有向图中,<v0,v1><v_0, v_1><v1,v0><v_1, v_0> 表示两条不同的边。

6-1

对于无向图,用线段或弧线来表示边。而对于有向图,用带箭头的线段来表示边,箭头的方向从尾顶点指向头顶点。上图中,G1,G2G_1, G_2 是无向图,G3G_3 是有向图。

这三个图的集合表示形式为: V(G1)={0,1,2,3}E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}V(G2)={0,1,2,3,4,5,6}E(G2)={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)}V(G3)={0,1,2}E(G2)={<0,1>,<1,0>,<1,2>} \begin{array}{ll} V(G_1) = \{0, 1, 2, 3\} & E(G_1) = \{(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)\} \\ V(G_2) = \{0, 1, 2, 3, 4, 5, 6\} & E(G_2) = \{(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)\} \\ V(G_3) = \{0, 1, 2\} & E(G_2) = \{<0, 1>, <1, 0>, <1, 2>\} \end{array} 由于把图中所有边和所有顶点都定义为集合,所以通常在图上进行如下限制:

  1. 图中不能有从顶点 ii 到其自身的边,也就是说边 <vi,vi><v_i, v_i>(vi,vi)(v_i, v_i) 是不合法的。这样的边称为 「自身环 self loops」
  2. 同一条边在图中不能出现两次或两次以上。这样的边称为 「多重图 multigraph」
  • 「完全图 complete graph」 是具有最多边数的图。对于一个具有 nn 个顶点的无向图,边数的最大值等于不同的无序顶点对 (vi,vj)(v_i, v_j)(其中 iji \neq j)的数量,其值为 n(n1)/2n(n-1)/2,对于一个具有 nn 个顶点的有向图,边的条数最多为 n(n1)n(n-1)。如本节第一张图,G1G_1 是一个具有 4 个顶点的完全图,而 G2,G3G_2, G_3 不是完全图。
  • 如果 (v0,v1)(v_0, v_1) 是无向图中的一条边,则称顶点 v0v_0v1v_1「相邻的 adjacent」,并称边 (v0,v1)(v_0, v_1) 与顶点 v0v_0v1v_1 「关联 incident」。如果 <v0,v1><v_0, v_1> 是有向图的一条边,则称顶点 v0v_0 「邻接到」 顶点 v1v_1,而称 v1v_1 「邻接于」 v0v_0,并称边 <v0,v1><v_0, v_1> 与顶点 v0v_0v1v_1 「关联」
  • 若图 GG' 是图 GG「子图 subgraph」,则 GG' 满足 V(G)V(G)V(G') \subseteq V(G)E(G)E(G)E(G') \subseteq E(G)。下图给出了图 G1G_1 和图 G3G_3 的若干子图。

6-3

  • GG 中从顶点 vpv_pvqv_q 的一条 「路径 path」 是一个顶点序列 vp,vi1,vi2,,vin,vqv_p, v_{i_1}, v_{i_2}, \cdots, v_{i_n}, v_q,若 GG 为无向图,则 (vp,vi1),(vi1,vi2),,(vin,vq)(v_p, v_{i_1}), (v_{i_1}, v_{i_2}), \cdots, (v_{i_n}, v_q) 是无向图 GG 中的边;若 GG 为有向图,则 <vp,vi1>,<vi1,vi2>,,<vin,vq><v_p, v_{i_1}>, <v_{i_1}, v_{i_2}>, \cdots, <v_{i_n}, v_q> 是有向图 GG 中的路径。路径的 「长度 length」 是路径上边的条数。
  • 一条 「简单路径 simple path」 是指路径上除了起点和终点可能相同外,其余顶点都互不相同,可以用顶点序列来表示一条简单路径,例如,路径 (0,1),(1,3),(3,2)(0, 1), (1, 3), (3, 2) 可以写成 0,1,3,20, 1, 3, 2。在上图 G1G_1 中,路径 0,1,3,20, 1, 3, 20,1,3,10, 1, 3, 1 具有相同的长度,都是 3。前者是一条简单路径,而后者不是简单路径。在图 G3G_3 中,顶点序列 0,1,20, 1, 2 是一条 「简单有向路径 simple directed path」
  • 「回路」 又称 「环路 cycle」 是一条简单路径,且其起点和终点相同。例如,在图 G1G_1 中,路径 0,1,2,00, 1, 2, 0 是一个环路。在图 G3G_3 中,路径 0,1,00, 1, 0 也是一个环路,称为「有向环路」。
  • 在无向图中 GG 中,如果从顶点 v0v_0v1v_1 存在一条路径,则称顶点 v0v_0v1v_1「连通的 connected」。如果无向图 GG 中的每对顶点 viv_ivjv_j,都存在一条从 viv_ivjv_j 的路径,则称无向图 GG「连通图 connected graph」。上图 G1G_1G2G_2 就是连通图,而下图的 G4G_4 不是连通图。
  • 无向图的 「连通分支 connected component」,简称 「分支」,是无向图中的极大连通子图。上图 G4G_4 包含两个连通分支:H1H_1H2H_2。树是一个连通的无环图。
  • 在有向图 GG 中,如果每对不同的顶点 viv_ivjv_j,都存在从 viv_ivjv_j 以及从 vjv_jviv_i 的有向路径,则称有向图 GG「强连通的 strongly connected」。本节第一张图 G3G_3 不是强连通的,因为从顶点 22 到顶点 11 没有路径。「强连通分支 strongly connected component」 是有向图的极大强连通子图。下图为图 G3G_3 的两个强连通分支。
  • 顶点的 「度 degree」 是关联于该顶点的边的条数。图 G4G_4 的顶点 00 的度为 2。对于有向图,把顶点 vv「入度 in-degree」 定义为以 vv 为头(即箭头指向 vv)的边的条数,而其 「出度 out-degree」 定义为以 vv 为尾的边的条数。图 G3G_3 的顶点 11 的入度为 1,出度为 2,度为 3。如果具有 nn 个顶点的图 GG 的顶点 ii 的度为 did_i,则 GG 的边数为 (0n1di)/2(\sum_0^{n-1}d_i)/2
  • 「ADT 图1 Graph 是一个非空顶点的集合和一个无向边的集合,其中每条边都是一个顶点对。
class Graph
{
    Graph Create() {
        // return 一个空图
    }
    Graph InsertVertex(Graph graph, Vertex v) {
        // 向图 graph 中插入没有关联边的新顶点 v,return 改变后的图
    }
    Graph InsertEdge(Graph graph, Vertex v1, Vertex v2) {
        // 在图 graph 的顶点 v1 和顶点 v2 之间插入一条边,return 改变后的图
    }
    Graph DeleteVertex(Graph graph, Vertex v) {
        // 删除图 graph 的顶点 v 及与其关联的所有边,return 改变后的图
    }
    Graph DeleteEdge(Graph graph, Vertex v1, Vertex v2) {
        // 删除图 graph 的边 (v1, v2),顶点 v1, v2 不删除,return 改变后的图
    }
    bool IsEmpty(Graph graph) {
        if (graph == 空图) return true;
        else return false;
    }
    List Adjacent(Graph graph, Vertex v) {
        // return 顶点 v 的所有邻接顶点
    }
}
1. 在本章的其余部分,所提到的「图」,如没有特殊说明,均指「无向图」

results matching ""

    No results matching ""