一、图的基本概念

部分概念请参阅我的另一篇博客：Graph Theory

1.6.2 关联矩阵

图 $G = (V, A)$ 的 关联矩阵(incidence matrix) $B$ 是如下定义的： \(\begin{aligned} B&=(b_{ij})_{n\times m}\in\{-1,0,1\}^{n\times m}\\ b_{ij}&=\begin{cases} 1,\;\;k=(i,j)\in A\\ -1,\;\;k=(j,i)\in A\\ 0,\;\;\text{其他} \end{cases} \end{aligned}\)

每行对应于图的一个节点，每列对应于图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素为 $1$；如过是终点则对应 $−1$；如果一个节点与一条弧不关联，则关联矩阵中 对应的元素为 $0$。

1.6.3 弧表

|||||||||| |—|—|—|—|—|—|—|—|—| |起点| 1| 1| 2| 3| 4| 4| 5| 5| |终点| 2| 3| 4| 2| 3| 5| 3| 4| |权 | 8| 9| 6| 4| 0| 3| 6| 7|

1.6.5 星形表示法

星形(star) 表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点，它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表示。也就是说，在该数组中首先存放从节点 $1$ 出发的所有弧，然后接着存放从节点 $2$ 出发的所有孤，依此类推，最后存放从节点 $n$ 出发的所有孤。

对每条弧，要依次存放其起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号，只是从同一节点出发的弧的顺序可以任意排列。此外，为了能够快速检索从每个节点出发的所有弧，我们一般还用一个数组记录每个节点出发的弧的起始地址(即弧的编号)。

Facts:
在数组 $point$ 中，

1. 其元素个数比图的节点数多 $1$ (即 $n +1$)，且一定有 $point(1) = 1, point(n+1) = m+1$。
2. 对于节点 $i$，其对应的出弧存放在弧信息数组的位置区间为 $[point(i), point(i +1) −1]$，
3. 如果 $point(i) = point(i+1)$，则节点 $i$ 没有出弧。

前向星形表示法有利于快速检索每个节点的所有出弧，但不能快速检索每个节点的所有入弧。为了能够快速检索每个节点的所有入孤，可以采用 反向星形(reverse star) 表示法：首先存放进入节点 $1$ 的所有孤，然后接着存放进入节点 $2$ 的所有弧，依此类推，最后存放进入节点 $n$ 的所有孤。其余同星形表示法

弧表略。由上表可知 $rpoint(1)=rpoint(1+1)\to$ 节点 $i$ 没有入弧

如果既希望快速检索每个节点的所有出弧，也希望快速检索每个节点的所有入弧，则可以综合采用前向和反向星形表示法。当然，将孤信息存放两次是没有必要的，可以只用一个数组(trace)记录一条弧在两种表示法中的对应关系即可

1.7 轨与连通

定义 $W$ 是图 $G$ 的一条道路(walk) \(W = v_0e_1v_1e_2...e_kv_k,\;\;e_i\in E(G), v_j\in V (G)\)

where,
$e_i$ 与 $v_{i−1},v_i$ 关联，$k$ 为路长，顶点 $v_0$ 和 $v_k$ 分别称为 $W$ 的起点和终点。

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

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

二、应用：最短路问题

指定顶点与其他顶点之间的最短路径

Def: Dijkstra 算法

一种贪心算法，通过依次遍历其他顶点，找到权重和最小的路径

这里仅给出一个无向图的 matlab 示例，如果对象是有向图，那么步骤将更为简单

图 2-1 加权无向图

C = [0, 7, 9, inf, inf, 14;
     7, 0, 10, 15, inf, inf;
     9, 10, 0, 11, inf, 2;
     inf, 15, 11, 0, 6, inf;
     inf, inf, inf, 6, 0, 9;
     14, inf, 2, inf, 9, 0];

costs = C(1, :);  % 距离
paths = ones(1, 6);  % 路径

for i = 2:6  % 遍历其他顶点
    for j = 1:6
        if C(i, j) ~= inf
            cost_temp = costs(1, i) + C(i, j);
            if cost_temp < costs(1, j)
                costs(1, j) = cost_temp;
                paths(1, j) = paths(1, i) * 10 + i;
            end
        end
    end
end

github 链接: graph_1_Dijkstra.md

三、树

3.1 基本概念

连通的无圈图叫做树，记之为 $T$。若图 $G$ 满足 $V(G) = V(T)$，$E(T)\subset E(G)$，则称 $T$ 是 $G$ 的生成树。

图 $G$ 连通的充要条件为 $G$ 有生成树。一个连通图的生成树的个数很多，用 $\tau(G)$ 表示生成树的个数，则有公式 \(\tag{1} (Caylay)\tau(K_n) = n^{n−2}\)

where, $G − e$ 表示从 $G$ 上删除边 $e$，$G\cdot e$ 表示把 $e$ 的长度收缩为零得到的图。

3.2 应用：连线问题

欲修筑连接 $n$ 个城市的铁路，已知 $i$ 城与 $j$ 城之间的铁路造价为$C_{ij}$，设计一个线路图，使总造价最低。

连线问题的数学模型是在连通赋权图上求权最小的生成树，即求最小生成树。有两种常用算法：

3.2.1 prim 算法

从所有 $p\in P, v\in V − P$ 的边中，选取具有最小权值的边 $pv$ ，将顶点 $v$ 加入集合 $P$ 中，将边 $pv$ 加入集合 $Q$ 中，如此不断重复，直到 $P=V$ 时，最小生成树构造完毕。 \(\begin{aligned} & \text{Set }P=\{v_1\}, Q=\{\} \\ & \text{while }\vert P\vert\neq\vert V\vert: \\ &\qquad\text{Find min edge }pv,\;\;p\in P, v\in V-P \\ &\qquad P=[P,v] \\ &\qquad Q=[Q,pv] \end{aligned}\)

图 3-1 加权无向图

a = zeros(7); 
a(1, 2) = 50; a(1, 3) = 60;
a(2, 4) = 65; a(2, 5) = 40;
a(3, 4) = 52; a(3, 7) = 45;
a(4, 5) = 50; a(4, 6) = 30; a(4, 7) = 42;
a(5, 6) = 70; 
a = a+a';  % 通过对称构造无向图
a(find(a == 0)) = inf;

result = [];
Ps = 1;  % 已访问的顶点
Vs = 2:length(a);  % 未访问的顶点

while length(Ps) ~= length(a)  % 全部顶点都被访问时, 结束循环
    % 找到距离最近的顶点
    temp = a(Ps, Vs); temp = temp(:);
    d = min(temp);
    [pb, vb] = find(a(Ps, Vs) == d);
    p = Ps(pb(1));
    v = Vs(vb(1));

    % 更新 result, Ps, Vs
    result = [result, [p; v; d]];
    Ps = [Ps, v];
    Vs(find(Vs == v)) = [];
end

github 链接: graph_2_prim.md

3.2.2 Kruskal 算法

四、匹配问题

4.1 基本概念

4.1.1 相配、许配

若 $M\subset E(G)$，$\forall e_i,e_j\in M$，$e_i$ 与 $e_j$ 无公共端点，则称 $M$ 为图 $G$ 中的一个对集；$M$ 中的一条边的两个端点叫做在对集 $M$ 中相配；$M$ 中的端点称为被 $M$ 许配。

4.1.2 完美对集、最大对集

$G$ 中每个顶点皆被 $M$ 许配时，$M$ 称为完美对集；$G$ 中已无使 $\vert M’\vert>\vert M\vert$ 的对集 $M’$，则 $M$ 称为最大对集。

4.1.3 交错轨、可增广轨

若 $G$ 中有一轨，其边交替地在对集 $M$ 内外出现，则称此轨为 $M$ 的交错轨，交错轨的起止顶点都未被许配时，此交错轨称为可增广轨。

图 4-1 最大对集、完美对集、交错轨与可增广轨

在图 4-1 中，$M = {e_{14}, e_{23}}$ 即两条红色的边，$G1,G2$ 则分别为包含蓝色、绿色区域所有顶点以及边的图，并满足 $G1\subset G2$。由图可得：

1. $M$ 为 $G1$ 的完美对集与最大对集
2. $G1$ 中的轨 $P_{1423}$ 为 $M$ 的交错轨
3. $G2$ 中的轨 $P_{5236}$ 为 $M$ 的可增广轨

4.2 定理与算法

4.2.1 定理 1

$M$ 是图 $G$ 中的最大对集当且仅当 $G$ 中无 $M$ 可增广轨。

4.2.2 定理 2

$G$ 为二分图，$X$ 与 $Y$ 是顶点集的划分，$G$ 中存在把 $X$ 中顶点皆许配的对集的充要条件是，$\forall S\subset X$，则 $\vert N(S)\vert\geq\vert S\vert$，其中 $N(S)$ 是 $S$ 中顶点的邻集。（简言之，可以理解为 $X$ 中任意 $n$ 个顶点都可以连接到 $\geq n$ 个 $Y$ 中的顶点）

推论 1
若 $G$ 是 $k$ 次（$k > 0$) 正则 $2$ 分图，则 $G$ 有完美对集（所谓 $k$ 次正则图，即每顶点皆 $k$ 度的图）。由此推论得出下面的婚配定理。

4.2.3 定理 3: 婚配定理

每个姑娘都结识 $k(k\geq1)$ 位小伙子，每个小伙子都结识 $k$ 位姑娘，则每位姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。