离散数学10 树

更新时间：2023-10-14 17:45:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

离散数学10小时突击网课推荐度：
相关推荐

1/6 第10章

第十章树

10.1画出所有不同构的，有5个顶点的树。

解

图10.1 习题1图

10.2 证明：一棵树的顶点度数之和为2(|V| ?1)，其中V是顶点集。

证明

一棵树的所有顶点的度数之和

?deg(v)?2|E|，因为树的|E|?|V|?1，所以

ii?1n?deg(v)?2|E|?2(|V|?1)。

ii?1n故一棵树的顶点度数之和为2(|V| ?1)。

10.3 一棵树有3个2度顶点，5个3度顶点，8个4度顶点，问有几个一度顶点？

解

设树T有n个一度顶点，则

?deg(v)=3?2?5?3?8?4?1?n?2(3?5?8?n?1)，

从而有n?23。

即该棵树有23个一度顶点。

10.4 一棵树n2个顶点的度数为2，n3个顶点的度数为3，…，nk个顶点度数为k，问有几个顶点度数为1个顶点。

解

设有n1个度数为

的顶点。顶点数v?n1?n2?..?.nk，边数

e?v?1?(n1?n2?..?.nk)?1。由握手定理知：

2e?2(v?1)??deg(vi)，故2(n1?n2?...?nk)?2?n1?1?n2?2?...?nk?k，

i?1n因此，n1?n3?2n4?...?(k?2)nk?2

10.5 证明：一棵树若有三片树叶，则至少有一个顶点度数大于等于3。

证明

2/6 第10章

eg(反证法。设T?(V,E)且没有一个顶点度数大于等于3，则对于?v?V，有d从而有：

v)?2，

?deg(v)?3?2(|V|?3)

?2(|V|?1)?1?2|E|

与握手定理矛盾。

故至少有一个顶点度数大于等于3。

10.6 T?(V,E)是一棵树，证明：若T仅有两个1度顶点，则T是一条直线。

证明

假设T不是一条直线，因为T仅有两个1度顶点，所以树中至少存在一个顶点，其度数?3。从而有：

?deg(v)?2?1?3?2(|V|?3)

?2(|V|?1)?1 ?2|E|?1 ?2|E| 与握手定理矛盾。故T是一条直线。

10.7 证明：正整数序列(d1,d2,?,dn)是一棵树的度序列当且仅当

d1?d2???dn?2(n?1)。

证明

（1）由握手定理知，必要性显然成立（2）充分性

对顶点数进行归纳证明。

当n?2时，d1?d2?2?(2?1)?2，则d1?d2?1，故以d1,d2为度数的树存在，即为一条边。

设任意n?1个正整数d1,d2,...,dn?1，只要序列d1,d2,...,dn?1的树。

对n个正整数d1',d2',...,dn'，有

?di?1n?1i?2(n?1)?2，则存在一棵顶点度数

?d'?2(n?1)，则d',din12',..,dn'中必有一个数为1，

i?1必有一个数大于等于2。不妨设d1'?1,dn'?2，因此，对n?1个正整数d2',d3',...,dn'?1，

3/6 第10章

有

?d'?(dii?2n?1n'?1)?2((n?1)?1)，则存在一棵顶点度数为d2',d3',...,dn?1',dn'?1的树T'，

其顶点序列为v2,v3,?,vn。在T'中增加一个顶点v1，且增加边(v1,vn)，得到T，则T为树，且T的顶点度数为d1',d2',...,dn'。

由数学归纳法知，原命题成立。

10.8证明一棵树又是二部图(偶图)。T?(V,E),V1，V2是T作为二部图的顶点分类，

|V1|?|V2|则V1中至少有一片树叶。

证明

因为T是一棵树，所以T中没有回路，也可以说T中回路的长度都为0（0为偶数），从而由二部图的充要条件知，T是二部图。

设V1中没有树叶，则V1中每个顶点的度数?2。由于T是二部图，则有：

2|E|?2|V1|?2|V2|?2(|V1|?|V2|?1)?2?2(|V|?1)?2?2|E|

与握手定理矛盾。故V1中至少有一片树叶。

10.9 T?(V,E)是简单无向图。T是一棵树当且仅当T中任意两点仅有唯一的简单通路。证明

（1）必要性

T是一棵树，设T中某两点间至少存在两条简单通路。根据简单通路的定义知，T中必然存在圈，这与T是一棵树矛盾，所以T中任意两点仅有唯一的简单通路。

（2）充分性

因为T中任意二点均有唯一的简单通路，所以T连通的。

假设T中存在圈，不妨设为(vi0,vi1,?,vik?1,vik,vi0)，则vi0和vik两点间存在两条简单通路：(vi0,vi0)和(vi0,vi1,?,vik?1,vik)。这与T中任意两点仅有唯一的简单通路矛盾, 所以T中不存在圈，故T是一棵树。

综上所述，T是一棵树当且仅当T中任意两点仅有唯一的简单通路。 10.10 求下面图的最小生成树。

4/6 第10章

2 5 4 7 3 9 3 4 6 5 7 3 8 6 4 3 图10.2 习题10图

解

最小生成树如图10.3中黑边所示：

最小生成树的权为2?3?3?3?3?4?4?5?5?32。

2 5 4 7 3 9 3 3 4 6 5 7 8 6 3 4 图10.3 习题10的答图

10.11 G是一个连通图，G?(V，E)，v?V，deg(v)?1,e?E是关联顶点v的一条边。证明e一定是任何一棵生成树的枝。

证明

假设e不是某一棵生成树的枝，则e一定是弦。根据弦的定义，e一定对应于一个圈。则e关联顶点v的度数至少为2。这与deg(v)?1矛盾，所以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 证明任何生成树的补不包含割。

证明

''''5/6 第10章

设生成树的补包含割，则删除该割集，生成树仍然存在，即图仍然连通，这与割集的定义矛盾。故任何生成树的补不包含割。 10.14 证明一个割集的补不含生成树。证明

设割集的补含有生成树，则删除割集后，生成树仍然在图中，也即图仍连通，与割集的定义矛盾。故一个割集的补不含生成树。

10.15证明一棵正则2－分树必有奇数个顶点。

证明

假设一棵正则2－分树有i个分枝点，每个分枝点有 2个儿子，故总的儿子数目为2i。而所有的儿子包括全部顶点减去一个根，即为分枝点数目i与树叶数目t之和,再减去1，所以有：

2i?i?t?1 即有： i?t?1

从而全部顶点数目为：

i?t?(t?1)?t?2t?1

显然, 它是一个奇数。

故一棵正则2－分树必有奇数个顶点。