其实离散数学的时候讲过，数据结构又讲过，数模再讲一遍。

什么问题能抽象为图论

举了一堆例子，然后得出结论：

能够把问题抽象为两种：元素，以及元素之间的关系

上面的这种问题就可以抽象为图论

基本概念

图的元素

  • $G=(V, E)$ $Vertex$ 为顶点，$Edge$ 为边
  • $V={v_1, v_2, v_3, v_4}, E={e_1, e_2, e_3, e_4}$
  • $e=(u, v)$ 无向边
  • $e=<u, v>$ 有向边（弧），$u$ 为始点（弧尾），$v$ 为终点（弧头），统称端点
  • 边与点：相关联
  • 点与点：邻接点/不邻接的
  • 边与边：邻接边
  • 自回路（环） 计算机科学叫自环

图的分类

孤立结点 零图（只有孤立节点） 平凡图（只有一个结点） $(n, m)$ 图（$n$ 点 $m$ 边）
无向图 有向图 混合图
平行边 重数 多重图 线图（非多重图）
简单图（无环的线图） 阶（顶点的个数）
完全图
同构图

图的记法

关联矩阵（$n*m$ 矩阵，存储边和点关联的次数） 邻接矩阵 邻接表（略）

度

度、入度、出度

握手定理（欧拉定理）：无向图中，所有结点的度数的总和等于边数的两倍
推论：度数为奇数的结点数为偶数

路

路 边不重复 点不重复
通路 简单通路（边不重复） 基本通路（除端点外任意两点都不同）
回路（起点和终点相同） 简单回路（边不重复的回路） 基本回路/圈（起点和终点相同的长为正的基本通路）

约定：凡指基本通路或路均认为此路不是圈。

易知，图中若点 u 与 v 间存在通路，则 u 与 v 间必存在基本通路；若过点 u 存在简单回路，则过点 u 必存在基本回路。

最短路问题

这里最短路指的是单源最短路。

这里放一个 Dijsktra 算法的描述。虽然数据结构和离散都讲过，还有代码，但是数模的描述还是稍微有一点不同的。

Dijkstra 算法
Dijkstra 算法

另外也可以用线性规划求解：

$$
\min \sum_{(i,j) \in E} w_{ij}x_{ij} \\
\text{such that}
\sum_{j=1, (i,j)\in E}^n x_{ij} - \sum_{j=1, (i,j)\in E}^n x_{ji} =
\begin{cases}
1 & i = 1 \\
-1 & i = n \\
0 & i \neq 1, n
\end{cases} \\
~\\
x_{ij} \geq 0, (i, j) \in E
$$

例题不少，可以看看 PPT。

子图

上面的概念是针对任何图，下面我们针对

这部分概念只是介绍一下，具体什么的定义还是去看 PPT 吧。

  • 子图：所有的顶点和边都属于图 G 的图称为 G 的子图。
  • 真子图：若这个节点子集或边子集是真子集，则称这个子图为真子图
  • 生成子图：含有 G 的所有顶点的子图称为 G 的生成子图。
  • （点）导出子图：由该图顶点的一个子集和该图中两端均在该子集的所有边的集合组成的图
  • （边）导出子图：由该图边的一个子集和以该子集中的边相关联的点组成的图
  • G 的补图：从完全图删除 G 的所有边得到的图
  • G1 在 G 的补图：从 G 中删除 G1 的所有边得到的图

树

无圈的连通图称为树。树中度为 1 的点称为树叶，其余点称为分枝点。

定理：设 $G$ 是具有 $n$ 个点 $m$ 条边的图，则以下关于树的命题等价。

  1. $G$ 是树。
  2. $G$ 中任意两个不同点之间存在唯一的路。
  3. $G$ 连通，删去任一边便不连通。
  4. $G$ 连通，且 $n=m+1$。
  5. $G$ 无圈，且 $n=m+1$。
  6. $G$ 无圈，添加任一条边可得唯一的圈。

居然是一条一条可以证明的，而且是从定义的仅仅 9 个字出发的。精妙精妙。证明略。读者可以自己思考。

一波定义：

有向树：去掉边方向后是一棵树的有向图
根树：恰有一个顶点的入度为 0，其余顶点的入度均为 1 的有向树

  • 根：入度为 0 的顶点
  • 叶：出度为 0 的顶点
  • 分支：出度不为 0 的顶点
    $m$ 叉树：所有顶点出度不大于 $m$ 的根树
    完全 $m$ 叉树：各顶点出度要么为 0，要么为 $m$ 的 $m$ 叉树

定理：

设完全 $m$ 叉树的叶子树为 $t$，分支树为 $i$，则有：
$$(m-1)i=t-1$$

证明从 各顶点出度之和=弧数 出发。

生成树

关于连通图：

边连通度：删掉任意 $k$ 边，图都连通（但不对 $k+1$ 成立），则该图的边连通度为 $k$
点连通度：删掉任意 $k$ 点，图都连通（但不对 $k+1$ 成立），则该图的点连通度为 $k$

树的边连通度、点连通度都是 1。

生成树定义：

若图 G 的生成子图T是树，则称T为G的生成树。

定理：连通图的生成树必存在。

证明：给定连通图 G，若 G 无圈，则 G 就是自己的生成树。若 G 有圈，则任取 G 中一个圈 C，记删去 C 中一条边后所得之图为 H1。显然在 H1 中，圈 C 已不存在，但仍连通。若 H1 中还有圈，重复以上过程，直至得到一个无圈的连通图 H。H 便是 G 的生成树。

没错，这就是“破圈法”——求生成树的一个算法。

最小生成树定义：

在权图 G 中，边权之和最小的生成树称为G的最优树。

Krusual 算法好评：

Kruskal 算法
Kruskal 算法