一道离散数学题

设 n 阶无向树 G = <V , E> 中有 m 条边，证明：m = n - 1

推荐答案 2018-02-24

对n使用数学归纳法。当n=1时结论显然成立。假设n>=2且n-1阶无向树恰有n-2条边。
首先，对于n>=2阶无向树G，每个节点的度数均>=1，由于G中不含有圈，由定理*知必存在一个节点v，其度数为1.
考虑G-{v},由于G是不含圈的连通图且deg(v)=1，所以G-{v}是不含圈的连通图，即G-{v}是n-1阶无向树，他恰有n-2条边。因此G恰有n-1条边。
定理*：在无向图G=（V，E）中，若任意v属于V，有deg（v）>=2，则G中存在圈。
参考资料：邓辉文《离散数学（第三版）》P119.

温馨提示：答案为网友推荐，仅供参考

当前网址：http://www.wendadaohang.com/zd/AW3nAKWKW15GnK4GKn5.html

相似回答

离散数学的一道题求解答答：六、①a*b=(a-5)(b-5)+5,任a,b≠5,则a*b≠5 ②(a*b)*c=[ab-5(a+b)+30]*c =[ab-5(a+b)+30]c-5[ab-5(a+b)+30+c]+30 =abc-5(ab+bc+ca)+25(a+b+c)-120,同理a*(b*c)=a*[bc-5(b+c)+30]=a[bc-5(b+c)+30]-5[a+bc-5(b+c)+30]+30 =abc...

一道离散数学题,求过程,谢谢,1.4-5谢谢了答：((P∧Q)∨¬R)→P ⇔¬((P∧Q)∨¬R)∨P 变成交并 ⇔P∨¬((P∧Q)∨¬R) 交换律排序 ⇔P∨(¬(P∧Q)∧R) 德摩根定律 ⇔P∨((¬P∨¬Q)∧R) 德摩根定律 ⇔P∨(¬P∧R)∨(¬Q∧R...

一道离散数学题答：解答：1)令A(-x,0);D(0,x)1/2*x*(x-1)=3 x=-2(舍去),x=3 A(-3,0),D(0,3)把ABD分别代入二次函数表达式:{9a-3b+c=0 {a+b+c=0 {c=3 解得:a=-1,b=-2,c=3 y=-x2-2x+3 2)y=-(x+1)2+4 M(-1,4)令M'(1,4);AM'方程为y=ax+b;代入A,M'{-3a+b=...

一道离散数学题目 帮我解答下采纳后另加分不好书写的话请截图需要过...答：4，求能同时被2，3整除的个数：500/6=83余2，有82个 5，求能同时被2，7整除的个数：500/14=35余10，有35个 6，求能同时被3，7整除的个数：500/21=23余17，有23个 7，求能同时被2.3.7整除的个数：500/42=11余38，有10个那么：能整除的个数为：250+166+71-82-35-23+10=...

一道离散数学题~~答：=[¬(p Λ q) V r] Λ [¬(¬p Λ ¬q) V r]=[(¬p V ¬q V r] Λ [(p V q V r]=M6 Λ M0 这个就是主合取范式 =m1 V m2 V m3 V m4 V m5 V m7 根据范式互补规律，这个就是主析取范式主析取范式也可以硬性推算，比较麻烦 (p←→...

求一道离散数学推理题推理过程:A、B、C三人去餐馆吃饭,他们每人要的...答：假设 a：火腿 b:猪排由1推出 c:火腿由3推出与2违背所以a不可能火腿 a：猪排由2推出 c：火腿所以只有b有可能

一道相当有意思的离散数学题!求解!谢各位大神!答：首先符号化爱吃素的人：P 爱是荤的人：﹁P (由题意知道爱吃荤的人就是不爱吃素的人)爱吃豆皮的人：Q 不爱吃豆皮的人：﹁Q 爱吃素的人都爱吃豆皮：(P→Q)∧(Q→P)吃荤的不爱吃豆皮：(﹁P→﹁Q)∧(﹁Q→﹁P)那么就是由前提：(P→Q)∧(Q→P) 得出结论：(﹁P→﹁Q)∧(﹁...

一道离散数学证明题答：（1）由b=a*a与半群的结合性,a*b=a*(a*a)=(a*a)*a=b*a (2)因为a*b属于｛a,b｝，故a*b=a或a*b=b，如果a*b=a，则由b=a*a得 b*b=(a*a)*b=a*(a*b)=a*a=b 如果a*b=b，则由b=a*a得 b*b=(a*a)*b=a*(a*b)=a*b=b 无论哪种情况均有b*b=b。

一道离散数学题答：其度数为1.考虑G-{v},由于G是不含圈的连通图且deg(v)=1，所以G-{v}是不含圈的连通图，即G-{v}是n-1阶无向树，他恰有n-2条边。因此G恰有n-1条边。定理*：在无向图G=（V，E）中，若任意v属于V，有deg（v）>=2，则G中存在圈。参考资料：邓辉文《离散数学（第三版）》P119.

大家正在搜

离散数学计算题题库离散数学选择题题库离散数学大题离散数学应用题离散数学试题及解答离散数学题库及答案离散数学综合题答案离散数学题型离散数学常考题