第9章特殊图及其应用.doc
习题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）画一个有一条欧拉回路，但没有一条哈密尔顿回路的图。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证明：有桥的图不是欧拉图。证明：方法一 反证法。假设图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)。由于删除了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。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的割边。 充分性。 任取两个结点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)=2·2+1·3+3·4+x·1，x9。16. 无向树有8片树叶，2个3度分支点，其余的分支点都是4度顶点，问有几个4度分至点？根据的度数列，请至少画出4棵非同构的无向树。注：“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)为奇数，则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条边，总度数应为2×7=14。1）中正整数列和是16，2）中正整数列和是14。因此1）中正整数列不能充当无向树的度数列。2）能充当无向树的度数列，3棵非同构的无向树如下： 22设G=<V，E>为连通图，切。证明：当且仅当是G的割边时，才在G的每棵生成树中。证明：充分性。设边e是G的割边，删去e，G就分成两个互不连通的子图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证明在完全二叉树中，边的总数等于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。将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）的同构平面图如下：123456456231图（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
