---

引言

按照正常进度应该学习动态规划了，但我想换换口味，而且动态规划听说也有一定难度，还不一定会考。

先说说图论的一些背景知识和发展情况吧。

图论是几十年来发展迅速、应用广泛的一个新的数学分支。它与数学的其他分支如矩阵论、概率论、数值分析等都有着密切地联系。事实上，图论为任何一个包含了一种二元关系的系统提供了一个数学模型；也因为它使用了图解式的表示法，图就具有了一种直观的和符合美学的外形。

图论的发展大致分为 3 个阶段。

第一阶段是从 18 世纪中叶到 19 世纪中叶，称为萌芽期。起源是“七桥游戏”问题，如下图所示。

问题是：能否从这四块陆地中的任何一块开始，通过每一座桥一次，并且仅一次，再次回到起点。

瑞士数学家欧拉（Euler）就这一问题发表了图论的第一篇论文，证明了不存在七桥游戏问题的解，并且把这个问题（边一笔画问题）深入一步地一般化了，给出了一个图存在欧拉圈的判定法则。

自从中国邮递员问题（Chinese Postman Problem）提出来以后，欧拉问题才具有了强烈的实用价值。

中国邮递员问题是这样的：邮递员在沿着邮路出发前，必须先从邮局取走他所应分发的邮件。为了节约时间，每一位邮递员都愿意以尽可能少的行程走完他所必须走的所有路线。用图论的话来说，是指如何以尽可能少的行程遍历邮路上所有各条街道后又回到他的出发点。

这类问题的第一篇论文是由中国数学家、山东师范大学的管梅谷教授在 1962 年提出的，因而得名“中国邮递员问题”。

19 世纪中叶到 20 世纪中叶是图论发展的第二阶段，这一时期图论大量问题涌现，其中以 Hamilton 问题和四色猜想最为著名。

1856 年英国数学家 William Hamilton 爵士发明了“绕行世界”的游戏。这个游戏用一个规则十二面体，它的 20 个顶点标以 20 个城市的名字，要求游戏者找一条从某一城市出发的路线，它经过每个城市恰好一次，并且最终回到出发点。

将正十二面体投影到平面上，就得到了下图。

实际上 Hamilton 周游世界问题，是图论中的点一笔画问题，是要在上图中找具有以下两个特点的一个圈 $H$ ：1.图中的每一个顶点都在圈 $H$ 中出现；2.在 $H$ 中顶点不重复出现（起终点不算重复）。这个圈称为 Hamilton 圈。

四色猜想问题，即能否仅用 4 种颜色给地图染色，使得相邻国家有不同的颜色。用图来描述就是：用点来表示国家，两个国家若有公共边界，就用一条边将这两点连接起来，于是，四色猜想问题就转化为能否用四种颜色给平面的点染色，使得相邻的点有不同颜色。

20 世纪中叶以后，是图论发展的第三个阶段，这一时期图论经过爆炸性的发展，成长为一门独立学科。其中最重要的是：出现了研究问题和解决问题的强有力工具：计算机。

---

一、图与网络的基本知识

1.1 图与网络的基本概念

1.1.1 图的定义

自然界和人类社会中，大量的事物及事物之间的关系，常可以用图形来描述。常将所研究对象看成一个点，用连线（带箭头或者不带箭头）表示对象之间的某种特定关系。为了区别起见，我们称不带箭头连线称为边，带箭头的连线称为弧。

定义 1.1 —— 一个图是由一个非空集合 $V$ ，以及 $V$ 中元素的无序（或有序）点对组成的集合 $E$ （或 $A$）所组成。$V$ 中元素的无序点对所构成的集合称为边集合 $E$ ，由点集合 $V$ 和边集合 $E$ 构成的图称为无向图（简称图），记作 $G=(V,E)$ 。一条连接点 $v_i,v_j$ 的边 $e_{ij}$ ，记为 $e_{ij}=[v_i,v_j]$ 或 $e_{ij}=[v_j,v_i]$ 。$V$ 中元素的有序点对构成的集合称为弧集合 $A$ ，由点集合 $V$ 和弧集合 $A$ 构成的图为有向图，记为 $D=(V,A)$ 。一条方向是从 $v_i$ 指向 $v_j$ 的弧记为 $a_{ij}=(v_i,v_j)$ 。

若图 $G$ 中，某个边的两个端点相同，称该边为环，若两个点之间有多于一条的边，称为多重边。一个无环、无多重边的图称为简单图，无环但允许有多重边的图称为多重图。

图 $G$ 或 $D$ 中的点数记为 $n=|V|$ ，边（弧）数记为 $m=|E|(m=|A|)$ ，在不引起混乱的情况下，分别简记为 $n,m$ ，其中 $n$ 为图的阶，若 $n$ 为有限的，称为有限阶。

1.1.2 图中相关术语

1. 端点。当 $e_{ij}=[v_i,v_j]$ 时，与边 $e_{ij}$ 相连的顶点称为边 $e_{ij}$ 的端点。
2. 边与点相关联。当 $e_{ij}=[v_i,v_j]$ 时，$e_{ij}$ 与 $v_i,v_j$ 称为边顶相关联。
3. 邻点。
4. 邻边。
5. 环。只与一个顶点相关联的边称为环。
6. 平行边。具有相同的两个端点的边称为平行边。
7. 邻域。与某点相邻接的点的集合。
8. 次。以点 $v_i$ 为端点的边的数目称为点 $v_i$ 在 $G$ 中的次，记为：$d(v_i)$ 。
   如果有环，则按两条边记，即 $$d(v_i)=d_l(v_i)+2l(v_i)$$ 其中：$d_l(v_i)$ 是与 $v_i$ 相关联的非环边数，$l(v_i)$ 是与 $v_i$ 相关联的环数。
9. 次序列。若 V = { v 1 , v 2 , … , v p } V=\{v_1,v_2,\dots,v_p\} V={v1​,v2​,…,vp​} ，则相对于每个点都有一个次，则可以得到一个次序列 $(d(v_1),d(v_2),\dots )$ 。

定理 1.1 —— 对于图 $G=(V,E)$ ，其中 $|V|=n,|E|=m$ ，则有：$$\sum _{v\in V}d(v)=2m$$ 定理 1.2 —— 奇数次顶点的总数是偶数。

10. 悬点。次为 1 的点。
11. 悬边。悬点关联的边。
12. 孤立点。次为 0 的点。
13. 链。
14. 初等链。链 $Q$ 中的顶点均不相同。
15. 简单链。链中边都不相同。
16. 链的长度。为所包含的边数。
17. 圈。
18. 路。
19. 路径。有向图中路每个顶点均不相同称为路径。
20. 回路。路的第一个点和最后一个点相同。

1.1.3 一些特殊图类

1. 平凡图。节点数 $n=1$ ，边数 $m=0$ 的图。
2. 零图。边数 $m=0$ 。
3. 连通图。图中每对节点都有一条链（路）连接，称这个图是连通的。
4. 树。无圈的连通图。
5. 完备图。任意两个顶点之间恰有一条边相关联。
6. 二分图。
7. 完全二分图。
8. 正则图。每个点的次数均相同。
9. 有向网络。加权的有向图。

1.1.4 图的运算

（1）子图和支撑
子图、支撑子图都是图 $G$ 的点或边作删除运算得到的。子图点和边都是原图的子集，支撑子图点和原图一样，边是原图子集。

（2）图的收缩运算

（3）割集
常记为 $\Phi (X)$ ，如下图中，若 X = { V 1 } X=\{V_1\} X={V1​} ，则割集为 $\Phi (X)=\{[v_1,v_2],[v_1,v_3],[v_1,v_4\}$ 。即用一条线去割，要求可以将 $X$ 完整割出来，这条线碰着的边记为割集。

（4）图的同构
设 $G_1,G_2$ 为两个同阶图，若顶点集合 $V_1,V_2$ 以及边集合 $E_1,E_2$ 之间在保持关联性质条件下一一对应，则称图 $G_1,G_2$ 同构。如下图所示。

1.2 图的矩阵表示

为了方便利用计算机识别图的相关信息，我们通过矩阵表示法来表示一个图，主要有邻接矩阵、关联矩阵、可达矩阵、权矩阵等。

1.2.1 邻接矩阵

邻接矩阵用于描述两个顶点之间是否有边（弧）相连。若两点之间有边（弧）相连，对应矩阵元素为 1 ，否则对应矩阵元素为 0 。

显然，无向图的邻接矩阵是一个关于对角线对称的矩阵。

1.2.2 可达矩阵

在有向图中可达矩阵用于描述两点之间是否有路相连，若有路相连，对应矩阵元素为 1 ，否则为 0 。

1.2.3 关联矩阵

有向图的关联矩阵也称为顶点—边关联矩阵。其每一行表示一个点 $v_i$ ，每一列表示一条弧 $a_j$ ，若 $v_i$ 是弧 $a_j$ 的起点，则对应矩阵元素 $m_{ij}=1$ ；若为弧的终点，记为 -1 ，无关则记为 0 。

1.2.4 权矩阵

可以理解为邻接矩阵的延伸，当两点之间存在边或弧时，对应矩阵元素为该边或弧的权重；当两点之间无边时，对应元素为 $\infty$ ；权矩阵对角元素全为 0 。

---

写在最后

这概念可是真的多，不过结合图来理解就还好，后面我们就来说说图论中的一些经典问题。