相识问题一例，欢迎帮助
我们这有一个问题：9个人中一定有3个人互相认识或者有4个人互相不认识。要证明这个问题，百思不得其解，希望高手指点。据了解用图论的相关只是可以解决，请求帮助 抽屉原理 大概是这样吧：用9个点表示9个人，互相认识的连一条边。
含9个点的完全图有36条边，若“有4个人互相不认识”不成立，则此图至少有x条边。当一个含9个点的图有x条边时，它一定有一个只含3个点的圈。
由于图论都忘得差不多了，不知道上述思路是否正确，好象有点多余。 感谢你对相识问题的回复，那么你可以具体点讲吗，想不出来啊
谢谢帮忙！ 你可以把9个人在图上表示为9个点，用红线和蓝线连接任意两个点分别表示两人相识或不识。然后你就会发现你所要的答案。
这个问题在初中的竞赛中就有，不过对于没有见过的人来说还是比较麻烦的。
问题好像不是那么解决的，我们当然可以看出那个结论，
可问题是，我们怎么才能证明，你作图只是若干种情况，怎么才能覆盖全呢？
麻烦了，具体说明具体说明
knigh 说的就是原理，我只是形象的说明。这个问题原先我见过的是很多人通信（比如现在可以用2004个人通信），你想想如何用抽屉原理来选择线段和点就行了。 你的相识包不包括 A认识B而B不认识A 的情况啊 建议看一下清华出版的<<组合数学>>,好象有个类似的例题,讲的够详细,明白. 还没搞定？
首先，相识不包括“A认识B而B不认识A”的情况。
然后，用图表示这9人的关系——认识的连一条边，构造图G=(V,E)。
现在证明此图中或含完全图K3，或含4阶零图N4。
对于任意V中一点x，……
还是找一本组合数学的书看看，其中的Ramsey定理。
http://www.shumo.org/bbs/dispbbs.asp?boardID=108&ID=4025&star=4
[此贴子已经被作者于2004-4-21 6:27:37编辑过]
页:
[1]
2