淮海工学院2011-2012-2离散数学期末复习题答案(1)

12、是个群，u∈G，定义G中的运算“?”为a?b=a*u*b，对任意a，b∈G， 求证：也是个群．

-1

证明：1）?a，b∈G，a?b=a*u*b∈G，运算是封闭的；

-1-1-1-1

2）?a，b，c∈G，（a?b）?c=（a*u*b）*u*c=a*u*（b*u*c）=a?（b?c），运算可结合；

-1

3）?a∈G，设E为?的单位元，则a?E=a*u*E=a，得E=u，存在么元u；

-1-1-1-1

4）?a∈G，a?x=a*u*x=E，x=u*a*u，则x?a=u*a*u*u*a=u=E，各元素都有逆元； 所以也是个群．

13、设图G=，|V|=n，|E|=m，k度顶点有nk个，且各顶点或是k度点或是k+1度点，证明：nk= (k+1)n -2m.

证明：由已知可知，G中k+1度顶点为n-nk个。再由欧拉握手定理可知

2m=

-1

?deg(v)=kn+(k+1)(n-n)=(k+1)n-n，n= (k+1)n -2m.

kkkkv?V14、设G=?V,E?是图，|V|=n，|E|=m，证明：?(G)≤

2m≤?(G) . nnn证明：根据最小度的定义，?v?V，deg(v)≥?(G)，所以，2m=?deg(v)≥???G?=n?(G)

i?1i?1即 n?(G) ≤2m，整理后得，?(G)≤

2m n另一方面，根据最大度的定义，?v?V，deg(v)≤?(G)，与前面推理类似的可得，2m≤n?(G) 整理后得，?(G)≥

2m2m，,所以， ?(G)≤≤?(G) . nn15、设图G有n个结点，n＋1条边，证明：G中至少有1个结点度数大于等于3. 证明：用反证法，设G=?V,E?，?v∈V，deg(v)≤2，

所有结点的度数之和2(n+1)小于2n。即2(n+1)≤2n，化简后，2≤0，矛盾， 所以，G中至少有1个结点度数大于等于3.