中学生论文利用特性质解图论题

1、利用特殊性质解图论题利用特殊性质解图论题南京外国语学校 乔明达一、引言 求解图论问题的过程 第一步，具体的问题转化为抽象的模型 第二步，用现成的经典算法求解这个模型 特殊的问题化为一般的模型：失去特殊性 利用特殊性质：降低算法的时间复杂度以及实现的难度 网络流模型的优化 特殊条件下求哈密尔顿回路二、网络流模型的优化例题三 linear kingdom races 题目来源：codeforces beta round #87 一条大道分为n个单位长度，把某个单位长度修建为跑道需要一定的费用。现在有m个赛跑比赛，其中每一个比赛有一个起点和一个终点，如果起点到终点的道路都修建为跑道，那么这个比赛能带

2、来一定收益。不同比赛可以共用跑道。求最大净收益。 n,m200000最小割建模 每个比赛有一定的收益 需要一些道路的修建 修建道路有一定的代价最小割建模sa1a2a3b2b3b4b1b5t动态规划 表示道路1i中修建一部分能够得到的最大收益 如何计算 如何快速求最大值1), 1(), 1(maxmaxifijsijwjfifif1,), 1(maxmax1,), 1(maxmaxifisumjsumijwjfififjsumisumijwjfif), 1(ijw动态规划的优化 考虑 新增的比赛以道路 为终点 比赛区间为 ，收益为 对于所有 ， 都要在 的基础上增加 线段树维护！) 1, 1()

3、, 1(ijwijwi,ixyxk ),(ikw) 1,(ikwy例题四 cow coupons 题目来源：usaco 2012 february gold 有n件物品，每件物品有一个售价和优惠价，优惠价严格小于售价。最多能以优惠价购买k件物品，求用m元最多能买多少件物品。 n50000费用流建模 买x件物品最少需要花多少钱sabx1x3x4tx2观察增广路 即使用优惠价买某件物品，费用为c0isabit观察增广路 即使用原价购买某件物品，费用为c1isabit观察增广路 原本用原价购买i，现改为优惠价购买i，原价购买j，费用为c0i+c1j-c1isabjit观察增广路 原本用优惠价购买i，

4、现改为原价购买i，优惠价购买j，费用为c1i+c0j-c0isabjit分析增广路 第三种增广路不会出现 前k次增广一定走第一种增广路 s到a的容量一直是0，不可能走出第三种增广路数据结构维护 假设当前用优惠价购买的物品集合为s0，用原价购买的集合为s1 我们只要考虑快速求出以下值： 用堆或平衡树维护！| 0min10ssiic| 1min10ssiic| 0min10ssiic| 0 1min0siicic小结 反向思考例题三 直接给出网络流的模型 联想到本题的实际意义 采用动态规划求解 例题四：利用费用流增广路的特殊性质 相似的题目：apio2007数据备份三、特殊条件下的哈密尔顿路问题例

5、题五 yetanotherhamiltonianpath 题目来源：topcoder srm 496 给出一个有n个顶点的无向完全图，每个顶点标有一个字符串si，定义v(s)为字符串s长度的平方，lcp(s,t)为字符串s和t的最长公共前缀。那么点i与点j的距离为v(si)+v(sj)-v(lcp(si,sj)。求点0到点1的最短哈密尔顿路径。 n50问题的简化 唯一的特殊性：权值的计算方式 每个点在路径中出现次数一定 一定 最大化 求一条点0和点1相邻的最长哈密尔顿回路)()(jisvsv),(jisslcpv在trie树上考虑问题 把所有串建成一棵trie树 lcp的长度=lca的深度 同

6、一子树内两个点的距离至少是1 不同子树间点的距离一定是0 尽量减少从一个子树走到另一个子树的次数 故最长路径一定是依次经过每棵子树的 对于trie中的其它结点，我们也能得到同样的结论可行性的证明 按照字典序遍历，哈密尔顿回路最长 不能保证点0和点1相邻 不同字母之间大小关系是没有用的 孩子可以随意交换 把点0和点1交换到字典序相邻的位置最终解法 把所有字符串按照字典序排序 以这个顺序得到哈密尔顿回路 回路长度减去点0到点1的距离例题六 alice and bob 题目来源：poj 1429 有一个正n边形，n个顶点随意标号为1n。除了n条边之外，又画了m条互不相交的弦。现在给出这(n+m)条边

7、，求这个图的一条哈密尔顿回路。 3n10000，0mn-3分析所求哈密尔顿回路 特殊性：构造方法 原正n边形是一条哈密尔顿回路 存在其它的哈密尔顿回路吗？nie！ 假设有另一条哈密尔顿回路，那么我们至少走了一条弦。因为弦之间不相交，所以这条弦把剩下的(n-2)个点分成了两个集合，且之间没有边，因此不存在哈密尔顿回路，矛盾。问题的分析 找哈密尔顿回路等价于找出这个多边形的n条边 如果一个点的度数恰好为2，那么这个点连出的2条边都是哈密尔顿回路上的边归纳法 n=3：不存在弦，哈密尔顿回路可以确定 n3：归纳到n-1的情况情况1 红点的度数为2，故两条粗边一定在哈密尔顿回路上。 删除红点，剩下的4个

8、点找哈密尔顿回路 注意：红色边不属于答案，打上标记情况2 红点度数为2，删除后，相邻两点的度数变为1，不存在哈密尔顿回路 连一条红色的虚边，同样打上标记归纳法的正确性 这样的度数为2的点一定存在吗？ l,rl+1,mid-1lrmid题目总结 经过证明，我们总是能把规模较大的问题转化为规模较小的问题。 规模为3的时候问题很容易解决，因此原问题得到了解决。 在实现算法的时候，可以用一个队列存储度数为2的点 其它细节这里不再赘述例题七 strange graph 题目来源：sgu 156 给出一个无向图，有n个点和m条边，满足以下性质： 1、没有重边和自环。 2、每个点的度数大于等于2。 3、每个

9、度数为2的点，它的两个邻点之间没有边。 4、每个度数大于2的点，它的邻点中存在一个度数为2的点，而且除了这个点以外，任意两个邻点之间都有边相连。 要求判断这个图是否存在哈密尔顿回路，存在则输出一组解 n10000，m100000分析图的性质 特殊性质：点的度数 把所有度数为2的点称为“v点” 考察一个非v点x0，设度数为(d+1)，d2 设x0连接着t0,x1,x2,.,xd分析xi的性质 x1xd会是v点吗？nie！ 反证法 反设x1是v点 点x1已经连接着x0,x2,x3,.,xd，共d个点 故d=2 然而x0与x2是相连的，与题目中的条件3矛盾考虑xi的邻点 xi不是v点，因此连接着某个

10、v点ti xi除了xj(ij)之外还有其它邻点吗？nie！ 反证法 反设xi还连接着点p 那么根据条件4，点p与x0之间有边 我们前文中假设x0的邻点仅有t0和x1xd 矛盾，故xi除了xj(ij)之外没有其它邻点图的性质 x0xd构成一个大小为(d+1)的团 团中每个点连向团外的边有且仅有一条 这些边都连接着某个v点 图中每个点要么是v点，要么属于一个团求哈密尔顿回路 v点度数为2 它的两条邻边都需要经过恰好一次 团中每个点都向外连着某个v点 团上的每个点也能保证至少经过一次收缩团 团内的边“可有可无” 团内没有一条边必须要经过 从团中某个点到另一个点时，这条边一定存在 把团缩成点 要求每条边恰好经过一次 哈密尔顿回路转化为欧拉回路总结 网络流模型是图论中非常重要的一部分，但是算法比较复杂且调试困难。如果建模的时候建成了比较复杂的模型，很可能需要较多的时间解题。此外网络流在点数较大的时候不能解决问题，因此有时需要转化为其它模型，或者使用数据结构优化。我们在解题时需要充