弦图与区间图「建议收藏」

弦图与区间图「建议收藏」弦图与区间图

大家好,又见面了,我是你们的朋友全栈君。

弦图与区间图


参考资料:陈丹琦《弦图与区间图》


  1. 预备知识

    图定义为\(G=(V,E)\),其中\(V\)为点集,\(E\)为边集。

    子图定义为对于原图\(G=(V,E)\)的子图\(G’=(V’,E’),V’\in V,E’\in E\)

    对于原图\(G=(V,E)\),诱导子图\(G’=(V’,E’),V’\subseteq V,E’=\{(u,v)|u,v\in V,(u,v)\in E\}\)

    团定义为原图的一个子图为完全图称为团。极大团定义为一个团不为另一个团的子集。最大团为点数最多的团。\(\omega(G)\)表示团数。

    最小染色为用最小的颜色给点染色使相邻的点的颜色不同。\(\chi(G)\)表示色数。

    最大独立集为最大的一个点的子集使任何两个点不相邻。\(\alpha(G)\)为最大独立集的点数。

    最小团覆盖为用最少的团覆盖所有的点,\(\kappa(G)\)为用的最少的团数。

    \(\omega(G)\le \chi(G)\),团数\(\le\)色数;\(\alpha(G)\le\kappa(G)\),最大独立集数\(\le\)最小团覆盖数。

  2. 弦图

    弦定义为一个环中连接不相邻的点的边。

    一个图被称为弦图当图中所有长度大于3的环至少有一个弦。

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

  3. 弦图的判定

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

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

    完美消除序列:一个点的序列\(v_1,v_2,\dots,v_n\)满足\(v_i\)\(\{v_i,v_{i+1},\dots,v_n\}\)的诱导子图中为一个单纯点。一个图为弦图当且仅当存在一个完美消除序列,证明可详见论文。

  4. 求完美消除序列

    求完美消除序列在论文中有很多方法,在这里介绍最简单的一种。

    MCS算法:最大势算法。从n到1给节点编号,设\(label[i]\)为表示第\(i\)个点与多少个已标号点相邻,每次选择\(label[i]\)最大的未编号点进行编号。时间复杂度为\(O(n+m)\)

    判断一个序列是否是完美消除序列:设\(\{\}\)

转载于:https://www.cnblogs.com/shanxieng/p/9899141.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107215.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号