弦图,区间图,完美消除,MCS,TreeDecp,PQTree及其他

BKG:某天晚上和dkw闲聊,然后随机到了一个题(ZOJ1015 Fishing Net)。

想了半天不会做。不久之后dkw说他看了题解……然后我们就找来了这个课件。。


感觉还是挺魔性的。

今天T3也是一个Chord Graph TAT.

行,现在开始抄课件.

 

图的定义

子图

G=(V,E), G'=(V',E'),V' \subseteq V , E' \subseteq E 为图 G 的子图。

诱导子图

G'=(V',E'),V' \subseteq V,E'=\{(u,v)|u,v \in V',(u,v) \in E \} 称为 G 的诱导子图。

G 的一个子图 G',满足 G' 为关于 V' 的完全图。

极大团

一个团是极大团,当它不是其他团的子集。

最大团

点数最多的团。记为 \omega (G) 

最小染色

用最少的颜色给点染色使相邻点颜色不同。色数记为 \chi (G) .

最大独立集

一个点集的最大子集使得任意两个点不连通。记为 \alpha (G) .

最小团覆盖

可以覆盖所有的点的最小团数。团数记为 \kappa (G) .

定理

\omega (G) \leqslant \chi (G) .

\alpha (G) \leqslant \kappa (G) .

弦(Chord)

连接环中的不相邻两个点的边。

弦图

一个无向图,图中任意长度 \geqslant 3 的环都至少有一个弦。

 

定理

弦图的每一个诱导子图一定是弦图。

弦图的任一个诱导子图不同构于 C_n \; (n>3)(?)

弦图判定

单纯点

一个点称为单纯点,当它和与它相连的所有点构成的诱导子图是一个团。

Lemma

任何一个弦图有至少一个单纯点,不是完全图的弦图至少有两个不相邻的单纯点。

完美消除序列

一个点组成的序列 v_1,v_2,v_3,\cdots ,v_n ,满足 v_i \{ v_i,v_{i+1},\cdots,v_n \} 的诱导子图中是一个单纯点。

定理

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

证明:略,详见课件qwq

Lexicographic BFS (LexBFS,字典序BFS)

实现困难又难记,我选择不写。

时间复杂度O(n+m) .

MCS (Maximum Cardinality Search,最大势算法)

这个算法要做的就是按照从 n1 顺序依次给每个点标号。标号为 i 的点是完美消除序列中的第 i 个点。

l[i] 表示第 i 个点与多少个已经标号的点相邻,每次选择一个 l 最大的未标号点进行标号。

😕 这个代码挺好的,但是有一点问题就是如何维护largest label.

有一个做法就是维护一个链表,并维护最大值。这样每次更新 \mathrm{label} 都是 O(1) 左右的。

还要啰嗦一句的是,存在MCS和BFS都得不到的完美消除序列。(但是我不会找……  🙁 )

相邻点判定完美消除序列(判定弦图)

1 \sim n 枚举序列中的每个点。

\{ v_{i+1},\cdots ,v_n \} 中所有与 v_i 相邻的点依次为 v_{j1},\cdots,v_{jk}

每次判断 v_{j1} 是否与 v_{j2},\cdots,v_{jk} 相邻即可。

时间复杂度 O(n+m)算法的正确性证明咕了,等我翻完论文看看有没有给出。

CODE

这份是 BZOJ1242 的代码,这玩意包括了求一个图的 PEO (Perfect Elimination Orderings) 和判定一张图是不是弦图 QAQ

(这段文字和这篇文章的首发差了半年的时间,233

弦图相关

寻找极大团

Lemma

设第 i 个点在弦图的完美消除序列的第 p(i) 个。

N(v)= \{ w | w \text{与} v \text{相邻且} p(w)>p(v) \} ,那么弦图的极大团一定是 v \cup N(v) 的形式。

推论

弦图最多有 n 个极大团。

我们只需要判定每个 v \cup N(v) 是否为极大团。

A = v \cup N(v) , 若存在 B = w \cup N(w) 使得 A \subseteq BA 不是极大团。

首先我们可以得到 p(w)<p(v)

\mathrm{next} (v) 表示 N(v) 中最前的点, w* 表示在所有满足 A \subseteq Bw 中最后的一个点。

可知 \mathrm{next} (w*) = v 。若不是,则 \mathrm{next} (w*) 也是一个满足上述条件的点,得证。

那么, v \cup N(v) \subseteq w \cup N(w) 当且仅当 | N(v) | +1 \leqslant | N(w) |

我们只需要判定是否存在一个 w ,满足 \mathrm{next} (w) = v| N(v) | +1 \leqslant | N(w) | 即可。

时间复杂度 O(n+m)

 

<<此处本应有代码>>

 

弦图点染色

行……我们终于来到了这个题……

HNOI2008 神奇的国度。

用最少的颜色给每个点染色,使得相邻的点染色不同。

有一个神奇的做法:

求出完美消除序列,从后向前给每个点染上可以染的最小色。

团数=色数。证明:比较简单,咕了,看课件吧

O(n+m)

弦图最大独立集,最小团覆盖

最大独立集:完美消除序列从前往后能选就选。

最小团覆盖:最大独立集的每个点都与它的邻点组成一个团,以此求出最小团覆盖。

\alpha (G) = \kappa (G)

区间图

定义

在序列上给定一些区间,定义一个相交图为:

  1. 每个顶点表示一个区间
  2. 两点之间有边,当且仅当对应代表的区间的交集非空。

如果一个图是若干区间的相交图,则它是区间图。

定理

区间图一定是弦图。

证明略,详见课件。

区间图完美消除序列

将所有的区间按照右端点从小到大排序。

没了。。。证明depends on我能不能找到了

区间图最大独立集

问题:给定 n 个区间,求一个选择最多区间的方案,使得所有区间的交集为空。

Sol:最裸的题,最大独立集。完美消除序列上的判定可以做到 O(n\log _2 n)   (线段树或堆),非常优秀。

区间图最小染色

n 个高度均为 1 的积木,第 i 个位于 [L_i,R_i] 的位置   (也就是起点在 L_i ,宽 R_i-L_i )。

求一个积木下落顺序,使得最后积木总高度尽可能小。

就是求一个最小染色,方案则是按照颜色编号从小到大掉落。

一个很意识流的解释就是尽量让不交的区间落在一层上。

更多实现上的细节:我们可以倒过来排序,然后依次处理。也是 O(n \log _2 n) 的。

判定区间图

  • 判定是否为弦图。
  • 找出所有的极大团。
  • 构建一个 顶点-团矩阵 A ,使得 A 的每一行代表 G 的一个顶点,每一列代表 G 的极大团。满足 A_{ij}=\begin{cases} 1 \; \mathrm{if} \; v_i \in C_j \\ 0 \; \mathrm{otherwise} \end{cases}
  • 判断是否存在一个重排方式,即任意交换 A 的各列,使得每行的所有 1 都是连续的。如果这种排列存在,就称这个矩阵具有连续 1 性质。
  • 可以用PQTree来实现(这就是作死)

 

  • 另外一种判定方法
  • 《A new Test for Interval Graphs》


 

Tree Decomposition

一个无向图 G=(V,E) 的 树的分解(Tree Decomposition) 定义为 (X,T) ,\; X= \{ X_1,X_2, \cdots ,X_m \} ,其中 X_iV 的一个子集, T 是一棵树,点集为 X

一些性质

X_1 \cup X_2 \cup \cdots \cup X_m = V

对于 G 中任意一条边 (u,v) \;,\; \exists X_i 使得 u,v \in X_i

对于每个点 v,P(v)= \{ X_i | v \in X_i \} ,则 TP(v) 的诱导子图是联通的。

所以这玩意到底有啥用啊 🙁

Clique Tree

clique tree是一种tree decomposition.

一个无向图 G 为弦图当且仅当存在一个clique tree.

一个无向图为区间图当且仅当存在一个链形态的clique tree

所以这玩意到底又有啥用啊 🙁

构建弦图Clique Tree

感觉这玩意没用。我Bing了一下Clique Tree看到的全是概率学玄学……

愿意学的看课件吧。

 

 

 

 

 

 

 

 

 

 

 

#洛谷P1967 货车运输

题目描述

A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。

输入输出格式

输入格式:

输入文件名为 truck.in。

输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道

路。 接下来 m 行每行 3 个整数 x、 y、 z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意: x 不等于 y,两座城市之间可能有多条道路 

接下来一行有一个整数 q,表示有 q 辆货车需要运货。

接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,注意: x 不等于 y 

输出格式:

输出文件名为 truck.out。

输出共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货

车不能到达目的地,输出-1。

先Kruskal跑一下最大生成树,就是把边权改成从大到小排序就行。

然后用倍增思想在有根树上记录一个minp[i][k]数组,表示这个点i上跳2k的高度,经过路径的最小边权:

显然它等于minp[i][k-1]和minp[l[i][k-1][k-1]中的最小值。也就是它向上跳2k-1高度的minp和从depth[i]-2k-1高度再往上跳2k-1高度的minp(参照倍增的思想)

而向上跳2k-1高度能够达到点l[i][k-1],这个就属于LCA的基本操作了吧……

注意初始化。

还要维护一下点的联通行……用Kruskal留下来的UFS就行。

USACO 牛的旅行 Cow Tours

一道比较困难的Floyd题目。

首先路径肯定都会算,就不说了。其次,Floyd也没有什么问题。

我们的策略是枚举两个不联通的点,把他们联通,求出新牧区的最小直径。

关键细节看代码

(如果有哪位dalao知道为什么要 if (i!=k && j!=k && i!=j) 麻烦您在评论中回复我

 

 

 

#洛谷 通往奥格瑞玛的道路

题面对我来说貌似有毒,看了很长时间才看懂这是一个最大值最小问题 果断二分答案。

主要思想是先跑一边Bellman-Ford+队列优化(也叫SPFA)把二分值设定成+∞ 然后看一看如果到终点的花费大于血量就输出AFK(away from keyboard)

如果可行就快排点权+二分下标 如果当前二分值可以跑到终点(跑SPFA判)就向左找(升序sort),不然就向右找。

跑SPFA的时候传一个upat也就是二分值 把点权大于二分值的点都判(删)掉 

 

还有一点就是最后还要判一下二分值。链式前向星+SPFA+手写Sort,没有注释……