握手定理

4639 · 发表于 2009-8-7 20:39:35

8个吗？
会不会太简单了。。。。。
LZ发下答案吧

2957 · 发表于 2009-8-7 23:39:08

握手定理　　握手定理：有n个人握手，握手次数的总和S，必有S≤ 2(n+1)。
　　顶点的度数与握手定理
　　--------------------------------------------------------------------------------
　　1．顶点的度数
　　定义14.4 设G=<V，E>为一无向图，v∈V，称v作为边的端点次数之和为v的度数，简称为度，记做 dG(v)，在不发生混淆时，简记为d(v).设D=<V，E>为有向图，v∈V，称v作为边的始点次数之和为v的出度，记做(v)，简记作d+(v).称v作为边的终点次数之和为v的入度，记做(v)，简记作d-(v)，称d+(v)+d-(v)为v的度数，记做d(v).
　　--------------------------------------------------------------------------------
　　2．握手定理
　　定理14.1(握手定理) 设G=<V,E>为任意无向图，V={v1,v2,…,vn}，|E|=m，则
　　　　　　　　=2m
　　证 G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然，m条边，共提供2m度。
　　定理14.2(握手定理) 设D=<V,E>为任意有向图，V={v1,v2,…,vn}，|E|=m，则
　　　　　　　　=2m，且==m.
　　　　本定理的证明类似于定理14.1
　　握手定理的推论任何图(无向的或有向的)中，奇度顶点的个数是偶数。
　　证设G=<V，E>为任意一图，令
　　　　　　　　V1={v|v∈V∧d(v)为奇数}
　　　　　　　　V2={v|v∈V∧d(v)为偶数}
　　则V1∪V2=V，V1∩V2=，由握手定理可知
　　　　　　　　2m==+
　　由于2m，均为偶数，所以为偶数，但因V1中顶点数为奇数，所以|V1|必为偶数。
　　握手定理也称为图论的基本定理，图中顶点的度数是图论中最为基本的概念之一。

4897 · 发表于 2009-8-7 23:41:08

这个是百度百科的解释。
大概看了一下，看不懂

4900 · 发表于 2009-8-8 06:06:13

不会啊。。。。。。。。。。。

阿聖メ龍漢華民于 2009-8-8 06:06 对帖子补充以下内容

不会啊。。。。。。。。。。。

阿聖メ龍漢華民于 2009-8-8 06:06 对帖子补充以下内容

提示一下啊。。。。

4322 · 发表于 2009-8-12 14:41:17

13# tianbenwuya

它用的是图论的解释方法，你要是搞明白什么是无向图，什么叫度，就明白这个意思了。

4322 · 发表于 2009-8-12 15:07:45

每两个人只能握一次手，且不能与自己握，也不能与自己的伴侣握，所以，每个人的握手数应该是小于等8。
此时题里说，客人们的握手数不一样，所以，他们的握手数应该是从1到8都有，这里就得到了客人们各自握手数了，然后，再用图论画一个无向图来分析。
假设的无向图我也画出来了，但因为没有提男女主人的握手数是否相同，所以，我没有得到最后的结果，还希望LZ把条件给全。

4322 · 发表于 2009-8-12 15:10:06

8# 侦铭の印

但此题不能完全用这个公式，因为夫妻间是不会握手的。

4551 · 发表于 2009-8-13 12:17:34

我们应该把最复杂的问题用最简单的语言说出来而不是把最简单的问题用最复杂的语言说出来 1个人和8个人握手难到会搞出个9个人 10个人出来吗

2992 · 发表于 2009-8-13 14:27:07

为什么次数会不一样啊？？？

[逻辑推理] 握手定理