当前位置: 首页 > news >正文

做一些好玩的个人网站新闻最新消息10条

做一些好玩的个人网站,新闻最新消息10条,网站图片优化,凡客做网站目录 一,普通子图禁图 二,Turan问题 三,Turan定理、Turan图 1,Turan定理 2,Turan图 四,以完全二部图为禁图的Turan问题 1,最大边数的上界 2,最大边数的下界 五,…

目录

一,普通子图禁图

二,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.yidumall.com/news/33781.html

相关文章:

  • 做的很漂亮的网站梅州网络推广
  • 北京网站被处罚今日热榜官网
  • 网站规划设计流程百度竞价个人开户
  • 小精灵网站在线做语文seo营销怎么做
  • 新媒体营销的概念seo平台优化服务
  • 网站开发结束语网站开发合同
  • 曲靖做网站建设的公司市场调研报告ppt
  • intitle 做网站百度识图网站
  • 好看的移动端网站百度快速排名工具
  • 快手做任务网站百度推广seo自学
  • 移动端网站提交提交百度竞价推广后台
  • 公关策划公司网站源码网页设计软件有哪些
  • 电子商务网站的建设流程是怎样的品牌推广和品牌营销
  • 官方网站建设合同百度一下官网首页登录
  • 重庆网站建设公司下载重庆百度seo
  • unity游戏制作软件百度刷seo关键词排名
  • wap网站 视频教程怎么建立企业网站
  • 网站流量少怎么办国际新闻稿件
  • java做网站如何验收手机系统优化
  • 旅行社做境外购物网站网络营销活动案例
  • 生意网官方网站网站推广的作用在哪里
  • 网站数据库怎么恢复seo搜索引擎优化费用
  • 太原做彩票网站公司厦门百度代理
  • wordpress 修改后台点击seo软件
  • 手机网站开发用什么优化网站推广网站
  • 深圳模板网站制作优帮云排名优化
  • 网站开发需要懂多少代码torrent种子搜索引擎
  • 郑州网站开发douyanet进入百度官网首页
  • 企业宣传片影视制作太原seo顾问
  • 新疆建设兵团门户网站南宁seo公司