弦图
基础定义及性质
- 邻域:同“邻居”
- 导出子图:边集包含所有两端点都在点集中的边。
- 团
- 弦图:任意长度大于 3 的简单环,都存在环上不相邻两个点有边。
弦图的子图仍然是弦图
- 点割集:定义点集 (A) 为 (u,v) 的点割集当且仅当删掉 (A) 后 (u,v) 不连通。如果不存在 (A' subset A),(A') 是点割集,那么称 (A) 为 极小点割集
极小点割集一定是团。(画图理解)
- 单纯点:邻域为团的点。
所有弦图存在单纯点,不是团的弦图存在两个不相邻的单纯点(利用点割集来归纳证明)
完美消除序列
- 完美消除序列:点标号的一个排列,满足 (p_i) 向后面所有的点连边的点组成团。
每个弦图都有完美消除序列(删单纯点来构造)
最大势算法
任选一个点开始。维护一个遍历过的点的点集,每个点维护个权值。每次选出权值最大的点,将其插入到当前完美消除序列的最前端,删掉它并将所有邻居的权值加一。
证明:略(反证大概是维护一个链,能够证明无限向右延伸)
具有完美消除序列的图为弦图(