求助：相识问题

liuye216 · 发表于 2004-3-25 06:05:10

6个人的集会上，假定认识和不认识都是相互的，则总能找到或者3个人都认识或者3个人都谁也不认识谁，问是否正确？
望高手拔刀相助，救小生一命

amao · 发表于 2004-3-25 18:37:22

正确
用6个点代表6个人，如果两人认识，则将他们所对应的点之间的连线染成蓝色，如果不认识，则染成红色，只要证明存在同色三角形即可。
相关资料，可以查“染色问题”

unique_18 · 发表于 2004-7-22 19:20:16

<

>呵呵,我们刚刚老师好象有讲,不过我没有听.</P><

>不过大概用图论的知识,最短路问题还是最大流问题,具体的忘记了.</P>

		自动登录	找回密码
密码			注-册-帐-号