早教吧作业答案频道 -->其他-->
设T是一个（n,m）无向图,若T无圈且m=n-1,证明T为树
题目详情
设T是一个（n,m）无向图,若T无圈且m=n-1,证明T为树
▼优质解答
答案和解析
设该图为G.只需要证明G是连通的.用反证法.
设G是不连通的,G含s个连通分图G1,G2,……Gs,(s>=2）.因每个Gi（i=1,2,……s)是连通的,并且不含圈,故每个Gi是树.设Gi有pi个点,则Gi有pi-1条边,于是
q(G)=q(G1)+q(G2)+……+q(Gs)=(p1-1)+(p2-1)+……+ps-1)=p(G)-s
设G是不连通的,G含s个连通分图G1,G2,……Gs,(s>=2）.因每个Gi（i=1,2,……s)是连通的,并且不含圈,故每个Gi是树.设Gi有pi个点,则Gi有pi-1条边,于是
q(G)=q(G1)+q(G2)+……+q(Gs)=(p1-1)+(p2-1)+……+ps-1)=p(G)-s
看了 设T是一个（n,m）无向图,...的网友还看了以下：
向量空间证明题怎么证明?设α1,α2...,αn和β1,β2,...βn是n维列向量空间R^n的两 2020-05-13 …
设a,m,n为自然数,a>1.证明若a^m+1|a^n+1,那么m|n设a,b,m,n为自然数,同 2020-05-16 …
已知函数f(x)=(lnx)/x的图像为曲线C,函数g(x)=1/2*a*x+b的图像为直线l.( 2020-06-04 …
一道高一水平的数学体,具体如下:函数y=f(x)定义在R上,当x>0时,f(x)>1,且对任意m, 2020-06-05 …
小明在实验室采用如图1所示装置探究“物体的加速度a与物体所受外力F、物体质量M间的关系”时，设小车 2020-06-29 …
不等式的证明设m,n为正整数,f(n)=1+1/2+1/3+.+1/n,证明(1)若n>m,则f( 2020-07-16 …
设f(x)在x=0的某个领域U(0,m)内有定义设f(x)在x=0的某个邻域U(0,m)内有定义, 2020-07-31 …
线数题怎么证明设η1,η2,η3,η4……ηS是非齐次线性方程组AX=b的S个解,证明x=k1η1+ 2020-11-02 …
设向量组α1,α2,...,αm线性无关,β1可由α1,α2,...,αm线性表示,但β2不可由α1 2020-11-03 …
线性代数特征向量问题求解1）设a是n阶矩阵A的特征向量,T是n阶可逆矩阵,B=T-1AT,求B的一个 2020-12-05 …