最大势算法

引入概念

为了解决bzoj1006学习了一下弦图的求完美消除序列算法-最大势算法 Maximum Cardinality Search

诱导子图(induced subgraph) 原图的若干个节点加上点之间的连边形成的子图。

团(clique) 原图中的子图G'=(V',E')，G'为关于V'的完全图。

极大团(maximal clique) 一个团是极大团当它不是其它团的子集。

最大团(maximum clique) 点数最大的团。

弦(chord) 连接环中不相邻的两个点的边。

弦图(chordal graph)

一个无向图称为弦图当图中任意长度大于3的环都至少有一个弦。（弦图的每一个诱导子图一定是弦图。）

单纯点(simplicial vertex)

设N(v)表示与点v相邻的点集。一个点称为单纯点当{v} + N(v)的诱导子图为一个团。

引理：任何一个弦图都至少有一个单纯点，不是完全图的弦图至少有两个不相邻的单纯点。

完美消除序列(perfect elimination ordering)

一个点的序列(每个点出现且恰好出现一次)v1, v2, …, vn满足vi在{vi, vi+1,…,vn}的诱导子图中为一个单纯点。

定理：一个无向图是弦图当且仅当它有一个完美消除序列。

最大势算法 Maximum Cardinality Search

从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。

设label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号。

算法流程

维护每个结点的“势”。并维护n个链表，分别表示势为0~n-1的结点各有哪些。

维护一个best值表示当前最大的势。

再开一个bool数组记录每个点是否已被取出放入序列。

初始时每个点势为0，都放在0号链表里。best=0。

①更新操作：某结点u的势从x变为x+1时，只要把u插到x+1链表的头部，无需将其从x链表中删除（所以不用写双向链表）。然后更新best值。

②取最大操作：取最大势结点时从best链表的头开始取，如果取到的是已被放入序列的结点就删除并继续往后取，仍取不到则--best，直到取到一个未被放入序列的点。

操作①每次O(1)，总共执行O(m)次。best++也被执行O(m)次，那么操作②中--best也只有O(m)次。操作①每次插一个结点，则总共有O(n+m)个结点，而操作②中每往后取一个就删一个，所以也是O(n+m)。

然后就搞到O(n+m)了。。

要是dijkstra也这么搞的话复杂度就和边权有关了。。吃不消