弦图学习笔记

预备知识

:若子图G’是一个完全图,则G’是G的一个团。

极大团:不被其他团包含的团。

最大团:点数最多的团。

团数:最大团的大小。

最小染色:用最少的颜色染完图并且相邻两点颜色不同的颜色数量。

最大独立集:最大的一个点的子集使任何两个点不相邻。

最小团覆盖:用最少个数的团覆盖所有的点。

诱导子图:对于图G和点集V,当子图G’的点集为V,边集为G中两点都在V中的边,称G’为G的一个诱导子图。

性质

$团数\leq 色数$

$最大独立集\leq 最小团覆盖$

一、定义

弦图指没有长度大于3的简单环的无向图。

二、判定

单纯点:对于点v即其邻接点N(v),v+N(v)组成一个团,则称v为单纯点。

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

 

完美消除序列:对于序列An,若任意Ai都有Ai为点集为{Ai,Ai+1,Ai+2,…,An}的诱导子图的单纯点,则An被称为完美消除序列。

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

证明

(充分性) 由引理知任何一个弦图都至少有一个单纯点以及弦图的诱导子图都是弦图。可以使用数学归纳法假设当点数<n的弦图一定有完美消除序列,那么点数为n的弦图的完美消除序列可以由一个单纯点加上剩余点的诱导子图的完美消除序列得到。

(必要性)反证若无向图存在一个长度 > 3的无弦环,不妨设环中在完美消除序列中出现在最前面的点为v,设环中vv1, v2相连,根据完美消除序列的性质知v1, v2相连,与环无弦矛盾。所以无向图为弦图。

最大势算法(MCS):用于求图的完美消除序列。

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

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

再对于其的邻接点的degree加1。

可以维护一个degree为0~n的链表,存储点的编号,维护最大的degree,详情看代码。

均摊后时间复杂度为O(n+m)

三、性质

$团数=色数$

$最大独立集= 最小团覆盖$

关于“弦图学习笔记”我的1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注