小猫咪吃python

# 欧拉路径和欧拉回路 哥尼斯堡七桥问题：18 世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来（如概述图）。有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。后来大数学家欧拉把它转化成一个几何问题 —— 一笔画问题。 在图论的概念里，我们把这个一笔画问题称为欧拉路径问题。 欧拉路径问题：是否存在一个路劲，使得每条边 恰好 走一次。 欧拉回路问题：是否存在一个环路，使得每条边 恰好 走一次。 # 欧拉路径和欧拉回路的成立条件 我们先把七桥问题转换成图，于是可以得到如下图： 我们发现四个点的度分别是： 3、3、5、3...

# 前置知识 图论基础之二分图中最小覆盖问题的求解思路 # 最小路径点覆盖 在一个有向无环图中，用最少的互不相交的路径将所有点覆盖，我们叫做最小路径点覆盖，又称为最小路径覆盖。 拆点：把一个点拆分成两个点 1 ，左边作为 出点1 ，右边作为 入点 1′1^\prime1′。 经过如上拆点的过程之后，我们发现一条边 i->j 可以拆分成一条由 i 指向 $j^\prime $...

# 前置知识 图论基础之二分图中最小覆盖问题的求解思路 # 最大独立集 图的最大独立集：从图中选出最多的点，使得选出的点中 任意两点之间没有边。 图的最大团：从图中选出最多的点，使得选出的 任意两点之间都有边。 根据定义，我们也能发现，这两个概念是互补的。 补图：就是把原图中所有边拆开，所有未连接的边连上。 那么，原图中的最大独立集就是补图中的最大团。 #...

# 前置知识 图论基础之匈牙利算法求二分图的最大匹配 # 最小点覆盖问题 最小点覆盖：给出一个图，从中选出最少的点，使得每一条边的两个点里面至少有一个点是被选出来的。 在二分图中，最小点覆盖有一个结论：最小点覆盖数量 == 最大匹配数量。 # 结论证明（可略过） 若想证明一个相等的结论，比如：A==B，我们可以先证明 A>=B，再证明 A<=B，这样就能推出来 A==B，然而如果我们想求出来 A 最小，那么其实只需要证明 A>=B 且 A==B，因为一定是取到等号的时候 A 才最小，所以我们就有本结论以下的证明方式： 最小点覆盖...

# 前置知识 本文第一部分（算法介绍部分）与这篇文章完全相同。但用作示例的题目不同，本文的题目更贴合实际应用，而这篇文章的题目更加的偏向模板，而且用 python 写的。 二分图的概念在图论基础之染色法判定二分图。本文主要讲述判定二分图的算法匈牙利算法。 二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。 二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。 # 匈牙利算法 # 抽象模型 该算法的主要作用就是求二分图的最大匹配的数量。 该算法可以用...

# 二分图问题 二分图：在一个图中，可以把所有的点划分到两个集合，满足所有的边都在两个集合之间连通，我们认为这个图是二分图。 如果点 a 与点 b 连通，a 属于集合 A，那么 b 就必须属于集合 B。如果 b 也属于集合 A，则 a 和 b 在集合 A 内部连通，就不是二分图。 示例中，绿色框所有的边都在两个集合之间连通，所以是二分图；而黄色框中点 f 和点 i 组成的边在集合 2 内部连通，因此黄框不是二分图。 #...

# 前置知识 有向图的强连通分量问题的思路与应用 无向图的双连通分量实在实在太太太太难难难难了，如果有什么地方不懂可以先看完正篇文章（其实是先看看题目，结合代码注释这种笨方法理解），如果还是不会实属正常，毕竟这三道题可能过了今天我就写不出来了。 # 无向图的双连通分量问题 对于一个无向图，它有两种双连通分量：边双连通分量（e-DCC）和点双连通分量（V-DCC）。 桥：如果在一个无向图内，删除一条边会使图变得不连通，则称这条边为 “桥”。（难道是象征着独木桥？） > 边的双联通分量：最大的，不含有桥的联通区域，称为...

# 有向图的强连通分量问题 对于一个有向图，它的连通分量：对于分量中 任意的两点 u 和 v，都能从 u 走到 v，并且可以从 v 走到 u。 强连通分量（SCC）：极大连通分量，对于分量外的任意一点，加入分量，都会导致 该连通分量不再满足定义。 强连通分量的作用是将 有向图 通过 缩点 转换为 有向无环图（拓扑图）。 缩点：将所有的连通分量缩为一个点。 在上图中，绿色部分就是强连通分量，所以我们可以把绿色部分缩点为一个点，同时其他四个单独的点，因为不和其他点相连，所以也符合强连通分量的定义，因此缩点后，整个图变成如下拓扑图的形式。 # Tarjan 算法求强连通分量 （ps:...

# 最近公共祖先问题 最近公共祖先，又叫 LCA 问题。在一个有根树当中，如果节点 z 既是 x 的祖先，又是节点 y 的祖先，那么就称 z 为 x 和 y 的公共祖先，而所有公共祖先中，深度最大的一个称为最近公共祖先，记为 LCA(x,y) 。 图中黄色圈为 x 和 y 的公共祖先，而深度最大的那个即为最近公共祖先。 特别要说明的，每个点自己也可能是自己的祖先，也就是说，假如 x 是 y 的祖先，那么就会有 LCA(x,y)=x 。 # 向上标记法 用向上标记法可以求解出两个点的最近公共祖先。我们从一个点 x 向上遍历所有点，把能到达的祖先节点都标记上，再从另一个点 y...

# 差分约束问题 差分约束是一种特殊的 N 元一次不等式组。包含 N 个变量X1∼XNX_1 \sim X_NX1​∼XN​，以及 M 个约束条件，其中每个约束条件有两个变量做差构成，形如：Xi−Xj<=CkX_i-X_j<=C_kXi​−Xj​<=Ck​，我们要做的就是求出一组X1∼XNX_1 \sim X_NX1​∼XN​ 的值，使得 M 个约束条件全部满足。 例如： {x1≤x2+1x2≤x3+3x3≤x1−2\left\{\begin{matrix} x_1 \le x_2+1 \\x_2 \le x_3+3 \\x_3 \le...