文件名称：分层图上的动态规划-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2024-06-29 16:21:34
集训队论文集
4.2 基于图上阶段划分思想的最大独立集算法 4.3 分层图上的动态规划 对于图 G = (V, E)，将点集 V 划分为 k 个不相交的集合 V1,V2, · · · ,Vk，使得对任意 u ∈ Vi, v ∈ V j，若 |i − j| > 1，则 (u, v) < E，则称集合序列 < V1,V2, · · · ,Vk >是 G的一个分 层。如果每个 Vi 中的结点都不多，那么可以按 V1,V2, · · · ,Vk 顺序进行决策，在每个阶段只 需状压一个层的选取情况即可，效率远高于一般图中的对整个图状压DP。 记 f (i, S )为图 G[V1 ∪ V2 ∪ · · · ∪ Vi]中包含 S 为子集的最大的独立集，状态转移方程如 下： f (i, S ) = −∞, S is not independent, 0, i = 0, max{ f (i − 1, S ′)|S ′ ⊆ Vi−1, S ∪ S ′ is independent} + |S ′|, otherwise G 的独立数为所有 G[Vk]的独立集 I 中 f (k, I)的最大值。该过程同样能求出一个 G 的 最大独立集，方法和之前类似，这里不再赘述。 这个算法的时间复杂度为 O( ∑k−1 i=1 2 |Vi |+|Vi+1 |)，不过在大多数情况下，每个 Vi 内的独立集 个数并不多，实际的时间效率远高于理论上界。 4.4 “k-仙人图”上的动态规划 例 5. 给定简单无向图 G = (V, E)，保证每条边属于且仅属于一个简单环，求 G 的独立数。 |V | ≤ 50, 000，|E| ≤ 60, 000。17 如果 G 不连通，那么求出 G 的每个连通块的独立数并求和即可。下文假设 G 是连通 图。每条边最多属于一个简单环的简单连通图称为“仙人掌”，它有什么特殊的性质呢？ 17题目来源：LYDSY 4316 44