朱睿大牛：图论基础与网络流习题集锦

图论基础与网络流习题集锦 北京大学朱睿 大纲 图论部分 1 图论简介2 生成树与生成树计数3 欧拉回路与哈密顿回路4 割与流 匹配 网络流问题部分 1 习题2 习题3 更多的习题 图论简介 一个无向图G一般被抽象为一个二元组1 V是一个集合并被称为G的点集 2 E是V的无序积的多重子集 被称为G的边集 其元素被称为无向边 一个有向图D一般被抽象为一个二元组1 V是一个集合并被称为D的点集 2 E是V的卡氏积的多重子集 被称为D的边集 其元素被称为有向边 图的阶 即 V 零图 E 0 基图 将D的有向边改为无向边 成为一个无向图 无向完全图 简单无向图中每个点都与其他点相邻 有向完全图 简单有向图中对于任意vi vj V都有 E且 E 图论简介 平行边 即重边 环 即自环 简单图 不含平行边且不含环的图 度 无向图中 与某点关联的边的数量 入度 出度 有向图中 与某点关联的入边和出边的数量 K 正则图 无向简单图中所有点的度数都为K 握手定理 所有点度数之和等于2 E 同构 两个无向图与 若存在双射函数f V1 V2 使得对于任意vi vj V1 f vi f vj V2时 E1当且仅当 E2 则称这两个无向图同构 生成树与生成树计数 生成树 一个连通无向图的极小连通子图 被称为这个图的生成树最小生成树 一个边带权的连通无向图的极小连通子图 同时包含最小的边权 Prim算法 Kruskal算法生成树计数问题 如何求出一个连通无向简单图的不重复生成树个数 生成树与生成树计数 Matrix Tree 矩阵树 定理 假设图G是一个包含n个点无向图 定义G的度数矩阵D G 为一个n n的矩阵 并且对于任意i j 有Dij 0 当i j时 Dij为节点i的度数 定义G的邻接矩阵A G 为一个n n的矩阵 并且对于任意属于G的边集时 Aij为1 否则为0 定义G的Laplace算子 Kirchhoff矩阵 为C G D G A G 那么图G的生成树个数为C G 的任意一个n 1阶主子式 即去掉第r行第r列 r任意 的行列式之绝对值 欧拉回路与哈密顿回路 欧拉回路 对于一个连通图 遍历所有边并回到起点的路径被称为是一条欧拉回路 无向图欧拉回路的充要条件 连通并且每个点的度数都为偶数 有向图欧拉回路的充要条件 强连通并且每个点的入度和等于出度和 欧拉回路与哈密顿回路 哈密顿回路 遍历图中所有点一次且仅一次并最终回到起点的路径被称为哈密顿回路 哈密顿通路 遍历图中所有点一次且仅一次的路径被称为哈密顿通路 到目前为止 还没有一个简明的条件能作为判断一个图是否存在哈密顿回路的充要条件TT这里给出一个充分条件 若对于无向简单图G 任意两个不相邻点的度数之和大于或等于n 1 则该图存在哈密顿通路 若对于无向简单图G 任意两个不相邻点的度数之和大于或等于n 则该图存在哈密顿回路 割与流 匹配 流 假设G V E 是一个有限的有向图 它的每条边 u v E都有一个非负值实数的容量c u v 如果 u v 不属于E 我们假设c u v 0 我们区别两个顶点 一个源s和一个汇t 一个网络流是一个对于所有结点u和v都有以下特性的实函数f V V R其满足以下三个要求 1 容量限制 f u v c u v 2 斜对称 f u v f v u 3 流守恒 除非u s或u t 否则 w V f u w 0则该网络流的流量为s的总输出 或t的总输入 割 设Ci为网络N中一些弧的集合 若从N中删去Ci中的所有弧 即 使得从顶点Vs到顶点Vt的路集为空集时 称Ci为Vs和Vt间的一个割 割与流 匹配 最大流 从s到t的所有可行的网络流中 流量最大的网络流 最小割 从s到t的割中 删除边权和最小的割 对于一个给定的s和t 最大流 最小割 割与流 匹配 对于一个无向图G 点独立集 V的一个子集使得该集合中任意两点之间没有边 点支配集 V的一个子集使得任意V中元素要么属于该集合 要么与该集合中点有边相连 点覆盖集 V的一个子集使得任意E中元素都与该集合中某个或某两个元素相关联 极大 最大点独立集 极小 最小点支配集 极小 最小点覆盖集 同样的 我们可以定义边覆盖集 即用边覆盖所有点 与边独立集 即任意两条边之间没有共同点 割与流 匹配 匹配 G的一个边独立集 又被称为G的一个匹配 极大匹配与最大匹配 二部图 二分图 若无向图G的点集V可以分割成两个互不相交的子集 并且对于边集E中的所有边 vi vj 所关联的两个顶点vi和vj都分属这两个子集 那么图G就被称为一个二部图 二部图匹配的霍尔定理 婚姻定理 设有二部图G 且 V1 V2 则该图有完美匹配的充要条件是 对于任意V1的子集S 设 S k 则与S相连的点集大小不小于k 推论 若G为k 正则二部图 那么G中存在k个边不同的完美匹配 网络流习题集锦 欧拉回路 给定一张包含N个点M条边的图 其中有些边是单向边有些边是双向边 问是否存在欧拉回路 N和M范围不限定 试给出尽量优秀的算法 网络流习题集锦 欧拉回路 解答 首先我们知道 若该混合图有欧拉回路 一定有一种方法使得给该图中所有无向边定向后的有向图仍然有欧拉回路 那么我们首先给所有无向边随意定一个向 有向图欧拉回路的充要条件 每个点的入度和等于出度和 那么此时该图至少要保证入度和 出度和是一个偶数 然后使用网络流 源点向所有入度和 出度和的点连一条大小为 入度和 出度和 2的边 所有出度和 入度和的点连一条 出度和 入度和 2的边 无向图中边 vi vj 若变成了有向边 那么在流中连一条容量为1的边 意为反悔 满流则有解 网络流习题集锦 趣味工厂 有一个工厂 工厂中有n个工人与n种产品 每个工人能够生产这些产品中的一部分 现在我们希望作一个k天的工作规划 使得每一天每一个产品恰好有一个工人在从事生产 并且在这k天内每个工人都不会生产重复的产品 1 n 100 1 k n思考 直接的贪心算法是否正确 网络流习题集锦 趣味工厂 解答 将所有工人看做一个点排成一排在左边 所有产品看做一个点排成一排在右边 若某个工人会制造某个产品 则在相应的两个点上连容量为1的边 此时 我们考虑到对这个图做网络流 源向左边每个点都连一条容量为K的边 右边每个点向终点连一条容量为K的边 如果没有流满 那么显然是不可能有解的 而如果流满 则根据Hall定理 我们也可以知道它是有解的 然后一遍一遍进行二分图匹配即可 网络流习题集锦 路径覆盖 路径覆盖类题目 主要是指这样一类问题 给定一个图以及一系列行走规则 问如何使用最小的代价将用一系列按照行走规则的路径覆盖住 下面我们就来具体问题具体反分析 网络流习题集锦 股票走势 小L最近迷恋上了炒股 他拿到了n支股票在0到k 1时刻的价格表 他想要把每只股票的价格根据时刻依次连成一个走势折线图 以此观察股票的情况 但是小L不想铺张浪费 所以在每张纸上他不想只画一条折线 而是把尽量多的折线画到一张纸上 使用尽量少的纸 两条折线能够画到一张纸上 是要求它们不相交 包括在端点处 数据规模 1 n 100 2 k 25思考 如何找到图中的网络流模型 提示 发现 折线 这一条件的特殊性 网络流习题集锦 股票走势 解答 首先考虑如何建图 假设我们将每只个股都看做一个点 如果A与B可以放在一张纸上 就连一条边 这样得到了一个无向图 但是很不幸 这个无向图没有给我们提供任何信息 考虑到折线一定是连续的 那么两个可以在同一张纸上的股票 是可以定义序关系的的 将无向图改造成有向图 若某只股票的折线完全高于另一只股票的折线 那么连一条有向边 这样我们得到了一个拓扑图 问题转化成了用最少的链来覆盖这个有向图 即最小链覆盖 使用匹配 网络流解决最小链覆盖 由于链上每个节点都有一个后继节点 那么将每个点拆成两个点排成两排 若A能到B则从A左向B右连边 那么答案就是n 匹配数 网络流习题集锦 星际竞速 N个点M条边的有向图 将所有点从1 N标号 每条边Eij都只能从编号小的点走到编号大的点 代价为Pij 可以使用瞬移 从任意点瞬移到i号点的代价为Ai 要求从一个标号为N 1的孤立点出发 经过所有点一次且仅一次 问最小代价 N 800 M 15000 网络流习题集锦 星际竞速 分析 首先这显而易见是一道图论相关的题目 在尝试使用最短路等常见模型无法解决后 考虑流的模型 使用网络流 本题既要求能够访问每一个点 又要求代价最小 网络流模型难以满足这两个条件 使用费用流 用流量保证每个点访问一次 用费用保证代价最小 将每一次瞬移后的行动看做一条路径 考虑到每一条路径除了第一个点以外都有一个前驱点 可以使用这个条件来建图 网络流习题集锦 星际竞速 解答 建立虚拟源st与虚拟汇en 将每个点都拆成两个两个点 如u u u 从st向所有u连边 容量为1费用为0 从所有u 向en连边 容量为1费用为0 若u v之间在原图中有边 那么在u与v 之间连边 费用为路径费用Puv 容量为1 从st向所有v 连边 费用为瞬移到v点的代价 在这个图上运行费用流 就能得到最小代价 网络流习题集锦 营救行动 一个N个点M条边的带点标号的无向图 经过一条边需要一定的时间 现在有K个人在0号点 K个人可以分头行动 在访问第i号点之前不能经过第i 1号点 K个人中任意一个经过某个点之后就可以认为该点被访问了 问访问完所有点的前提下 这K个人的行走路径长度之和最小是多少 网络流习题集锦 营救行动 其实这也是一道路径覆盖的题目 相当于把1 n这个序列拆成K个序列 并使得总路程和最小 于是我们可以先用改动过的Floyd算法求出在保证只访问标号比i j都小的节点的前提下 i到j的最短路 之后和上题有相似之处 将点i拆成两个点Ai和Bi 对于i 0 由Ai向Bi连一条费用为0容量为1的边 然后Bi向汇点连一条容量为1费用为0的边 源点向B0连一条容量为k费用为0的边 每个B点都向比自己大的A点连一条容量为1费用为最短路的边 等等 这个算法好像有问题 与上一题不同的是 这题要求遍历所有节点 因此我们应该把所有A B的边增设下界1 网络流习题集锦 闭合子图 最大权闭合子图类问题 给定一些事件 事件之间有依赖关系 比如若选了A就一定要选B 建图的经典思想 S pA A inf B pB TS A TS B TA c B用c作为最小割 网络流习题集锦 加工顺序 有N个工作 M种机器 每种机器你可以租或者买过来 每个工作包括若干道工序 每道工序需要某种机器来完成 你可以通过购买或租用机器来完成 现在给出这些参数 求最大利润 N 1200 M 1200 网络流习题集锦 加工顺序 分析与解答 这道题显然是最大权闭合子图的模型 将所有任务放在左边 源向任务连容量为报酬的边 将所有机器放在右边 向汇连容量为购买代价的边 任务向它需要的机器连容量为租用代价的边 网络流习题集锦 最优选择 给定一张n个点的无向简单图 上面有一些点给定了一个整数的权值 有一些点没有 定义一条边的权值为它相关联的两个点的权值的异或 现在要求你确定剩下的那些点的权值 使得该图的边权和最小 N 500提示 按位处理 网络流习题集锦