- 主题:早培下午数学图论题2
trick似乎在于n个城市的话没给点的度至少是n-5，n足够大就会出现四边形，不知道写下这个point能的几份
【 在 gscas 的大作中提到: 】
: 某国家有若干个城市，它们之间的航线满足：对于任意三个城市，都至少有一条航线连接其中的两个，对于任意四个城市，一定存在两个 ...
--
FROM 14.219.238.*
答案肯定比9大，9个点似乎可以构造出来，标好1-9放在一个圈上，距离小于等于2的pair都连上线似乎就OK？
【 在 iamwxy 的大作中提到: 】
: 我家说写了个7，到底是几啊，不会做- 来自 水 ...
--
FROM 15.164.94.*
说错了这个只能证明比8大...
我上面说的可以证明比13小，每个点的度至少是n-4
【 在 lonelycat 的大作中提到: 】
: 答案肯定比9大，9个点似乎可以构造出来，标好1-9放在一个圈上，距离小于等于2的pair都连上线似乎就OK？ ...
--
FROM 15.164.94.*
不知道，我这个构造并没有做到极致，比如你可以要求距离1，2还有别的比如4的pair都连接
【 在 albedo 的大作中提到: 】
: 答案应该就是8 ...
--
FROM 120.229.142.*
虽然我现在觉得答案应该比较小，但你的证明似乎太不严格，我能想出来的证明大概是考虑一个顶点的度，这个最少是5但是因为度的和是偶数所以一定一个顶点的度是6，然后这么弄下去，分几种情况，我懒得一个个验证就是了
【 在 albedo 的大作中提到: 】
: 先构造出两个独立三角，6个第三个独立三角就不行了，所以小于9个把两个独立三角连起来，连线中再各加一个点，8个 ...
--
FROM 120.229.142.*
感觉他就是反复用ramsey定理吧，不过这个题没啥意思了，因为一般广义的题这么做的了么，比如每四个点有一条线但是没有5个点两两连线。
感觉要是能想清楚我构造的8个点的例子也许有一般解
【 在 figo12 的大作中提到: 】
: 错的，你加的两个点和三角顶点无连线 ...
--
FROM 120.229.142.*
n=100也满足啊
【 在 figo12 的大作中提到: 】
: 哦，对我算错了我算的通用公式是c(n,2)<=c(n,4)N=8也满足不应该在6停 ...
--
FROM 120.229.142.*
其实我也没看懂这个 ...
【 在 kakapo7 的大作中提到: 】
: 为什么三个独立三角就不行了？没懂...&nbsp ...
--
FROM 120.229.142.*
OK，我想了个更简单的证明
首先n个城市每个点的度至少是n-4，不然要么一个三角形没边要么有4个点全连
9个的话就是度至少是5，但是因为度的和是偶数所以一定有一个顶点度至少是6，考虑这个顶点练的6个点，根据ramsey定理有么有个三角形全连这样就有4个点全连要么有全不连的三角形，矛盾，所以9不行，8的话可以用我前面给的构造，这个应该可以推广到一般情况
【 在 lonelycat 的大作中提到: 】
: 感觉他就是反复用ramsey定理吧，不过这个题没啥意思了，因为一般广义的题这么做的了么，比如每四个点有一条线但是没有5个 ...
--
FROM 120.229.142.*
你这个不算证明吧，只是证明了我在8个城市的构造思路在9行不通而已，这个我自己也发现了
【 在 albedo 的大作中提到: 】
: ...
--
FROM 120.229.142.*