离散习题(附答案) (9)(4)

第9章 习题解答

?0???解：D=??????121??011?，dij=1的含义是vi到vj距离为1或vi到vj有边。

101??120??

16

第9章 习题解答

习题 9.5

1.画出一个满足下述条件的无向欧拉图。 ⑴ 奇数个结点，奇数个边。 ⑵ 偶数个结点，偶数个边。 ⑶ 奇数个结点，偶数个边。 ⑷ 偶数个结点，奇数个边。

解：⑴奇数个结点，奇数个边的无向欧拉图如图9.85(a)所示。 ⑵偶数个结点，偶数个边的无向欧拉图如图9.85(b)所示。 ⑶奇数个结点，偶数个边的无向欧拉图如图9.85(c)所示。

⑷偶数个结点，奇数个边的无向欧拉图如图9.85(d)所示。

2.画出满足1中的四个要求的有向欧拉图。 解：⑴奇数个结点，奇数个边的有向欧拉图如图9.86(a)所示。

⑵偶数个结点，偶数个边的有向欧拉图如图9.86(b)所示。

⑶奇数个结点，偶数个边的有向欧拉图如图9.86(c)所示。

⑷偶数个结点，奇数个边的有向欧拉图如图9.86(d)所示。

3.若无向图G是欧拉图，G中是否存在割边? 为什么? 解：无割边。如果有割边，此边不在任何回路上，而无向图欧拉图图中有一条经过每一条边一次且仅一次的欧拉回路。所以G中无割边。

4.n取怎样的值，无向完全图Kn有一条欧拉回路? 这个结论对有向完全图Kn成立吗？为什么？

解：①n为奇数，?v∈V，deg(v)=n-1为偶数。所以，当n是大于或等于3的奇数时，Kn有欧拉回路。

②当Kn是有向完全图时，则不成立。因为，在有向图中有欧拉回路，必须每个结点入度等于出度，而这个条件Kn不满足。

5.完成下列各题：

⑴ 画一个有一条欧拉回路和一条汉密尔顿回路的图。 ⑵ 画一个有一条欧拉回路，但没有汉密尔顿回路的图。 ⑶ 画一个没有欧拉回路，但有一条汉密尔顿回路的图。

17

第9章 习题解答

解：⑴有一条欧拉回路和一条汉密尔顿回路的图如图9.87(a)所示。 ⑵有一条欧拉回路，但没有汉密尔顿回路的图如图9.87(b)所示。 ⑶没有欧拉回路，但有一条汉密尔顿回路的图如图9.87(c)所示。

6.证明：若G是有向欧拉图，则G是强连通的。

证明：因为G是有向欧拉图，G存在一条欧拉回路，G的每一条边都在这条欧拉回路上。因为欧拉图中无孤立点，所以所有结点也都在这条欧拉回路上，于是，G的任何一对结点通过欧拉回路相互可达，所以，G是强连通的。

7.n取怎样的值，无向完全图Kn是汉密尔顿图? 这个结论对有向完全图Kn成立吗？为什么？

解：当n≥3时，?v,u∈V，deg(v)+deg(u)=2n-2=n＋n-2≥n+3-2=n+1＞n，所以，此时Kn是汉密尔顿图。

这个结论对有向完全图Kn不成立。例如有向完全图K 4不存在汉密尔顿回路。如图9.88所示。

8.设G=?V,E?是一个无向简单图，|V|=n，|E|=m，设m=(n–1)(n–2)＋2。试证明G中存在一条汉密尔顿回路。

证明：证法1： 反证法。

设G中存在两个结点v1，v2使得deg(v1)+deg(v2)＜n。

删除结点v1和v2后,得图G′, G′是具有n–2个结点的无向图，最多删除了n–1个边。 设G′的边数为m′，则

18

12第9章 习题解答

m′≥m–(n–1) =(n–1)(n–2)＋2–(n–1)＞(n–1)(n–2)＋1–(n–1)

=(n–1)(n–2)–(n–2) =(n–2)(n–3)

即 m′＞(n–2)(n–3)

但G′是具有n–2个结点的简单无向图，它最多有

1(n–2)(n–3)，矛盾。所以，G中存在汉密尔顿回路。 21(n–2)(n–3)条边，即m′≤21212121212证法2：将图G看成有同样结点的完全图删除S个边而得到的，

111n(n–1)–S=?E?=(n–1)(n–2)＋2＞(n–1)(n–2) 22211n(n–1) –S＞(n–1)(n–2) 22n2–n –2S＞n2–3n +2 S＜n–1

而任何完全图中删除的边数小于n–1都是连通图，所以G是连通图。

9.设无向图G=?V,E?具有汉密尔顿路，S是V的任意非空子集，试证明W(G-S)≤|S|+1。 证明：设C是G的一条汉密尔顿路，W(C)=1对于任意S?V，删去S中的任一结点a1，则W(C－a1)≤2，如果再删去S中的另一个结点a2，则W(C－a1－a2)≤2，依次类推，可得W(C-S)≤|S|+1。因为C－S是G－S的生成子图，所以

W(G-S)≤W(C-S)≤|S|+1，即W(G-S)≤|S|+1。

10.试证明在无向完全图Kn (n≥6)中任意删除n-3条边后所得的图是汉密尔顿图。 证明：?v，u∈V，

如果，无向完全图Kn (n≥6)中任意删除了n－3条边。

①如果删除结点v上的一条边，则在结点u上至多删除了n－3个边，

deg(v)＋deg(u)=(n－1－1)+(n－1－(n–3))=(n－2)＋(n－1－n＋3)=(n－2)＋2=n ②如果删除了结点v上的2条边，则在结点u上至多删除了(n–3)–1个边， deg(v)＋deg(u)=(n－1－2)+(n－1－(n－4))=(n－3)+(n－1－n＋4)=(n－3)＋3=n

③当删除了结点v上的m条边，则在结点u上至多删除了(n–3)–(m–1)=n–m–2个边， deg(v)＋deg(u)=(n－1－m)＋(n－1－(n－m－2))=n－1－m＋n－1－n＋m＋2=n 根据定理9.5.5的推论，无向完全图Kn (n≥6)中任意删除n-3条边后所得的图是汉密尔顿图。

19

第9章 习题解答

习题 9.6

1.一棵无向树T有2个4度结点，3个3度结点，其余的结点都是树叶，问T有几片树叶?

解：设有x个树叶，结点数为：2＋3＋x，边数为：2＋3＋x－1，依定理9.1.1列方程：

2(2＋3＋x－1)= 2×4＋3×3＋x

解之得：x=9。即T有9片叶子。

2.无向树T有8片树叶，2个3度分枝点，其余的分枝点都是4度结点，问T有几个4度分枝点?

解：设有x个4度分枝点，则无向树T的结点数为：2＋x＋8，边数为：2＋x＋8－1，依定理9.1.1列方程：

2(2＋x＋8－1)= 8＋2×3＋4x

解之得：x=2。即T有2个4度分枝点。

3.设T是一棵无向树，它有ni个i度分枝点(i=2，3，…，k)，其余结点都是树叶，求T中的树叶数。

解：设有x个树叶，则无向树T的结点数为：?ni+x，边数为：?ni+x－1，依定理

i?2i?2kk9.1.1列方程：

2(?ni+x－1)=?ini+x

i?2kki?2解之得：x=?ini－?2ni＋2=??i?2?ni＋2=??i?2?ni＋2

i?2kkkki?2i?2i?34.证明：有n个结点的无向树，其结点度数之和为2n－2。

证明：该无向树的边数为：m=n－1，度数之和为：2m=2(n－1)=2n－2

5.设无向图G=?V,E?是k (k≥2)颗树组成的森林。|V|=n，|E|=m，证明：m=n–k。 证明：设第i颗树Ti的结点数和边数分别为ni和mi。则mi=ni－1，i=1…k。?ni=n，

i?1k?mi=m，两边求和得：?mi??ni??1。即m=n－k。

i?1i?1i?1i?1kkkk6.设T是一棵非平凡的无向树，树T的最大度?(T)≥k，证明树T至少有k片树叶。 证明：设树T有n个结点，这n个结点中，其中x个为树叶，则树T的边数为n－1，依定理9.1.1列方程：

2(n-1)=?deg(v)

v?V因为 ?(T)≥k，所以，?u∈V，使deg(u)≥k(u为分枝点)。而其余的分枝点v，deg(v)≥2。所以，2(n－1)=?deg(u)≥x＋2(n－x－1)＋k，解之得：x≥k。

v?V7.图9.52是无向连通图。图9.52有多少个生成树？它们的补各是什么？

20

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散习题(附答案) (9)(4)在线全文阅读。