第9章特殊图及其应用.doc
《第9章特殊图及其应用.doc》由会员分享,可在线阅读,更多相关《第9章特殊图及其应用.doc(12页珍藏版)》请在三一文库上搜索。
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时,有向完全图为哈密尔顿图。41)画一
2、个有一条欧拉回路和一条哈密尔顿回路的图。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)|S|=1,与W(G-S)2矛盾。故有桥的图不是哈密尔顿图。6证明:有桥的图不是欧
3、拉图。证明:方法一 反证法。假设图G为欧拉图。利用简单回路的一个性质,设C为任意的简单回路,e为C上任意的边,则c-e仍连通。记这个性质为*因为G为欧拉图,所以存在欧拉回路,设C为其中的一条欧拉回路,则G中任何边均在C上。于是,eE(G),G=G-e=C-e。由*可知,G仍连通,故由桥的定义可知,e不是G中的桥。由e的任意性得证,G中无桥。故假设错误,图G为欧拉图。方法二 反证法。假设图G为欧拉图。设e=(u,v)为G中的桥,由于G为欧拉图,所以e的两个端点在G中的度数dG(u),dG(v)均为偶数。因为e为G中桥,所以G=G-e由两个连通分支G1和G2组成。不妨设uV(G1),vV(G2)。
4、由于删除了e,因而在G1和G2中,dG1(u)与dG2(v)为奇度顶点,而对于任意的wV(G1),wu,dG1(w)为偶数,即G1中只有一个奇度顶点u;类似地,G2中也只有一个奇度顶点v。这与握手定理的推论矛盾。故G中不可能含桥。7. 判断下列命题是否为真?1)完全图()都是欧拉图。2)阶有向完全图都是欧拉图。解:1)假。2)真。8. 证明:若有向图是欧拉图,则是强连通的。证明:若有向图是欧拉图,中必有有一个回路L,通过图中每边一次且仅一次。由于L通过图中每条边,L必定至少包含每个结点一次。由定理8.2.5,有向图是强连通的。9判断下图是否有哈密尔顿回路。解:没有哈密尔顿回路。因为图中有割点v
5、。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)|S|+1,而C-S是G-S的生成子图,故 W(G-S)W(C-S)|S|+113. 画出所有5阶和7阶非同构的无向树。解:14当且仅当连通图的每条边均为割边时,该连通图才是一棵树。证明:必要性。 如果图G是树。则删去任一边后,就成为不连通图,故任一边都是G的
6、割边。 充分性。 任取两个结点u和v,图G是连通的,u和v之间就有路。如果连接u和v有两条路,该两条路就可组成一个回路,删去回路上任意一条边,不改变图的连通性,这样该回路上的各条边都不是割边,与假设矛盾,因此任意两个结点之间恰有一条路,图G是树。15一棵树有两个结点度数为2,一个结点度数为3,三个结点度数为4,问它有几个度为1的结点。解:设有x个度数为1的结点,结点数v2+1+3+x6+x,边数ev-1=5+x。而2edeg(vi),故2(5+x)=22+13+34+x1,x9。16. 无向树有8片树叶,2个3度分支点,其余的分支点都是4度顶点,问有几个4度分至点?根据的度数列,请至少画出4棵
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 特殊 及其 应用
链接地址:https://www.31doc.com/p-2534003.html