第六章 图

Posted on In Views:

图

  • 图 G 由顶点集 V 和边集 E 组成，记为 G = (V, E)，其中 V(G) 表示图 G 中顶点的有限非空集；E(G) 表示图 G 中顶点之间的关系（边）集合。若 V = {v1, v2, …, vn}，则用 |V| 表示图 G 中顶点的个数，也称图 G 的阶，E = {(u, v) | u ∈ U, v ∈ V}，用 |E| 表示图 G 中边的条数。
  • 线性表可以是空表，树可以是空树，但图不可以是空，即 V 一定是非空集。而 E 可以为空集。
  • 若 E 是无向边（简称边）的有限集合时，则图 G 为无向图。边是顶点的无序对，**记为(v, w)或(w, v)，因为(v, w) = (w, v)**，其中 v、w 是顶点。可以说顶点 w 和顶点 v 互为邻接点。边(v, w)依附于顶点 w 和 v，或者说边(v, w)和顶点 v、w 相关联。
  • 若 E 是有向边（也称弧）的有限集合时，则图 G 为有向图。弧是顶点的有序对，记为<v, w>，其中 v、w 是顶点，v 称为弧尾，w 称为弧头，<v, w> 称为从顶点 v 到顶点 w 的弧，也称 v 邻接到 w，或 w 邻接自 v。**<v, w> != <w, v>**。
  • 简单图
    • 不存在重复边
    • 不存在顶点到自身的边
  • 多重图：图 G 中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则 G 为多重图。
  • 对于无向图：
    • 顶点 v 的度是指依附于该顶点的边的条数，记为 TD(v)
    • 在具有 n 个顶点、e 条边的无向图中，$\sum\limits_{i=1}^nTD(V_i) = 2e$，即无向图的全部顶点的度的和等于边数的2倍。
  • 对于有向图：
    • 入度是以顶点 v 为终点的有向边的数目，记为 ID(v)
    • 出度是以顶点 v 为起点的有向边的数目，记为 OD(v)
    • 顶点的 v 的度等于其入度和出度之和，即 TD(v) = ID(v) + OD(v)
    • 在具有 n 个顶点、 e 条边的有向图中， $\sum\limits_{i=1}^nID(V_i) = \sum\limits_{i=1}^nOD(V_i) = e$
  • 路径——顶点 vp 到顶点 vp 之间的一条路径是指顶点序列，Vp, Vi1, Vi2, …, Vq。
  • 回路——第一个顶点和最后一个顶点相同的路径称为回路或环。
  • 简单路径——在路径序列中，顶点不重复出现的路径称为简单路径。
  • 简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
  • 路径长度——路径上边的数目。
  • 点到点的距离——从顶点 u 出发到顶点 v 的最短路径若存在，则此路径的长度称为从 u 到 v 的距离；若从 u 到 v 根本不存在路径，则记该距离为无穷（∞）。
  • 无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的。若图 G 中任意两个顶点都是连通的，则称图 G 为连通图，否则称为非连通图。
    • 对于 n个顶点的无向图 G，
      • 若 G 是连通图，则最少有 n-1 条边
      • 若 G 是非连通图，则最多可能有 $C_{n-1}^2$条边
  • 有向图中，若从顶点 v 到顶点 w 和从顶点 w 到顶点 v之间都有路径，则称这两个顶点是强连通的。
    • 对于 n 个顶点的有向图 G，若 G 是强连通图，则最少有 n 条边（形成回路）
  • 设有两个图 G = (V, E) 和 G’ = (V’, E’)，若 V‘ 是 V 的子集，且 E’ 是 E 的子集，则称 G’ 是 G 的子图。
  • 若有满足 V(G’) = V(G) 的子图 G’，则称其为 G 的生成子图。
  • 无向图中的极大连通子图（子图必须连通，且包含尽可能多的顶点和边）称为无向图的连通分量。
  • 有向图中的极大强连通子图（子图必须强连通，同时保留尽可能多的边）称为有向图的强连通分量。
  • 连通图的生成树是包含图中全部顶点的一个极小连通子图（边尽可能的少，但要保持连通）。若图中顶点树为 n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
  • 在非连通图中，连通分量的生成树构成了非连通图的生成森林。
  • 边的权——在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
  • 带权图/网——边上带有权值的图称为带权图，也称网。
  • 带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。
  • 无向完全图——无向图中任意两个顶点之间都存在边。
    • 若无向图的顶点数 |V| = n，则 |E|∈[0, $C^2_n$] = [0, n(n-1)/2]
  • 有向完全图——有向图中任意两个顶点之间都存在方向相反的两条弧。
    • 若有向图的顶点数 |V| = n，则 |E|∈[0, 2$C^2_n$] = [0, n(n-1)]
  • 边数很少的图称为稀疏图，反之称为稠密图。二者没有绝对的界限，一般来说 |E| < |V|log|V| 时，可以将 G 视为稀疏图。
  • 树——不存在回路，且连通的无向图
    • n 个顶点的树，必有 n-1 条边
    • n 个顶点的图，若 |E| > n-1，则一定有回路
  • 有向树——一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树。