《特殊图及其应用》word版

《《特殊图及其应用》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、习题91．构造一个欧拉图，其结点树v和边树e满足下述条件1)v、e的奇偶性一样。2）v、e的奇偶性相反。如果不可能，说明原因。解：1）2）2．确定n取怎样的值，无向完全图Kn为欧拉图；n取怎样的值，有向完全图为欧拉图。解：一个图中若存在欧拉回路，必满足每个结点的度数均为偶数．对于无向完全图Kn，deg(v)=n–1。所以，当n是奇数时，无向完全图Kn有一条欧拉回路。所有有向完全图为欧拉图。3.确定n取怎样的值，无向完全图Kn为哈密尔顿图；n取怎样的值，有向完全图为哈密尔顿图。解：n=1或n≥3时，无向完全图Kn是哈密尔顿图。n≥1时，有向完全图为哈密尔

2、顿图。4．1）画一个有一条欧拉回路和一条哈密尔顿回路的图。2）画一个有一条欧拉回路，但没有一条哈密尔顿回路的图。3）画一个没有一条欧拉回路，但有一条哈密尔顿回路的图。解：（1）有欧拉回路和哈密尔顿回路；（2）有欧拉回路，但无哈密尔顿回路；（3）无欧拉回路，但有哈密尔顿回路；（4）既无欧拉回路，又无哈密尔顿回路。（1）（2）（3）（4）5．证明：有桥的图不是哈密尔顿图。证明：采用反证法。假设哈密尔顿图G中存在桥e=(u,v)，取结点集V的一个非空子集S={u}，必有W（G-S）≥2。因为G为哈密尔顿图，由定理9.1-5，W（G-S）≤

3、S

4、=1，与W（G

5、-S）≥2矛盾。故有桥的图不是哈密尔顿图。6．证明：有桥的图不是欧拉图。证明：[方法一]反证法。假设图G为欧拉图。利用简单回路的一个性质，设C为任意的简单回路，e为C上任意的边，则c-e仍连通。记这个性质为*因为G为欧拉图，所以存在欧拉回路，设C为其中的一条欧拉回路，则G中任何边均在C上。于是，e∈E(G)，G'=G-e=C-e。由*可知，G'仍连通，故由桥的定义可知，e不是G中的桥。由e的任意性得证，G中无桥。故假设错误，图G为欧拉图。[方法二]反证法。假设图G为欧拉图。设e=(u,v)为G中的桥，由于G为欧拉图，所以e的两个端点在G中的度数dG(u

6、),dG(v)均为偶数。因为e为G中桥，所以G'=G-e由两个连通分支G1和G2组成。不妨设u∈V(G1)，v∈V(G2)。由于删除了e，因而在G1和G2中，dG1(u)与dG2(v)为奇度顶点，而对于任意的w∈V(G1)，w≠u，dG1(w)为偶数，即G1中只有一个奇度顶点u；类似地，G2中也只有一个奇度顶点v。这与握手定理的推论矛盾。故G中不可能含桥。7.判断下列命题是否为真？1）完全图（）都是欧拉图。2）阶有向完全图都是欧拉图。解：1)假。2）真。8.证明：若有向图是欧拉图，则是强连通的。证明：若有向图是欧拉图，中必有有一个回路L，通过图中每边一

7、次且仅一次。由于L通过图中每条边，L必定至少包含每个结点一次。由定理8.2.5，有向图是强连通的。9．判断下图是否有哈密尔顿回路。解：没有哈密尔顿回路。因为图中有割点v。v10．判断以下图形能否一笔画出。（1）（2）解：（1）是欧拉图，能一笔画出。（2）是半欧拉图，能一笔画出。11．证明如G具有哈密尔顿路，则对于V的每一个真子集S有证明：设C是G的一条哈密尔顿路，W(C)=1，对于任一SV，删去S中任一结点a1，则W(C-a1)≤2，如果再删去S中结点a2，则W(C-al-a2)≤3，依此类推，可得W(C-S)≤

8、S

9、+1，而C-S是G-S的生成子图，

10、故W(G-S)≤W(C-S)≤

11、S

12、+113.画出所有5阶和7阶非同构的无向树。解：14．当且仅当连通图的每条边均为割边时，该连通图才是一棵树。证明：必要性。如果图G是树。则删去任一边后，就成为不连通图，故任一边都是G的割边。充分性。任取两个结点u和v，图G是连通的，u和v之间就有路。如果连接u和v有两条路，该两条路就可组成一个回路，删去回路上任意一条边，不改变图的连通性，这样该回路上的各条边都不是割边，与假设矛盾，因此任意两个结点之间恰有一条路，图G是树。15．一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，问它有几个度为1的结点。解：

13、设有x个度数为1的结点，结点数v＝2+1+3+x＝6+x，边数e＝v-1=5+x。而2e＝Σdeg(vi)，故2(5+x)=2·2+1·3+3·4+x·1，x＝9。16.无向树有8片树叶，2个3度分支点，其余的分支点都是4度顶点，问有几个4度分至点？根据的度数列，请至少画出4棵非同构的无向树。注：“4度分至点”改为“4度分支点”。解：设4度分支点个，则，解得度数列11111111334417.证明：阶无向树不是欧拉图。证明：无向树没有回路，因而不是欧拉图。18.证明：阶无向树不是哈密尔顿图。证明：无向树没有回路，因而不是哈密顿图。19.证明：任何无向树

14、都是二部图。证明一：无向树没有回路，因而不存在奇数长度的圈，是二部图。证明二:取定一点w为T的