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

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

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}$ 称为它的内部顶点。

若道路 $W$ 的边互不相同，则 $W$ 称为迹。若道路 $W$ 的顶点互不相同，则 $W$ 称为轨。
如果一个长度非0，起点和终点相同的道路，则称为闭合道路。起点和终点重合的轨称作圈。

若图 $G$ 的两个顶点 $u,v$ 间存在道路，则称 $u和v$ 联通。 $u,v$ 间的最短轨道长叫做 $u,v$ 间的距离。记做 $d(u, v)$ 。若图 $G$ 的任二顶点均联通，则称 $G$ 是连通图。

显然有：

1.图 $P$ 是一条轨的充要条件是 $P$ 是联通的，且有两个一度的顶点，其余顶点的度是两度。
2.图 $C$ 是一个圈的充要条件是 $C$ 是各顶点的度均为2的联通图。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 219,928评论 6赞 509
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,748评论 3赞 396
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 166,282评论 0赞 357
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 59,065评论 1赞 295
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 68,101评论 6赞 395
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,855评论 1赞 308
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,521评论 3赞 420
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,414评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,931评论 1赞 319
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 38,053评论 3赞 340
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,191评论 1赞 352
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,873评论 5赞 347
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,529评论 3赞 331
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,074评论 0赞 23
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,188评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,491评论 3赞 375
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,173评论 2赞 357