甘肃建设体网站,北京公司名称大全集,科院公司网站建设目标是什么,建视频网站系统目录
一#xff0c;普通子图禁图
二#xff0c;Turan问题
三#xff0c;Turan定理、Turan图
1#xff0c;Turan定理
2#xff0c;Turan图
四#xff0c;以完全二部图为禁图的Turan问题
1#xff0c;最大边数的上界
2#xff0c;最大边数的下界
五#xff0c;…目录
一普通子图禁图
二Turan问题
三Turan定理、Turan图
1Turan定理
2Turan图
四以完全二部图为禁图的Turan问题
1最大边数的上界
2最大边数的下界
五以偶圈为禁图的Turan问题
六Ramsey问题
1Ramsey定理
2Ramsey问题 一普通子图禁图
参考普通子图
普通子图禁图指的是给出一些具体的图描述某个图不以这些具体的图作为普通子图。 二Turan问题
给出一个图集F求以F为普通子图禁图的图的最大边数以及取到最大值的图是什么
即一个图最多能有多少条边使得不以F中的任意图为普通子图。
PS我们只关心简单图否则如果2个点之间连无穷条多重边那就没意义了。
PS取到最大值的图称为极图如果有唯一的极图我们就说满足条件的极图是什么不需要赘述边数了。 三Turan定理、Turan图
1Turan定理
以完全图K(r1)为禁图的极图是平衡完全r部图且没有其他极图。
2Turan图
n个点的平衡完全r部图也叫图兰图Tr,n即把n个点平均分成r份得到的完全r部图。
所以也可以说以完全图K(r1)为禁图的n个点的图唯一的极图是图兰图Tr,n。
比如以完全图K4为禁图的8个点的图唯一的极图是T3,8 实际上图兰图Tr,n的边数就是其中pn/r
比如T3,8n8,r3,p2, 四以完全二部图为禁图的Turan问题
1最大边数的上界
定理对于任意st2存在常数C对于任意n以完全二部图Ks,t为禁图的图的边数不超过
猜想对于任意st2以完全二部图Ks,t为禁图的图的最大边数为
其中θ是渐进相等的符号。
2最大边数的下界
存在常数C对于任意t2任意sC^t以完全二部图Ks,t为禁图的图的最大边数为
已经很接近上面的猜想了但还没完全解决。 五以偶圈为禁图的Turan问题
定理对于任意k2以2k个点构成的偶圈为禁图的图的边数不超过
猜想对于任意k2以2k个点构成的偶圈为禁图的图的边数为 六Ramsey问题
1Ramsey定理
对于任意的s1,t1一定存在一个整数N对于任意N个点的图要么存在s个点两两相连要么存在t个点两两不相连。
我们把满足条件的最小N记做R(s,t)
2Ramsey问题
Ramsey问题就是R(s,t)的大小和性质。
