图论小结（一）包括一些最短路，最小生成树，差分约束，欧拉回路，的经典题和变种题。强连通，双连通，割点割桥的应用。二分匹配
图论小结（一）&
下面是对暑假集训的图论部分的一些总结和体会。&
包括一些最短路，最小生成树，差分约束，欧拉回路，的经典题和变种题。强连通，双连通，割点割桥的应用。二分匹配，KM，支配集，独立集，还有2-SAT。&
下面就暑假写过的一些题做一个小结。&
（1）最短路的话一个主要掌握三个算法和两个优化。Dijsktra单源最短路，可以变形他的松弛条件，而产生很多的最短路变种，题型非常灵活。Floyed可求全源最短路。时间复杂度是O（n^3），空间复杂度是O(n^2)，可用于小数据范围的快速求解，更适合于稠密图，另外将更新条件更改还可求传递闭包。还有贪心的floyed倍增。而对于存在负权回路的图来说，bellman-ford可求解该情况下的最短路，如果不存在最短路将会报错。其优化是SPFA。其算法的时间复杂度是O（kE），当边比点大较多倍时，效果不是特别理想。此时dijsktra的heap优化会有更好的效果。由bellman-ford相关的有差分约束系统。其难点在构造出一组相同符号的不等式，然后利用bellman-ford构造进行解的存在性判断。下面是一些相关的题目。&
Heavy Cargo ：这个是求所有边中最小边的最大值。将dijsktra的转移方程更改为dist[j]=max(dist[j],min(dist[k],map[k][j]));其中k是当前的距离最小点，j是松弛遍历的点。&
Frogger ： 这个和上面的相反，是求所有边中最大边的最小值。转移方程改为dist[j]=min(dist[j],min(dist[k]),map[k][j]);注意细节。memset里面的0x7f和常数赋值的0x7f差别很大。常数赋值的数值很小。而memset内部是按照字节进行赋值。是一个很大的值。&&
这一道题是一道最短路的变种。实际上是求所有路径中最大边的最小值。 起点是1，终点为2.&
King 差分约束系统: 将所有的不等式全都转化成&=的形式，如&1变为&=0. 注意建模。即构造不等关系。然后将两端点反向存图。接着就上bellman.&
关于最短路还有一些求路径的问题，第k短路，多条最短路问题，还有每条路可重复行走的最短路径问题，二维dijsktra，都等待接下去一个月的陆续补充。&
（2）接下去是最小生成树。目前只涉及到很粗浅的部分，不再多说。就几个题。&
Arctic Network，The Bug Sensor Problem 最小生成树求第k大边 。很简单，对所有的边排序即可。&
&Communication Planning for Phobos 最小生成树加计算几何double dis(double x1,double y1,double x2,double y2,double R)&&&
{&&& //参数都是弧度表示的&&&
&&&& x1=pie*x1/180.0;&&&
&&&& y1=pie*y1/180.0;&&&
&&&& x2=pie*x2/180.0;&&&
&&&& y2=pie*y2/180.0;&&&
&&&& return R*(acos(cos(x1)*cos(x2)*cos(y1-y2)+sin(x1)*sin(x2)));&&&
}& 主要记下一个计算球面点距离的公式即可。&
（3）欧拉路径问题。&
欧拉路径问题就写了两篇，但都是博客里访问量较大的两篇，将近一千人。&
第一个是 Play on Words 并查集加欧拉回路：&
该题构图的时候将每个单词拆开，每个单词的第一个字母和最后一个字母记为两个节点，又第一个字母向后一个字母连一条有向边。第一个字母节点的出度++，后一个节点的入度++。&
这道题将图当做无向图，然后用并查集处理连通性的问题。再记录每个点的出度和入度。 然后用欧拉路的定义来求解。存在欧拉回路的条件是：所有点出度==入度。 存在欧拉道路的条件是：有且仅有两个点出度！=入度，且出度和入度之差为1.其余点出度==入度。&
第二个题是关于欧拉途径的拓扑输出问题。&
&John's trip& 欧拉回路输出路径：用& g[u][e]=v; g[v][e]=u;的方法将点对应的边记录下来。&&
深搜的时候直接输出。&
如果有一个点的度数为奇数，就说明他的入度！=出度。即不存在欧拉回路。&
规律：考虑用欧拉回路解题，一般题目中有每一边（或是点）都只遍历过一次，最后会回到起点，问路径是否存在，若存在，路径输出等问题。&
（4）强连通分量。&
如果一个集合内的任意两点两两互达，则该两个点属于一个强连通分量中。强连通分量很重要，也常作为复杂题的预处理，缩点等问题，就是将一个强连通分量等效为一个点来处理。可以通过处理缩点的出度和入度而高效的处理一个图。还可以直接利用强连通分量的性质，判断属于一个强连通分量里的两个点互达性，连通性。&
&The Bottom of a Graph 强连通分量加缩点：题意比较晦涩，大致就是求一个图缩点后出度为0的点的个数 。&
The Busiest Man 强连通分量+缩点+传递闭包 !&&
强连通分量+缩点+传递闭包。有n种物品，现给出m种关系，每种关系a,b对应着物品b能够用物品a来换，然后有q个询问(a,b)，问物品a能不能换到物品b。刚开始是判断两个点是否在一个连通分量里，后来想下题目有问单向可达即可，判连通分量范围太小，是错的。这题直接搜索也能过。但是如果传递闭包的话，直接用floyed超时。可以先缩点，再对新图求传递闭包。这是一类关系问题中的单向连通。是一类有代表性的题目。&&
（5）求一些关于图的性质的题。如求割点和割边。&
SPF ，network ，tarjan算法求割点。具体见博客的代码。&
这类题一般会有删除某个点或某条边将图分为两部分或者不再连通。可以求连通块的个数或者是割点的个数，割边的个数，割点的编号。&
（6）二分图匹配。&
二分图匹配和2-SAT其实都是下面即将讲到的网络流的一个分支吧。其实这些图问题是共通的吧。&一切问题皆网络流&。这些问题都可以转化为网络流来求解。但是又由于二分图和2-SAT有着自己模型和特点，所以有着更为简便的解法。&
首先二分图最大匹配等价于最小点集覆盖。&
这些题一般都会给一些配对关系，然后求最大可匹配的组数。构图的时候有的需要将点离散开处理T-Shirt Gumbo 二分最大匹配 hoj ，有些需要将点拆分，如两个棋盘覆盖问题。建立点和点自身的匹配关系。&
下面主要介绍下棋盘覆盖的二分图经典模型。&
Don't Get Rooked 二分最大匹配经典题&&
可以把一个图拆分成两个图。一个统计行，另一个统计列。如果一行连续，则将该连续块打上一个相同的标号，否则，标号加1，该部分的处理有点麻烦。这两个图的坐标如果有相等的部分，就在此连一条边.也是点拆分的建图方法，自身条件匹配，很经典的题。&&
poj 2446 Chessboard 二分图最大匹配经典题&&
题意是在一些有洞的棋盘上用一个1x2的方形条将棋盘完全填满。可以对不是洞的每一个点找和他相邻的点，如果他相邻的点也不是洞的话，就画一条边。然后获取标号。实际上就是一个将一个点拆分成两个点的想法。将||可能||，可能匹配的点都连一条！！&&
（7）网络流。这是一个大块。关于这个部分的很多总结都要留待以后，在此只做几道模板题的说明。网络题重点是建模。建立图的网络模型。然后模板套之。&
&A Plug for UNIX 最大流&
题意就是给了你m个电器，n个插头，tt个转换器，以及自己增加一个虚拟的源点和汇点。将转换器和插头相连的边置为无穷大。&&
其余的边长度都置为1.该模板中n表示图中节点的总数。最后要记得修改。还有一点需要注意的就是转换不是只有样例中给出的'X，可能有无数个，无数种类型。&&
在这里借鉴了一种网上map的写法。很简介。下面这个网址给了一张图很详细。一看便知/longdouhzt/archive//2165860.&
&Power Network 最大流基础 hoj&
题意中给出多个节点和多个发电站与消费站。可以建一个虚拟的源点和虚拟的汇点，将所有的发电站和源点连一条边，将所有的消费占和汇点连一条边。&&
然后利用网络流建图即可。下面是SAP算法。&
也是给定一些匹配关系求最值问题的模型。&
您对本文章有什么意见或着疑问吗？请到您的关注和建议是我们前行的参考和动力&&
您的浏览器不支持嵌入式框架，或者当前配置为不显示嵌入式框架。trackbacks-0
【问题分析】
二分图点权最大独立集，转化为最小割模型，从而用最大流解决。
【建模方法】
首先把棋盘黑白染色，使相邻格子颜色不同，所有黑色格子看做二分图X集合中顶点，白色格子看做Y集合顶点，建立附加源S汇T。
1、从S向X集合中每个顶点连接一条容量为格子中数值的有向边。2、从Y集合中每个顶点向T连接一条容量为格子中数值的有向边。3、相邻黑白格子Xi,Yj之间从Xi向Yj连接一条容量为无穷大的有向边。
求出网络最大流，要求的结果就是所有格子中数值之和减去最大流量。
【建模分析】
这是一个二分图最大点权独立集问题，就是找出图中一些点，使得这些点之间没有边相连，这些点的权值之和最大。独立集与覆盖集是互补的，求最大点权独立集可以转化为求最小点权覆盖集（最小点权支配集）。最小点权覆盖集问题可以转化为最小割问题解决。结论:最大点权独立集 = 所有点权 - 最小点权覆盖集 = 所有点权 - 最小割集 = 所有点权 - 网络最大流。
对于一个网络，除去冗余点（不存在一条ST路径经过的点），每个顶点都在一个从S到T的路径上。割的性质就是不存在从S到T的路径，简单割可以认为割边关联的非ST节点为割点，而在二分图网络流模型中每个点必关联到一个割点（否则一定还有增广路，当前割不成立），所以一个割集对应了一个覆盖集（支配集）。最小点权覆盖集就是最小简单割，求最小简单割的建模方法就是把XY集合之间的变容量设为无穷大，此时的最小割就是最小简单割了。
有关二分图最大点权独立集问题，更多讨论见《最小割模型在信息学竞赛中的应用》作者胡伯涛。
阅读排行榜
评论排行榜独立集，覆盖集，支配集，最大团，最大匹配
编辑：www.fx114.net
本篇文章主要介绍了"独立集，覆盖集，支配集，最大团，最大匹配"，主要涉及到独立集，覆盖集，支配集，最大团，最大匹配方面的内容，对于独立集，覆盖集，支配集，最大团，最大匹配感兴趣的同学可以参考一下。
/RyanWang/archive//81617.aspx
&&& 独立集是指图的顶点集的一个子集,该子集的导出子图不含边.如果一个独立集不是任何一个独立集的子集, 那么称这个独立集是一个极大独立集.一个图中包含顶点数目最多的独立集称为最大独立集。最大独立集 一定是极大独立集，但是极大独立集不一定是最大的独立集。
&&& 与独立集相对应的就是支配集，支配集也是图顶点集的一个子集，设S 是图G 的一个支配集，则对于图中的任意一个顶点u，要么属于集合s,
要么与s 中的顶点相邻。 在s中除去任何元素后s不再是支配集，则支配集s是极小支配集。称G的所有支配集中顶点个数最 少的支配集为最小支配集，最小支配集中的顶点个数成为支配数。
最小点的覆盖：
&&& 最小点的覆盖也是图的顶点集的一个子集，如果我们选中一个点，则称这个点将以他为端点的所有边都覆盖了。将图中所有的边都覆盖所用顶点数最少，这个集合就是最小的点的覆盖。
&&&&图G的顶点的子集，设D是最大团，则D中任意两点相邻。若u，v是最大团，则u,v有边相连，其补图u,v没有边相连，所以图G的最大团=其补图的最大独立集。
一些性质：
最大独立集+最小覆盖集=V
最大团=补图的最大独立集
最小覆盖集=最大匹配
本文标题：
本页链接：任意图支配集精确算法回顾
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
任意图支配集精确算法回顾
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口图论讲义第5章-支配集_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
喜欢此文档的还喜欢
图论讲义第5章-支配集
数​学​建​模​ ​资​料
阅读已结束，如果下载本文需要使用
想免费下载本文？
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢