图优化算法

图表示

---

关联矩阵

---

• 有向图

$$m_{ij}=\begin{cases} 1, v_i与e_j相关联,v_i是e_j的起点 \\ -1, v_i与e_j相关联,v_i是e_j的终点 0, v_i与e_j不关联 \end{cases}$$

• 无向图

$$m_{ij}=\begin{cases} 1, v_i与e_j相关联 \\ 0, v_i与e_j不关联 \end{cases}$$

邻接矩阵

---

• 有向图

$$a_{ij}=\begin{cases} 1, (v_i, v_j)\in E \\ 0, (v_i, v_j)\notin E \end{cases}$$

• 无向图

$$a_{ij}=\begin{cases} 1, v_i与e_j相邻 \\ 0, v_i与e_j不相邻 \end{cases}$$

图算法

---

最短路径算法

---

Dijkstra算法

问题：求解$u_0$到其余各点的最短路径

初始化：S为标号的顶点集为$\empty$， Step为0

1. 将$u_0$添加到$S$集合中，找$u_0$到邻接的各点的距离，记录到表格；并把距离最短的顶点$u_i$加入到$S$
2. 从新的$S$集合找到各点的距离，若上一步结束后当前集合为$S=\{u_0, u_i\}$,那就要找$u_0,u_i$到其他各点之间的距离，并取到其最短距离的顶点加入到$S$，不断重复。
3. 计算完毕后按列看找到每一列，每一列数值最小的那个数就是起点到这个点的最短距离。

匹配与覆盖

---

图匹配

• 定义：设有图$G=(V,E)$，$M\subseteq E$，若 $M$ 的边互不相邻，则称 $M$ 是 $G$ 的一个匹配，$M$ 为匹配边.(M是边集)
• 若顶点$v$相关联的是其中一条匹配边,也就是$(v,x)\in M$,则顶点$v$是饱和点，否则就是非饱和点.
• 完美匹配：$M$是$G$的匹配，若每个顶点都是饱和点，则为完美匹配
• 最大匹配：$M$是$G$的匹配，若能找到一个顶点数最多的匹配，则这个就是最大匹配
• 交错路：$M$是$G$的匹配，若一条路中匹配边和非匹配边相互交错(匹配边--非匹配边--...--匹配边)
• 增广路：起点和终点都是非饱和点的交错路叫增广路(可以理解为通过交错路找到其中一个非饱和点，随着交错路的越来越长，路就越来越长，就慢慢变长了，路就长了)'
• 理解：其实就是两条互不相连的边，没有公共的顶点，为什么叫匹配呢？因为两条边如果都没有共同的顶点，说明这两边都是配对的，可以理解为性质相同的两条边，相互配对了。

图覆盖

• 定义：设有图$G=(V,E)$,$K\subseteq V$,若G的每条边都与K的一个顶点关联，则称K是G的覆盖。(K是顶点集)
• 最小覆盖：若能找到一个顶点数最少的覆盖，则为最小覆盖。
• 理解：就是一个点能覆盖一个图里面多少个点，如果一个点能覆盖其他几个点，说就能覆盖完全了，有点像从天上落下到某个点，从这个点延展开能连接到所有的点，就是覆盖。

割边

删除一条边导致图不连通，该边为割边 判断：$G$的边$e$是割边的充要条件$e$不在$G$中的回路（圈）中

Summary

点覆盖边，边匹配点

• M是最大匹配的充要条件是$G$没有增广路，只要不存在增广路了就是最大的匹配了。
• 若$|M|=|K|$，则$M$为最大匹配，$K$为最小覆盖

匈牙利算法——求解最大匹配

1. 先只看一边，然后从第一个点$x_1$开始，若$x_1$点与其他相连的点($y_i$)相连接，则随便选择一条
2. 看到第二个点$x_2$时，若该点与上一步的$y_i$有连接且没有其他连接，则把上一步的连接取代，该点x2与$y_i$连接，则刚才的x1与其他相连的点$y_j$连接。若有其他连接则选择其他相连的点。
3. 有权值就按照权值来

求解最小覆盖

直接找一个点能够连接到所有点的点

最小生成树

---

• Kruskal算法

  1. 先对图的边按权重从小到大排序
  2. 按照边从小到大对应连接各顶点

• Prim算法

  1. 从一个起点开始找相关联权值最小的边，将该边的顶点加入点集
  2. 继续找该边集到其他各相邻点权值最小的边，将该边的顶点加入点集
  3. 重复直到有$n-1$条边
  • 注意不能形成回圈

邮递员问题——巡回问题

• 若是欧拉图，直接使用Fluery算法(弗勒里)

• 若不是欧拉图

  • 若正好有两个奇数度的顶点
    1. 先求出奇数度顶点$u$和$v4之间的最短路
    2. 将该最短路加入到$G$中
    3. 使用Fluery算法
  • 若有$2n$个奇数度的顶点$(n>2)$
    1. 先求出所有奇数度顶点之间的最短路和距离
    2. 用所有奇数度顶点导出一个子图(包含原来的边)
    3. 在该子图中求解最小权值完美匹配
    4. 在完美匹配的边的两顶点之间的最短路添加重复边
    5. 使用Fluery算法

• Fluery算法(求解欧拉通路)

  1. 任选一个顶点$v_0$,道路$w_0=v_0$;
  2. 选定任意一条道路，从$E-{e_1,e_2,...,e_i}$剩下的边中选出一条边$e_{i+1}$，使得$e_{i+1}$与$v_i$关联且$e_{i+1}$不是割边.

图优化问题求解方法

1. 从问题中找出能够作为节点的参数(量)。
2. 根据题目要求用节点构建图模型。
3. 3.然后确定好每个节点代表什么意思。
4. 再根据最后所求问题使用对应方法求解。