求助：用图论证明两问题 1握过奇数次手的人必有偶数个 2

zengrenjie · 发表于 2009-12-18 21:07

向各位请教啊！
如题请用图论证明：
1：在一次集会中，和别人握手次数为奇数的人数为偶数。
2：在由n个人构成的一个团体中，每个人恰好有3个朋友，证明n为偶数

先谢谢了！

zengrenjie · 发表于 2009-12-18 21:09

再加一句：证明过程详细清楚点哦

谢谢各位战友啊！

colinyouare · 发表于 2009-12-18 21:49

你这哪是啥考研的题啊？智力竞赛啊？
第一个，握手一次肯定是两个人各自握手次数+1，所以总的握手次数是偶数
第二个，同样的，每个人有3个朋友，朋友也是相互的，所以总数目肯定得是偶数，而3是奇数

genivs007 · 发表于 2009-12-19 08:26

这是集合论图论的题。

wangzmfalcon · 发表于 2009-12-19 09:06

总的握手次数一定是偶数因为一次握手时2个人每人一次
那握手偶次数的人的总握手次数是偶数
偶数-偶数=偶数
所以奇次握手的人的总握手次数也是偶数
偶数/奇数=偶数

第二题
一共n个人每人3个总数为3n
但你是我的朋友我就是你的朋友所以是相互的也就是总次数是偶数个m
m=3n
所以偶数/3=偶数

zengrenjie · 发表于 2009-12-25 20:11

谢谢wangzmfalcon 、genivs007、colinyouare啊！
这两个题目得用图论证明的呢，是集合图论的内容，谢谢大家了！

		自动登录	找回密码
密码			注册

NEW最新资料推荐