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

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

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

弦图与区间图


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


  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)


相关推荐

  • contentWindow,[通俗易懂]

    contentWindow,[通俗易懂]a>contentWindow兼容各个浏览器,可取得子窗口的window对象。b>contentDocumentFirefox支持,>ie8的ie支持。可取得子窗口的

  • .NET(c#) 移动APP开发平台 – Smobiler(1)

    .NET(c#) 移动APP开发平台 – Smobiler(1)如果说基于.net的移动开发平台,目前比较流行的可能是xamarin了,不过除了这个,还有一个比xamarin更好用的国内的.net移动开发平台,smobiler,不用学习另外一套开发模式或者搭建复杂的开发环境,smobiler能够让大家像开发传统windows一样去开发移动应用,那么列举一下这个平台的特点。1. 基于VisualStudio的可视化开发。如同开发传统Windows平台一样的…

  • 轻松搞懂【TF-IDF、word2vec、svm、cnn、textcnn、bilstm、cnn+bilstm、bilstm+attention实现】英文长文本分类[通俗易懂]

    轻松搞懂【TF-IDF、word2vec、svm、cnn、textcnn、bilstm、cnn+bilstm、bilstm+attention实现】英文长文本分类[通俗易懂]项目来源:https://www.kaggle.com/c/word2vec-nlp-tutorial/之前我写过几篇博客:就这?word2vec+BiLSTM、TextCNN、CNN+BiLSTM、BiLSTM+Attention实现中英文情感分类代码详解就这?word2vec+SVM(支持向量机)实现中英文情感分类代码详解这两篇博客主要是基于中文进行情感分类的,那么本篇博客,我会以这个kaggle项目来介绍如何实现英文长文本情感分类。1实验数据本次数据集来源于kaggle项目“Bago

  • PHP集成环境 Xampp,PHPwamp等等国内外著名的集成环境[通俗易懂]

    PHP集成环境 Xampp,PHPwamp等等国内外著名的集成环境[通俗易懂]原文:http://www.toutiao.com/i6378285337512247809/?tt_from=mobile_qq&utm_campaign=client_share&app=news_article&utm_source=mobile_qq&iid=7663221178&utm_medium=toutiao_android在本地测试网站,有个集成环境直接测试还

  • Navicat 15 for mysql 永久激活码_通用破解码

    Navicat 15 for mysql 永久激活码_通用破解码,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 以《简单易懂》的语言带你搞懂逻辑回归算法【附Python代码详解】机器学习系列之逻辑回归篇

    以《简单易懂》的语言带你搞懂逻辑回归算法【附Python代码详解】机器学习系列之逻辑回归篇目录必看前言逻辑回归算法1概述2基本原理3sklearn实现3.1导入数据(乳腺癌数据集)3.2建模3.3绘制学习曲线3.4网格搜索-确定最优参数结束语必看前言这一篇文章,我会详细从机器学习的角度介绍逻辑回归,以及如何利用Python来实现逻辑回归以及逻辑回归的实战模拟,另外我也会教大家如何利用网格搜索找到最优参数。干货满满!逻辑回归算法1概述分类技术是机器学习和数据挖掘应用中的重要组成部分。在数据科学中,绝大多数的问题属于分类问题。解决分类的算法也有很多种。如:KNN,使距

发表回复

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

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