第十章-树

第十章树10.1画出所有不同构的，有5个顶点的树。解图10.1习题1图10.2证明：一棵树的顶点度数之和为)1|(|2V，其中V是顶点集。证明一棵树的所有顶点的度数之和||1||2)deg(ViiEv，因为树的1||||VE，所以)1|(|2||2)deg(||1VEvVii。故一棵树的顶点度数之和为)1|(|2V。10.3一棵树有3个2度顶点，5个3度顶点，8个4度顶点，问有几个一度顶点？解设树T有n个一度顶点，则)deg(v=)1853(21483523nn，从而有23n。即该棵树有23个一度顶点。10.4一棵树2n个顶点的度数为2，3n个顶点的度数为3，…，kn个顶点度数为k，问有几个顶点度数为1个顶点。解设有1n个度数为1的顶点。顶点数knnnv...21，边数1)...(121knnnve。由握手定理知：niivve1)deg()1(22，故knnnnnnkk...212)...(22121，因此，2)2(...2431knknnn10.5证明：一棵树若有三片树叶，则至少有一个顶点度数大于等于3。证明反证法。设),(EVT且没有一个顶点度数大于等于3，则对于Vv，有2)deg(v，从而有：)3|(|23)deg(Vv||21||21)1|(|2EEV与握手定理矛盾。故至少有一个顶点度数大于等于3。10.6),(EVT是一棵树，证明：若T仅有两个1度顶点，则T是一条直线。证明假设T不是一条直线，因为T仅有两个1度顶点，所以树中至少存在一个顶点，其度数3。从而有：)3|(|2312)deg(Vv1)1|(|2V1||2E||2E与握手定理矛盾。故T是一条直线。10.7证明：正整数序列),,,(21nddd是一棵树的度序列当且仅当)1(221ndddn。证明（1）由握手定理知，必要性显然成立（2）充分性对顶点数进行归纳证明。当2n时，2)12(221dd，则121dd，故以21,dd为度数的树存在，即为一条边。设任意1n个正整数121,...,,nddd，只要2)1(211ndnii，则存在一棵顶点度数序列121,...,,nddd的树。对n个正整数',...,','21nddd，有)1(2'1ndnii，则',...,','21nddd中必有一个数为1，必有一个数大于等于2。不妨设2',1'1ndd，因此，对1n个正整数1',...,','32nddd，有)1)1((2)1'('12nddnnii，则存在一棵顶点度数为1',',...,','132nndddd的树'T，其顶点序列为nvvv,,,32。在'T中增加一个顶点1v，且增加边),(1nvv，得到T，则T为树，且T的顶点度数为',...,','21nddd。由数学归纳法知，原命题成立。10.8证明一棵树又是二部图(偶图)。),(EVT,1V，2V是T作为二部图的顶点分类，12||||VV则1V中至少有一片树叶。证明因为T是一棵树，所以T中没有回路，也可以说T中回路的长度都为0（0为偶数），从而由二部图的充要条件知，T是二部图。设1V中没有树叶，则1V中每个顶点的度数2。由于T是二部图，则有：||22||22)1|(|22)1|||(|2||2||2||22121EEVVVVVE与握手定理矛盾。故1V中至少有一片树叶。10.9),(EVT是简单无向图。T是一棵树当且仅当T中任意两点仅有唯一的简单通路。证明（1）必要性T是一棵树，设T中某两点间至少存在两条简单通路。根据简单通路的定义知，T中必然存在圈，这与T是一棵树矛盾，所以T中任意两点仅有唯一的简单通路。（2）充分性因为T中任意二点均有唯一的简单通路，所以T连通的。假设T中存在圈，不妨设为),,,,,(0110iiiiivvvvvkk，则0iv和kiv两点间存在两条简单通路：),(00iivv和),,,,(110kkiiiivvvv。这与T中任意两点仅有唯一的简单通路矛盾,所以T中不存在圈，故T是一棵树。综上所述，T是一棵树当且仅当T中任意两点仅有唯一的简单通路。10.10求下面图的最小生成树。2534376453976843图10.2习题10图解最小生成树如图10.3中黑边所示：最小生成树的权为32554433332。2534376453976843图10.3习题10的答图10.11G是一个连通图，)(EVG，，vV，1)deg(v,eE是关联顶点v的一条边。证明e一定是任何一棵生成树的枝。证明假设e不是某一棵生成树的枝，则e一定是弦。根据弦的定义，e一定对应于一个圈。则e关联顶点v的度数至少为2。这与1)deg(v矛盾，所以e一定是任何一棵生成树的枝。10.12试证明简单连通图G的任一条边都可以是某一生成树的枝。证明设e为简单连通图G的任一条边。（1）若G中没有回路包含e，则G的任何生成树都包含e。因为不含e的任何G的子图不连通，因而不可能是生成树。又因为G连通，所以任一棵生成树都包含e。（2）若G中有回路包含e，则在回路中去掉一条非e的边。若有多个回路包含e，则重复上述过程，直到没有回路包含e为止。这样得到的一个连通的生成子图'G，在'G中没有回路包含e，由（a）知'G至少有一棵生成树，并且包含e。而'G的任何生成树均为G的生成树，所以G有生成树包含e。10.13证明任何生成树的补不包含割。证明设生成树的补包含割，则删除该割集，生成树仍然存在，即图仍然连通，这与割集的定义矛盾。故任何生成树的补不包含割。10.14证明一个割集的补不含生成树。证明设割集的补含有生成树，则删除割集后，生成树仍然在图中，也即图仍连通，与割集的定义矛盾。故一个割集的补不含生成树。10.15证明一棵正则2－分树必有奇数个顶点。证明假设一棵正则2－分树有i个分枝点，每个分枝点有2个儿子，故总的儿子数目为i2。而所有的儿子包括全部顶点减去一个根，即为分枝点数目i与树叶数目t之和,再减去1，所以有：12tii即有：1ti从而全部顶点数目为：12)1(tttti显然,它是一个奇数。故一棵正则2－分树必有奇数个顶点。10.16给定权为1，4，9，16，25，36，49，64，81，100。（1）构造一棵带权最优2-分树(二叉树)；（2）构造一棵带权最优3-分树(三叉树)；解（1）最优2-分树(二叉树)如图10.4(a)所示。（2）最优3-分树(三叉树)如图10.4(b)所示。385219119641001668185493625553016149541385100911943050149162536496481(a)(b)图10.6习题16图10.17画一棵带权为3，5，5，7，9，11，13，14的最优2－分树。解最优二分树如图10.7所示：672740131417238123557911图10.7习题17答图