《第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棵
7、非同构的无向树。注:“4度分至点”改为“4度分支点”。解:设4度分支点个,则 ,解得度数列11111111334417. 证明:阶无向树不是欧拉图。证明:无向树没有回路,因而不是欧拉图。18. 证明:阶无向树不是哈密尔顿图。证明:无向树没有回路,因而不是哈密顿图。19. 证明:任何无向树都是二部图。证明一:无向树没有回路,因而不存在奇数长度的圈,是二部图。证明二: 取定一点w为T的树根。对T的每一点v,w到v有唯一链,于是d(w,v)=h(v)是v的一个特性参数(关于树根的高)。对T的任二不同结点u和v,u和v相邻仅当|h(u)-h(v)|=1。于是令X=v|h(v)为偶数,Y=v|h(v)为
8、奇数,则X(Y)的不同点不会相邻,得证T= XY 是二部图。20. 什么样的无向树既是欧拉图又是哈密尔顿图。解:一阶无向树。21. 下面两个正整数列中,哪个(些)能充当无向树的度数列?若能,请画出3棵非同构的无向树。1)1,1,1,1,2,3,3,42)1,1,1,1,2,2,3,3解:无向树有8个结点,故有7条边,总度数应为27=14。1)中正整数列和是16,2)中正整数列和是14。因此1)中正整数列不能充当无向树的度数列。2)能充当无向树的度数列,3棵非同构的无向树如下: 22设G=为连通图,切。证明:当且仅当是G的割边时,才在G的每棵生成树中。证明:充分性。设边e是G的割边,删去e,G就
9、分成两个互不连通的子图G1和G2。对于G的任一棵生成树T,由于T是连通图,故连结G1与G2之间的唯一边e必在T中。 必要性。用反证法。设边e包含在G的每棵生成树中,但e不是割边。在图G中删去e得图G,G仍是连通图。对G来说必有一棵生成树T,T中不包含边e,与假设矛盾。23. ()各有多少棵非同构的生成树?解:K1 K1生成树 K2 K2生成树 K3 K3生成树 K4 K4生成树 K5 K5生成树 K6 K6生成树 K7K7生成树 24对于下图,利用求一棵最小生成树。12345678910解:1 12步骤1 步骤2123 1235步骤3 步骤4 12357 步骤5 25证明在完全二叉树中,边的总
10、数等于2(n-1),式中n是树叶数。证明:设分枝点数为i,由定理9.2-7,(2-1)i=n-1,即i=n-1。在完全二叉树中,每个分枝有2条边,故边的总数为2(n-1)。26在一棵t叉树中,其外部通路长度与内部通路长度之间有什么关系。解:在一棵完全t叉树中,有n个分枝点,若内部通路长度总和为I,外部通路长度总和为E,则满足关系式E(t-1)I+tn。证明:对分枝点数目n进行归纳。当n1时,Et,I=0,故E(t-1)I+tn成立。假设nk-1时成立,即E(t-1)I+tn(t-1)I+t(k-1)。当nk时。若删去一个分枝点v,该分枝点与根的通路长度为L,且v的t个儿子是树叶,得到新树T。将
11、T与原树比较,它减少了t片长度为L+1的树叶和一个长度为L的分枝点,因为T有(k-1)个分枝点,故E(t-1)I+t(k-1) (式(1))但在原树中,有EE-L +t(L+1)E+(t-1)L+t (式(2))II+L (式(3))式(1)(3)代入式(2)得E= E+(t-1)L+t=(t-1)I+t(k-1)+(t-1)L+t=(t-1)(I+L)+tk=(t-1)I+tk=(t-1)I+tn。27给定权1,4,9,16,25,36,49,64,81,100,构造一棵最优二叉树。解:最优二叉树如下:28证明下图中所示各图都是平面图。(1)(2)证明:图(1)的同构平面图如下:123456
12、456231图(2)的同构平面图如下:123456 16352429证明:小于30条边的平面简单图有一个结点度数小于等于4。证明:用反证法。假设任一顶点的度均大于或等于5,则5n2m60,即n12。 又因为 5n2m6n 12于是5n6n 12,即n12。矛盾。因此至少有一个顶点的度不大于4。30证明:在6个结点12条边的连通平面简单图中,每个面用3条边围成。证明:根据欧拉公式n m + r=2,有 r=2 n + m=8故每个面的平均度数为2m/r = 3又因为连通平面简单图(n3)中每个面的度数均大于或等于3,因此该图每个面的度数均为3。31设G有11个或更多结点的图,证明G或是非平面图。注:G为简单无向图。证明:用反证法。假设G和G的补都是平面图,且G的边数为m,的边数为m,则有m3n 6,m3n 6(注意,定理9.3.4对非连通简单平面图同样成立)。进而 m + m6n 12又因为 m + m=n(n 1)/2,故 n(n 1)/26n 12得3n10,与n11,矛盾。因此G和G的补中至少有一个是非平面图。32证明:1) 对于的任意边e,-e是平面图。2)对于的任意边e,-e是平面图。证明一:显然,-e与-e不包含与或在2度结点内同构的子图。所以由Kuratowski定理,-e与-e是平面图。证明二:-e(a): -e(b): :-e:123456 456231