Skip to content

《组合数学》缩写(六)

第12章

有向图就是边是顶点的有序对的图,也就是说每个边都有起始顶点和终止顶点。任意两顶点间有且仅有一条边的有向图叫竞赛图。若任两顶点间都可以沿有向路径互达,图就是强连通的。

无向图的强连通定向就是把每条边指定一个方向,然后保证得到的有向图是强连通的。强连通定向存在当且仅当原图中没有桥。构造出这一强连通定向事实上很简单:按照一遍DFS的访问方向给边定向就可以了(书中的算法一如既往地麻烦)。

核心分配问题是这样的:n个商人,每人有1个商品,每人对所有n个商品按照自己的喜好进行排序。求一个把n个商品分配给n个人的方案,使不存在几个商人的集合,他们把分到的商品再次进行交换后可以使每个人都更满意。算法是:每个商人对自己最喜欢的商品的主人连一个有向边,找一个圈(由于每个点都有出边,所以这肯定是能找到的),按照这个圈进行分配,把已分配的顶点删掉,所有指向这些顶点的边重新计算。

网络就是存在源点s和汇点t的有向图,其中每条边都有一个可以认为是“容量”的权值。网络中的流定义为加在每条边上的一个函数,也就是说给每条边指定一个“流量”。合法的流应该满足:每条边的流量不超过其容量,除源点和汇点外,点的出边的容量和与其入边的流量和相等。流的净流量就是源的出边的流量和或汇的入边的流量和。求一个合法的净流量最大的流就是最大流问题。

网络的割是一组边的集合,满足把这些边从原图中删去后从源点到汇点不再连通。最小割就是边的权值(就是上述“容量”)和最小的割。最大流最小割定理的内容就是:网络中的最大流的值等于最小割的值。

求解最大流问题和最小割问题可以采用残量网络增广路的方法。这在很多很多资料中都有很好的介绍。《组合数学》这书似乎并不是学网络流的好教材。

第13章

χ(G)是图G的色数,就是说给图的每个顶点赋一个颜色使所有边的两个端点的颜色不同,需要的最少颜色数目。它也可以理解成将顶点划分成若干个集合,使每个集合的导出子图都是零图的最少集合数目。求图的色数很困难。

关于图G的色多项式pG(k),也就是说将图G用k种颜色的方法数。有一个结论:设T是一棵n阶树,则pT(k)=k(k-1)^(n-1)。它的证明也简单:第一个顶点有k种着色方式,以后每添加一个与当前顶点相邻的顶点都k-1种着色方式(因为它仅与一个顶点相邻),根据乘法原理得证。另外,n个顶点的零图的色多项式是k^n。求色多项式的一种方法是:当G不为零图时,设x、y是一对邻接顶点,设G1为原图去掉边x、y的图,G2为原图将x、y合并成一个顶点的图(原来与x或y相邻的顶点均与新顶点相邻),那么就有pG(k) = pG1(k) – pG2(k),递归求解即可。这个算法的正确性还比较好理解的,不过显然它是指数级的算法。它可以采用非递归的方法实现,就是维护一个图的集合,每次取出一个非零图的元素把它分成两个元素。

平面图就是可以“画”在平面上而且边不交叉的图。(更“数学”的定义似乎书上没有。)它有一些很好的性质:设一个连通的平面图的平面表示有n个顶点点、e条边曲线、r个所围区域,则:n+r-e=2。证明的方法是先对树证明,再往树上加边,保持等式始终成立。一个平面图必存在一个顶点,它的度至多是5,这是欧拉公式的推论。

五色定理是:一个平面图的色数至多是5。这个可以比较简单地证明,主要根据上面的欧拉公式的推论来利用那个特殊的顶点做突破口。它的加强版本四色定理也是成立的。

图的独立集的定义是一个顶点的集合,它的导出子图是零图。图的独立数α(G)就是图中最大的独立集的大小。求图的独立数很难。图的控制集是一个顶点的集合,它满足所有不在集合中的顶点都与集合中的点有边。最小的控制集的大小称为图的独立数dom(G)。图的团就是一个顶点的集合,它的导出子图是完全图。图中的一个团是图的补图的独立集,反之亦然。图的团数ω (G)是最大的团的大小。将图的点集划分成最少的团的数目称为团划分数θ(G)。完美图满足它的任何一个导出子图有χ(G)=ω (G)且α(G)=θ(G)。

图的弦就是连接圈的两个顶点且不属于该圈的一条边。如果每一个长度大于3的圈都有弦,图就被称为弦图。所有的弦图都是完美的。所有的区间图(定义不说了)都是弦图。

以上定理的证明均略,因为第一我也搞不太懂,第二它们在OI中似乎没什么用。

图的顶点连通度κ(G)是最少删去多少个顶点可以使图不再连通,定义κ(K_n)=n-1。边连通度λ(G)是最少删去多少条边可以使图不再连通。再设δ(G)表示图中顶点的最大度,则有显然的不等式κ(G)≤λ(G)≤δ(G)。

顶点连通度κ(G)不小于k的图称为k-连通图,一个图是2-连通图与以下结论等价:没有关节点;任两个顶点a、b都存在一个包含a、b的圈;每三个顶点a、b、c,都存在一条连通a、b且不经过c的路径。这些都很好证明。

关于图的点连通度的Menger定理的内容是这样的:设k是一个正整数,G是一个阶为n≥k+1的图,则G是k-连通的当且仅当对任意两个不同的顶点a和b都存在连接a、b的k条路径使得每对路径只有a和b两个公共点。

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*