帮忙做几道大学题

来源：百度知道 编辑：UC知道 时间：2024/05/10 19:15:09
已知树T(n,m)的节点n=16,那末m=

设简单图G所有节点的度数之和为18，则G一定有____条边

n 阶完全图Kn= (n,m)中m=________________________

1. 令N为自然数的集合，N上二元关系定义为当且仅当ni/nj=2m,
试证明为等价关系
试证明在任何图中度为奇数的结点的个数为偶数

1)m=n-1=15,(这个公式书上有)
2)∑deg(v)=2m,所以m=9
3)m=n(n-1)/2
4)证明:对于任意x∈N有,x/x=1=2^0(自反性)
对于任意x,y∈N,若x/y=2^m,则y/x=2^(-m)(对称性)
对于任意x,y,z∈N,若x/y=2^m,y/z=2^n,则有x/z=2^(m+n)(可传递性)
从而N上二元关系定义为当且仅当ni/nj=2m,为等价关系

证明:假设度为奇数的结点的个数为奇数,故这奇数个节点的度的和为奇数(奇数个奇数相加为奇数),而任意个偶数相加为偶数,故最后所有的节点的度相加为奇数,而由公式∑deg(v)=2m知所有的节点的度相加为偶数,二者矛盾.
从而原假设不成立,所以在任何图中度为奇数的结点的个数为偶数

说明:我此处用的公式定理都是书上的,如有不清楚的地方,请再仔细看一下课本

看课本