【数学建模算法】（7）图与网络模型及方法：概论和基本概念

作者: 热爱学习的高老板 | 来源:发表于2019-08-09 15:12 被阅读10次

前面我们主要讲了数学规划问题，从这一部分开始我们进入下一部分：图和网络。

1.概论

图论起源于 18 世纪。第一篇图论论文是瑞士数学家欧拉于 1736 年发表的“哥尼斯堡的七座桥”。1847 年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷 $C_{n} H_{2 n+2}$ 的同分异构物时，也发现了树的概念。近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、运筹学，生物遗传学、心理学、经济学、社会学等学科中。

图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来，问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。

哥尼斯堡七桥问题

当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。
图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。

2.图与网络的基本概念

2.1.无向图

一个无向图(undirected graph)G是由一个非空有限集合 $V(G)$ 和 $V(G)$ 中某些元素的无序对集合 $E(G)$ 组成的二元组，记为 $G=(V(G), E(G))$ 。其中 $V(G)=\left\{v_{1}, v_{2}, \cdots, v_{n}\right\}$ 称为图 $G$ 的顶点集(vertex set)或节点集(node set)， $V(G)$ 中的每一个元素 $v(i)，(i=1,2,...n)$ 称为该图的一个顶点（vertex )或节点(node)； $E(G)=\left\{e_{1}, e_{2}, \cdots, e_{m}\right\}$ 称为图 $G$ 的边集(edge set)， $E(G)$ 中的每一个元素 $e_{k}$ （即 $V(G)$ 中1某两个元素 $v_{i}, v_{j}$ 的无序对）记为 $e_{k}=\left(v_{i}, v_{j}\right)$ 或 $e_{k}=v_{i} v_{j}=v_{j} v_{i}$ ， $(k=1,2, \cdots, m)$ ，被称为该图的一条从 $v_{i}$ 到 $v_{j}$ 的边(edge)。

当边 $e_{k}=v_{i} v_{j}$ 时，称 $v_{i}, v_{j}$ 是边 $e_{k}$ 的端点，并称 $v_{i}$ 与 $v_{j}$ 相邻；边 $e_{k}$ 称为与顶点 $v_{i}, v_{j}$ 关联，如果某两条边至少有一个公共端点，则这两条边在图 $G$ 中相邻。

边上赋权的无向图称为赋权无向图或无向网络，在这里对图和网络不做区分，因为任何图是可以赋权的。

如果一个图，它的顶点集和边集都有限，那么它被称为有限图。图 $G$ 的顶点数用符号 $|V|$ 或 $\nu(G)$ 表示，边数用 $|E|$ 或 $\varepsilon(G)$ 表示。
当讨论的图只有一个时，总是用G来表示这个图。从而在图论符号中我们常略去字母 $G$ ，例如，分别用 $V,E,v和\varepsilon$ 来代替 $V(G), E(G), v(G)和\varepsilon(G)$ 。
端点重合为一点的边称为环。
如果一个图既没有环也没有两条边连接同一对顶点，那么这个图称为简单图。

2.2.有向图

定义：一个有向图G是由一个非空有限集合 $V$ 和 $V$ 中某些元素的有序对集合 $A$ 组成的二元组，即为 $G=(V, A)$ 。其中
$V=\left\{v_{1}, v_{2}, \cdots, v_{n}\right\}$ 称为图 $G$ 的顶点集和节点集， $V$ 中的每一个元素 $v_{i}(i=1,2, \cdots, n)$ 称为该图的一个顶点或节点； $A=\left\{a_{1}, a_{2}, \cdots, a_{m}\right\}$ 称为图 $G$ 的弧集， $A$ 中的每一个元素 $a_{k}$ （即 $V$ 中某两个元素 $v_{i}, v_{j}$ 的有序对）记为 $a_{k}=\left(v_{i}, v_{j}\right)$ 或 $a_{k}=v_{i} v_{j}(k=1,2, \cdots, n)$ ，或被称为该图的一条从 $v_{i}$ 到 $v_{j}$ 的弧。

当弧 $a_{k}=v_{i} v_{j}$ 时，称 $v_{i}$ 为 $a_{k}$ 的尾， $v_{j}$ 称为 $a_{k}$ 的头，并称 $a_{k}$ 为 $v_{i}$ 的出弧，为 $v_{j}$ 的入弧。

对应于每个有向图 D ，可以在相同顶点集上作一个图 G ，使得对于 D 的每条弧，G 有一条有相同端点的边与之相对应。这个图称为 D 的基础图。反之，给定任意图 G ，对于它的每个边，给其端点指定一个顺序，从而确定一条弧，由此得到一个有向图，这样的有向图称为 G 的一个定向图。

以下若未指明“有向图”三字，“图”均视为无向图。

2.3 完全图，二分图

对于每一对不同的顶点都有一条边相连的简单图称为完全图。 $n$ 个顶点的完全图记为 $K_{n}$ 。

若 $V(G)=X \cup Y$ ， $X \cap Y=\Phi,|X \| Y| \neq 0$ ，（这里 $|X |$ 表示集合 $X$ 中的元素个数）,若此时 $X$ 中无相邻顶点对， $Y$ 中亦然，则称 $G$ 为二分图；特别地，若 $\forall x \in X, \forall y \in Y$ ，则 $x y \in E(G)$ ，则称 $G$ 为完全二分图，记为 $K_{|X|,|Y|}$ 。

二分图与完全二分图的解释

2.4 子图

如果 $V(H) \subset V(G)$ ， $E(H) \subset E(G)$ ，则称图 $H$ 叫做图 $G$ 的子图，记做 $H \subset G$ 。若 $H$ 是 $G$ 的子图，则 $G$ 称为 $H$ 的母图。

特殊地，当 $V(H)=V(G)$ 时，图 $H$ 称为图 $G$ 的支撑子图。

2.5 顶点的度

设 $v \in V(G)$ ， $G$ 中与 $v$ 关联的边数（每个环算作两条边）称为 $v$ 的度，记做 $d(v)$ 。若 $d(v)$ 是奇数，称 $v$ 是奇顶点： $d(v)$ 是偶数，称 $v$ 是偶顶点。关于顶点的度，我们有如下结论：

1. $\sum_{v \in V} d(v)=2 \varepsilon$
2.任意一个图的奇顶点的个数是偶数。

2.6 图和网络的数据结构

网络优化研究的是网络上的各种优化模型与算法。为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。一般来说，算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的 5 种常用表示方法：邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法。在下面数据结构的讨论中，我们首先假设 $G=(V, A)$ 是一个简单有向图， $|V|=n,|A|=m$ ，并假设 $V$ 中的顶点用自然数 $1,2, \cdots, n$ 表示或编号， $A$ 中的弧用自然数 $1,2, \cdots, m$ 表示用编号。对于有多重边或无向网络的情况，将会在讨论完简单有向图的表示方法之后，给出说明。

2.6.1 邻接矩阵表示法

邻接矩阵表示法是讲图以邻接矩阵的形式存储在计算机中。图 $G$ 的邻接矩阵是如下定义的：
$C$ 是一个 $n \times n$ 的0-1矩阵，即：

$C=\left(c_{i j}\right)_{n \times n} \in\{0,1\}^{n \times n}$
$c_{i j}=\left\{\begin{array}{ll}{1,} & {(i, j) \in A} \\ {0,} & {(i, j) \notin A}\end{array}\right.$

例1 对于下面的有向图，用邻接矩阵表示法表示

例1图

直接写出邻接矩阵
$\left[\begin{array}{lllll}{0} & {1} & {1} & {0} & {0} \\ {0} & {0} & {0} & {1} & {0} \\ {0} & {1} & {0} & {0} & {0} \\ {0} & {0} & {1} & {0} & {1} \\ {0} & {0} & {1} & {1} & {0}\end{array}\right]$

2.6.2 关联矩阵表示法

关联矩阵表示法是将图以关联矩阵的形式存储在计算机中。图 $G=(V, A)$ 的关联矩阵 $B$ 是如下定义的： $B$ 是一个 $n \times m$ 的矩阵，即：
$B=\left(b_{i k}\right)_{n \times m} \in\{-1,0,1\}^{n \times m}$
$b_{i k}=\left\{\begin{array}{ll}{1,} & {\exists j \in V, k=(i, j) \in A} \\ {-1,} & {\exists j \in V, k=(j, i) \in A} \\ {0,} & {其他}\end{array}\right.$

例2 对于例1的每条弧编号，从1到8分别是(1,2),(1,3),(2,4),(3,2),(4,3),(4,5),(5,3)和(5,4)，则关联矩阵表示为：
$\left[\begin{array}{llll}{1} & {1} & {0} & {0} & {0} & {0} & {0} & {0} \\ {-1} & {0} & {1} & {-1} & {0} & {0} & {0} & {0} \\ {0} & {-1} & {0} & {1} & {-1} & {0} & {-1} & {0} \\ {0} & {0} & {-1} & {0} & {1} & {1} & {0} & {-1} \\ {0} & {0} & {0} & {0} & {0} & {-1} & {1} & {1}\end{array}\right]$

2.6.3 弧表表示法

弧表表示法将图以弧表的形式存储在计算机中。所谓图的弧表，也就是图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点，共需 $2m$ 个存储单元，因此当网络比较稀疏时比较方便。此外，对于网络图中每条弧上的权，也要对应地用额外的存储单元表示。

例3 还是对于例1，用弧表表示法表示

弧编号	1	2	3	4	5	6	7	8
起点	1	1	2	3	4	4	5	5
终点	2	3	4	2	3	5	3	4
权	1	1	1	1	1	1	1	1

2.6.4 邻接表表示法

邻接表表示法将图以邻接表（adjacency lists）的形式存储在计算机中。所谓图的邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有弧，链表中每个单元对应于一条出弧。为了记录弧上的权，链表中每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数组表示。

链表举例

2.7 轨与联通

$W=v_{0} e_{1} v_{1} e_{2} \cdots e_{k} v_{k}$ ，其中 $e_{i} \in E(G), \quad 1 \leq i \leq k, \quad v_{j} \in V(G), \quad 0 \leq j \leq k, \quad e_{i}$ 与 $v_{i-1}, v_{i}$ 关联，称 $W$ 是图 $G$ 的一条道路， $k$ 为路长，顶点 $v_{0}$ 和 $v_{k}$ 分别称为 $W$ 的起点和终点，而 $v_{1}, v_{2}, \cdots, v_{k-1}$ 称为它的内部顶点。