极值图论基础

目录

一,普通子图禁图

二,Turan问题

三,Turan定理、Turan图

1,Turan定理

2,Turan图

四,以完全二部图为禁图的Turan问题

1,最大边数的上界

2,最大边数的下界

五,以偶圈为禁图的Turan问题

六,Ramsey问题

1,Ramsey定理

2,Ramsey问题


一,普通子图禁图

参考普通子图

普通子图禁图指的是,给出一些具体的图,描述某个图不以这些具体的图作为普通子图。

二,Turan问题

给出一个图集F,求以F为普通子图禁图的图的最大边数,以及取到最大值的图是什么?

即,一个图最多能有多少条边,使得不以F中的任意图为普通子图。

PS:我们只关心简单图,否则如果2个点之间连无穷条多重边,那就没意义了。

PS:取到最大值的图称为极图,如果有唯一的极图,我们就说满足条件的极图是什么,不需要赘述边数了。

三,Turan定理、Turan图

1,Turan定理

以完全图K(r+1)为禁图的极图是平衡完全r部图,且没有其他极图。

2,Turan图

n个点的平衡完全r部图也叫图兰图Tr,n,即把n个点平均分成r份得到的完全r部图。

所以也可以说以完全图K(r+1)为禁图的n个点的图,唯一的极图是图兰图Tr,n

比如,以完全图K4为禁图的8个点的图,唯一的极图是T3,8:

实际上,图兰图Tr,n的边数就是(p^2r+pr+n^2-n)/2-pn,其中p=n/r

比如T3,8,n=8,r=3,p=2,(p^2r+pr+n^2-n)/2-pn=(12+6+64-8)/2-16=21

四,以完全二部图为禁图的Turan问题

1,最大边数的上界

定理:对于任意s>=t>=2,存在常数C,对于任意n,以完全二部图Ks,t为禁图的图的边数不超过Cn^{2-1/t}

猜想:对于任意s>=t>=2,以完全二部图Ks,t为禁图的图的最大边数为\Theta (n^{2-1/t})

其中,θ是渐进相等的符号。

2,最大边数的下界

存在常数C,对于任意t>=2,任意s>C^t,以完全二部图Ks,t为禁图的图的最大边数为\Theta (n^{2-1/t})

已经很接近上面的猜想了,但还没完全解决。

五,以偶圈为禁图的Turan问题

定理:对于任意k>=2,以2k个点构成的偶圈为禁图的图的边数不超过100k\cdot n^{1+1/k}

猜想:对于任意k>=2,以2k个点构成的偶圈为禁图的图的边数为\Theta(n^{1+1/k})

六,Ramsey问题

1,Ramsey定理

对于任意的s>1,t>1,一定存在一个整数N,对于任意N个点的图,要么存在s个点两两相连,要么存在t个点两两不相连。

我们把满足条件的最小N记做R(s,t)

2,Ramsey问题

Ramsey问题就是R(s,t)的大小和性质。

R(s,t)\leq \binom{s+t-2}{s-1}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/254729.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Vue3大事件项目(ing)

文章目录 核心内容1.大事件项目介绍2.大事件项目创建3.Eslint配置代码风格4.配置代码检查工作流问题: pnpm lint是全量检查,耗时问题,历史问题 5.目录调整6.vue-router4 路由代码解析7.引入 Element Plus 组件库8.Pinia 构建仓库 和 持久化9.Pinia 仓库统一管理 核心内容 Vue3…

【C/C++ 10】扫雷小游戏

一、题目 写一个扫雷小游戏,每次输入一个坐标,若该处是地雷,则游戏失败,若该处不是地雷,则显示周围地雷数量,若扫除全部非地雷区域,则扫雷成功。 二、算法 设置两张地图(二维数组&…

04-Java建造者模式 ( Builder Pattern )

建造者模式 摘要实现范例 建造者模式(Builder Pattern)使用多个简单的对象一步一步构建成一个复杂的对象 一个Builder 类会一步一步构造最终的对象,该 Builder 类是独立于其他对象的 建造者模式属于创建型模式,它提供了一种创建对…

【Java八股面试系列】并发编程-并发关键字,线程池

目录 并发关键字 Synchronized synchronized最主要的三种使用方式: 具体使用:双重校验锁单例模式 synchronized 底层实现原理? synchronized锁的优化 偏向锁 轻量级锁 重量级锁 Mark Word 与 Monitor 之间的关系 总结 偏向锁、轻量…

Aethir和Well-Link Tech携手革新云游戏,释放人工智能(AI)潜力

​Aethir将为Well-Link Tech的2亿用户提供先进的GPU计算能力,大幅提升他们的游戏体验。 新加坡,2024年2月7日 - 先驱性的去中心化GPU网络Aethir与实时云渲染技术领导者Well-Link Tech携手共创云游戏和元宇宙发展的新时代。 借助Well-Link Tech对领先游戏…

2024年第一篇博客

这是2024年的第一篇博客,2023年笔者经历了一连串的生活、工作、学习上的转折和调整,跌跌撞撞时光飞逝,转眼间就踏着元旦的钟声步入了2024年,前思后想、辗转反侧、犹豫再三不知道从哪里开始博客新的篇章,这个问题坦诚说…

.NET高级面试指南专题六【线程安全】5种方法解决线程安全问题

前言 多线程编程相对于单线程会出现一个特有的问题,就是线程安全的问题。所谓的线程安全,就是如果你的代码所在的进程中有多个线程在同时运行,而这些线程可能会同时运行这段代码。如果每次运行结果和单线程运行的结果是一样的,而且…

ElementUI Data:Table 表格

ElementUI安装与使用指南 Table 表格 点击下载learnelementuispringboot项目源码 效果图 el-table.vue&#xff08;Table表格&#xff09;页面效果图 项目里el-table.vue代码 <script> export default {name: el_table,data() {return {tableData: …

ubuntu22.04@laptop OpenCV Get Started: 000_hello_opencv

ubuntu22.04laptop OpenCV Get Started: 000_hello_opencv 1. 源由2. Hello OpenCV2.1 C应用Demo2.2 Python应用Demo 3. 参考资料 1. 源由 之前&#xff0c;通过敲门砖已经砸开了OpenCV的大门&#xff0c;接下来是体验下“Hello World&#xff01;”程序。 2. Hello OpenCV …

【01】判断素数/质数(C语言)

目录 &#xff08;1&#xff09;素数特点&#xff1a;只能被1和本身整除 &#xff08;2&#xff09;代码如下&#xff1a; &#xff08;3&#xff09;运行结果如下 ​编辑 &#xff08;4&#xff09;函数引申 &#xff08;1&#xff09;素数特点&#xff1a;只能被1和本身…

每日五道java面试题之java基础篇(四)

第一题. 访问修饰符 public、private、protected、以及不写&#xff08;默认&#xff09;时的区别&#xff1f; Java 中&#xff0c;可以使⽤访问控制符来保护对类、变量、⽅法和构造⽅法的访问。Java ⽀持 4 种不同的访问权限。 default (即默认&#xff0c;什么也不写&…

5-3、S曲线生成器【51单片机+L298N步进电机系列教程】

↑↑↑点击上方【目录】&#xff0c;查看本系列全部文章 摘要&#xff1a;本节介绍步进电机S曲线生成器的计算以及使用 一.计算原理 根据上一节内容&#xff0c;已经计算了一条任意S曲线的函数。在步进电机S曲线加减速的控制中&#xff0c;需要的S曲线如图1所示&#xff0c;横…

containerd中文翻译系列(十九)cri插件

cri插件包含的内容比较多&#xff0c;阅读之前请深呼吸三次、三次、三次。 CRI 插件的架构 本小节介绍了 containerd 的 cri 插件的架构。 该插件是 Kubernetes 容器运行时接口&#xff08;CRI&#xff09; 的实现。Containerd与Kubelet在同一个节点上运行。containerd内部的…

【Rust日报】2024-02-08 Loungy:使用 Rust 和 GPUI 开发的 MacOS 启动器

Mira Screenshare&#xff1a;基于 Rust 和 WebRTC 的高性能屏幕分享工具 一群大学生宣布推出了他们的期末项目&#xff1a;Mira Screenshare&#xff0c;一个开源、高性能的屏幕共享工具&#xff0c;由 Rust 和 WebRTC 构建。此项目支持 4k 60 FPS 和 110ms 端到端延迟的屏幕…

pycharm deployment 灰色 一直无法点击

我的development的配置如下&#xff0c;我看了很多教程一直不知道为什么一直是灰色的&#xff0c; 文件夹配置&#xff1a; 如果你这里 Autodect&#xff0c;那么你Mapping 的文件夹应该是应该省略这个前缀的&#xff0c;例如我下面&#xff0c;我应该将本地文件夹映射到/home…

深度学习入门笔记(九)自编码器

自编码器是一个无监督的应用&#xff0c;它使用反向传播来更新参数&#xff0c;它最终的目标是让输出等于输入。数学上的表达为&#xff0c;f(x) x&#xff0c;f 为自编码器&#xff0c;x 为输入数据。 自编码器会先将输入数据压缩到一个较低维度的特征&#xff0c;然后利用这…

天猫平台数据查询(天猫数据分析):床上用品市场规模达335亿,床品消费呈现功能化趋势

作为人们的生活必需品之一&#xff0c;床上用品的市场规模庞大。近年来&#xff0c;越来越多消费者购物习惯发生转变&#xff0c;线上客流大幅提升&#xff0c;面对这一变化&#xff0c;许多家纺企业开始借助线上平台开展销售&#xff0c;不断创新营销模式&#xff0c;通过短视…

【大厂AI课学习笔记】【1.5 AI技术领域】(8)文本分类

8,9,10&#xff0c;将分别讨论自然语言处理领域的3个重要场景。 自然语言处理&#xff0c;Natual Language Processing&#xff0c;NLP&#xff0c;包括自然语言识别和自然语言生成。 用途是从非结构化的文本数据中&#xff0c;发掘洞见&#xff0c;并访问这些信息&#xff0…

[职场] 抖音运营SOP全攻略 #微信#职场发展

抖音运营SOP全攻略 1.养号的步骤 注册一机—卡一号&#xff0c;在注册的前5天只看视频不发视频&#xff0c;单日观看视频的时长不少于30分钟。观看过程中正常评论点赞互动&#xff0c;关注5-10个头部大号。关注20个二三十万至百万的竟品账号。 粉丝量低于1W的账号下不要留下…

树与二叉树---数据结构

树作为一种逻辑结构&#xff0c;同时也是一种分层结构&#xff0c;具有以下两个特点&#xff1a; 1&#xff09;树的根结点没有前驱&#xff0c;除根结点外的所有结点有 且只有一个前驱。 2&#xff09;树中所有结点可以有零个或多个后继。 树结点数据结构 满二叉树和完全二…