查看: 2561|回复: 8

请教图论题，求大神帮助！ [复制链接]

Light

红魔

Rank: 4

积分: 1041
帖子: 559
精华: 4
UID: 1241121
性别: 男

电梯直达

1^#

发表于 2012-7-4 19:53:43 |只看该作者 |正序浏览

本帖最后由 Light 于 2012-7-4 20:22 编辑

证明：一个有2n个顶点和n^2+1个边的图至少有一个K3子图？

然后证明一个有2n个顶点和n^2+1个边的图至少有n个K3子图

谢谢！

K3是complete graph，就是3个点，有3条线使他们两两相连
其实貌似如果能看懂，不用非得学过图论

收藏0

Why...so...seriouS!!!

使用道具举报

PKUSMSBQ

蓝魔

Rank: 2

积分: 206
帖子: 176
精华: 0
UID: 1257377
性别: 女

9^#

发表于 2012-7-5 10:49:16 来自手机 |只看该作者

果然是用归纳法的

使用道具举报

只会十贰板

红魔

Rank: 4

积分: 1108
帖子: 1018
精华: 0
UID: 1305059
性别: 男
居住地: 太原市
WCA ID: 2011WANG19
兴趣爱好: 速度

8^#

发表于 2012-7-5 08:45:57 |只看该作者

仔细琢磨了下。没看懂。。。我悲剧了

PB/5/12/50/100 mm 1.48/1.65/1.66/1.73/1.79
PB/5/12/50/100 clock 8.63/10.32/11.09/11.83/12.24

使用道具举报

则卷同学

粉魔

则卷N囧

Rank: 5 Rank: 5

积分: 3660
帖子: 1972
精华: 1
UID: 85309

7^#

发表于 2012-7-5 01:52:00 |只看该作者

我能说我是把题目看成数论然后兴高采烈的进来的么...

计划十一去嘉定旅游~（百分之九十九的人呢会想错地方）

使用道具举报

Light

红魔

Rank: 4

积分: 1041
帖子: 559
精华: 4
UID: 1241121
性别: 男

6^#

发表于 2012-7-4 21:18:24 |只看该作者

chuchudengren 发表于 2012-7-4 20:39
第一个就是托兰定理的特例,一般图论书应该都该有这个定理的.第二个记得用归纳法证过,具体证法我再想想

E ...

非常感谢！魔方吧上果然有大神！

Why...so...seriouS!!!

使用道具举报

Light

红魔

Rank: 4

积分: 1041
帖子: 559
精华: 4
UID: 1241121
性别: 男

5^#

发表于 2012-7-4 20:53:07 |只看该作者

chuchudengren 发表于 2012-7-4 20:39
第一个就是托兰定理的特例,一般图论书应该都该有这个定理的.第二个记得用归纳法证过,具体证法我再想想

恩，非常感谢！

Why...so...seriouS!!!

使用道具举报

chuchudengren

红魔

Rank: 4

积分: 2052
帖子: 1452
精华: 5
UID: 84402
性别: 男

4^#

发表于 2012-7-4 20:39:03 |只看该作者

本帖最后由 chuchudengren 于 2012-7-4 21:09 编辑

第一个就是托兰定理的特例,一般图论书应该都该有这个定理的.第二个记得用归纳法证过,具体证法我再想想

Edit从书上抄了个证明：
当n=2 时，显然成立；
设n<k时成立，当n=k时:
由第一条知存在K3, 设三顶点A,B,C的度分别为n1+2, n2+2, n3+2. 如果n1+n2+n3>=3k-4时,考虑含有A、B、C中至少两个点的K3个数，此时K3个数>=(n1+n2+n3)-(2k-3) +1>=k；当n1+n2+n3<=3k-5, n1+n2、n2+n2、n1+n3中必有一个小于等于2k-4, 不妨设为n1+n2, 这样移去这两个点以及与其相连的线,余下的图有归纳法假设知含有至少k-1个K3，因此原图含有至少k个K3
由归纳法知命题成立。

contact me by email: chutianxiang at gmail.com

使用道具举报