习题7
本章目录 · 1 节
本章导读
本章按原书7.1—7.42保留全部习题组,并为原本无顶点标号的图补上说明用标号。无向树的路径指初级通路,长度按边数;欧拉、哈密顿图均要求闭合回路。“非同构”不等于“边集不同”:同一形状的不同标号实现须合并;根树还必须保留根的位置,但不把儿子的左右换画另计为新类。
【习题7.1】画出全部5阶及7阶非同构无向树。
解:5阶恰有3类,7阶恰有11类,下面逐一画全。图形可旋转、拉伸,但顶点数、连接关系不变。5阶的三类分别为路径、度3分支延长一臂、星;7阶不能只按度数列分类,因为相同度数列可能对应不同树。完整性可用普吕弗编码枚举全部有标号树,再依树的同构关系合并检验:5阶有 个编码、7阶有 个编码,分别合并成3、11类。
【习题7.2】树有5片树叶、3个2度点,其余为3度点,求阶数。
解:设3度点数为 。握手定理给 ,得 。所以共有11个顶点、10条边。也可用树叶恒等式 ,得到 。
【习题7.3】树有8片叶、两个3度点,其余分支点为4度点,求4度点数并画四棵非同构例子。
解:设4度点数为 ,则 ,得 ;全树有12个顶点。以下四棵树都由一条四个内点的路径加上8片叶得到,沿内点路径的最终度数分别为 、、、。两3度点距离与两4度点距离分别为 ,这是同构不变量,故四者确实不同构。
【习题7.4】非平凡树有 个度数为 的分支点,,其余为叶,求叶数。
解:设叶数 ,由 和 相减,得到 。2度点不改变叶数;每多一个 度分支点,相对路径就需增加 片叶。平凡树的唯一0度点不满足题设“其余都是树叶”的条件,不能无条件套这个公式。
【习题7.5】 阶树的最大度最少、最多各为多少?
解:,两个界都能达到。路径 的最大度为2,星 的最大度为 。若最大度不超过1,连通图至多有两个顶点,与 矛盾。
【习题7.6】 阶树最大度为2,最长路径多长?
解:连通、无圈且各度至多2,只能是 ,因此最长路径经过全部 点,长度为 条边,不是 。
【习题7.7】证明至少两个顶点的树不是欧拉图。
证明:非平凡树至少有两片树叶,它们度数为1,违反欧拉图全偶度条件。因此没有欧拉回路;其中路径虽然有开放欧拉通路,仍不能称欧拉图。
【习题7.8】证明至少两个顶点的树不是哈密顿图。
证明:树没有圈,而哈密顿回路必须是覆盖全部顶点的圈。也可看树叶:回路中的顶点必须有两条不同关联边,1度树叶不可能满足。
【习题7.9】证明任意无向树都是二部图。
证明:任选根,按到根的距离奇偶把点分为两部。树中每条边都连接某点与其父亲,层数相差1,因此必跨两部;若同层奇偶相同的两点有边,会与树内唯一路径构成圈。平凡树可一部含该点、另一部为空,仍满足二部图定义。
【习题7.10】什么树既是欧拉图又是哈密顿图?
解:只有平凡树 ,按教材约定同时具有这两种性质。任意至少两点的树由7.7、7.8都被排除。
【习题7.11】什么树是半欧拉图?
解:恰为 的路径 。半欧拉条件要求恰有两个奇度点,而所有叶都是奇度,树至少两叶,所以只能恰有两叶。由7.4,不能再有3度及以上分支点,因而只能是路径。反向路径两端奇度、其余2度,确有开放欧拉通路而无欧拉回路。
【习题7.12】什么树是半哈密顿图?
解:也恰为 的路径 。哈密顿通路已用 条不同边,而树总共恰有 条边,所以整棵树就是这条路径;反向显然。平凡树按约定是哈密顿图,不能再归到“有通路但无回路”的半哈密顿图。
【习题7.13】判断 与 能否作为树的度数列;可行者画三种非同构实现。
解:第一列和为16,8阶树应为 ,所以不能。第二列和14,且均为正整数,可以实现。一般正整数列满足和 时,可以让顶点 在普吕弗编码中出现 次,总长度恰 ,从而得到对应树。
以下三棵的度数多重集均为第二列,两3度点之间的距离分别为1、2、3,所以不同构。
【习题7.14】连通图的边 属于每一棵生成树,它必须具有什么性质?
解:当且仅当 是桥。桥是连接其两侧顶点的唯一跨边,任何生成树都必须含它;若 非桥, 仍连通,取它的一棵生成树就不含 ,否定“每棵都含”。
【习题7.15】连通图的边 不属于任何生成树,它必须具有什么性质?
解:当且仅当 为自环。自环不可能出现在树中;反向若 不是环,单条 加其余孤立点是森林,可不断加入连接不同分支的原图边,因 连通最终扩充成一棵含 的生成树。所以普通非环边即使在圈上,也并非“永远不能选”。
【习题7.16】非环也非桥的边,既能作某生成树的树枝,也能作另一个的弦。
证明:非环保证可以从只含该边的森林扩充出生成树,故能作树枝;非桥保证 连通,取其中一棵生成树,则 未选入、恰作弦。两个条件各自负责一个方向,不能省略。
【习题7.17】证明任一生成树的余树不包含原图的边割集。
证明:若某割集的全部边都属于余树,就全部不属于生成树。删除这些边后原图已分开,生成树却仍保留全部自己的边并连接所有顶点,矛盾。因此每个割集至少含一条树枝。这里“余树不包含”不是说它不能包含割集中的某一条边,而是不能把整个割集都包进去。
【习题7.18】若 是连通图的边割集,证明 不含 的生成树。
证明: 已不连通,任何子图都不能重新连接不同分支,而 的生成树必须保留全部原顶点且连通。各分支可以分别有自己的生成树,但它们的并只能是生成森林。
【习题7.19】原图中要求边 均为树枝,有几类非同构生成树?画出它们。
解:强制三边为 ,它们形成两分支 、,再选一条跨边即可。跨边只有 或 ;另一条平行 会成二圈, 会在右侧成圈。故共有2棵、也恰为2类:一棵为五点路径,另一棵有3度分支点。
树边为 。
树边为 。
【习题7.20】原六顶点图有几类非同构生成树?画出它们。
解:共有5类。六阶无向树有6类,其中星 需要5度中心,而原图最大度只有4,故不可能;另外五类都可实现,下面逐一给出原图中的边集代表。原图实际有120个不同的有标号生成树边集,但题目问非同构类型,不能把120作为答案。
第1类树边为 。
第2类树边为 。
第3类树边为 。
第4类树边为 。
第5类树边为 。
【习题7.21】 各有多少类非同构生成树?
解:依 ,分别为 。因为任意 阶树都可以作为 的生成子图,所以就是各阶无向树同构类数。不能用有标号树数 替代;例如 有125个有标号生成树,却只有3种形状。
【习题7.22】 是 阶树,简单图 满足 ,证明 含与 同构的子图。
证明:先为 任取根,按父亲先于儿子的次序嵌入 。已嵌入 点时,要把新点接到其已嵌入父亲上;该父亲在 至少有 个邻点,而已占用的其他顶点至多 ,所以至少有一个未用邻点可选。继续到全部 点,树边全部对应原图边,得到同构子图。原图中这些点之间可能还有额外边,选子图时不用它们即可;本命题不是说一定含同构的导出子图。
【习题7.23】森林由 棵树组成,共 点、 边,证明 。
证明:第 棵树有 点、 边,包括孤立点形成的平凡树也成立。求和 。
【习题7.24】对两幅图的实线生成树,列出全部弦及基本回路系统、全部树枝及基本割集系统。
解:保持原图字母边号,下面的集合表示边集,不表示书写顺序就是连续行走顺序。基本圈各含唯一对应弦,基本割集各含唯一对应树枝。
图(a)树枝为 ;弦为 。
弦 对应基本圈 。
弦 对应基本圈 。
弦 对应基本圈 。
弦 对应基本圈 。
树枝 对应基本割集 。
树枝 对应基本割集 。
树枝 对应基本割集 。
树枝 对应基本割集 。
以上全部基本圈构成该图对应实线树的基本回路系统,全部基本割集构成基本割集系统;图(a)的圈秩为4,割集秩为4。
图(b)树枝为 ;弦为 。
弦 对应基本圈 。
弦 对应基本圈 。
弦 对应基本圈 。
弦 对应基本圈 。
弦 对应基本圈 。
树枝 对应基本割集 。
树枝 对应基本割集 。
树枝 对应基本割集 。
树枝 对应基本割集 。
树枝 对应基本割集 。
以上全部基本圈构成该图对应实线树的基本回路系统,全部基本割集构成基本割集系统;图(b)的圈秩为5,割集秩为5。
【习题7.25】求两幅带权图的最小生成树。
解:用克鲁斯卡尔法,先按权排序,只有连接不同分支的边才加入;同权可能产生不同但同样最优的树。下面深色实线是选中边,浅色虚线是未选边。
图(a)可取树边 ,依加入次序的权为 ,总权为 。
图(b)可取树边 ,依加入次序的权为 ,总权为 。
【习题7.26】非平凡树最大度至少 ,证明至少有 片树叶。
证明:取度数 的顶点 ,删除它分成 个分支。在每个分支中取离 最远的点;该点若还有除朝向 以外的邻点,就会存在更远点,矛盾,所以它在原树中是叶。各分支给出不同叶,共至少 片。
【习题7.27】圈 上两条不同边 ,证明原图有同时包含它们的割集。
证明:原图不一定连通,先只在包含 的连通分支 内操作。把路径 扩充成 的生成树 ,它包含 ;弦 对应的基本圈恰为 。删除树枝 产生的基本割集中, 也跨越两侧,因此这个割集同时包含二边。它割开 的一个分支,其他原分支不受影响,故同样是原图的割集。两条边取不同者,避免把单个自环误说成可以属于割集。
【习题7.28】树 的两个树子图 至少共一条边,证明公共边的边导出子图也是树。
证明:它是树的子图,必无圈。任取其两个端点 ,二者都属于两个树子图; 中唯一的 路径必须同时包含在 中,否则其中一棵子树就无法连通这两点。因此路径每条边都为公共边,公共边导出图连通。结合无圈即为树;公共边非空排除了空边导出图的定义歧义。
【习题7.29】 阶简单图或其补图中必含圈。
证明:若两图都无圈,都是森林,故各至多 条边。可是两图边数之和是 ,必须满足 ,即 ,与题设矛盾。
【习题7.30】两生成树中,边 属于 而不属 ,证明存在边 可以同时交换并仍各为生成树。
证明:删除 的 ,把顶点分成 ; 唯一跨这两部的边原来就是 。在 中加入 形成一个圈,这个圈除 外必还有一条跨越 的边 。该边属 、不属 。向 加 恰好连通两分支;从 删除圈上 恰好破圈,两者都保留全部顶点和 条边,所以均为生成树。
【习题7.31】回答原根树的叉数、高度、内点数、分支点数。
解:按所需最小上界是4叉树,因为根恰有四个儿子,其余点均不超过4。树高4,在最深叶 达到;内点为 共5个,分支点再加根 共6个。全树13点、7叶。层数按边计,不能把最长根叶路径上的5个顶点误作高度5;根也不能计入教材所称的“内点”。
【习题7.32】画三棵高度3、基图互不同构的二叉正则树。
解:下面分别有7、9、11个顶点,每个分支点恰有两个儿子,高度均为3。顶点数已经不同,所以其基图必不同构,无须只凭画面外观判断。
【习题7.33】画高度3的完全正则二叉树。
解:第0至3层点数为1、2、4、8,共15点、8叶;全部叶都在第3层,每个非叶点有两个儿子。不能用仅有部分末层叶的普通“完全二叉树”代替。
【习题7.34】原有向图是否存在根树生成子图?若有,几类非同构?
解:存在,共3类;若按原顶点、弧身份数,共有5个不同边集。原顶点 没有入弧,所以任何生成根树都必须以 为根; 唯一入弧是 ,它也必须选。再给 各选一条入弧并排除二圈,可得5种。它们合并为:高度3的链;根仅有一个儿子、该儿子再分两个叶的高度2树;根有两个儿子、其中一个再有一个儿子的高度2树。下图按根在上重排,省略向下箭头,所有边都仍取自原图。
【习题7.35】画全部 阶非同构根树。
解:按 ,分别为1、1、2、4、9类,共17类,下面全部列出。这里根必须对应根,但儿子不规定左右次序;同一无向树选不同位置为根可能产生新类,单纯把同一根树左右翻画不产生新类。
【习题7.36】二叉正则树有 叶,证明共有 顶点。
证明:设分支点数为 ,总点数 。每个分支点恰有两条出弧,所以边数 ,解得 。编码中把平凡根树视为单叶时, 也符合。若不是正则树、允许单儿子节点,这个等式一般不成立。
【习题7.37】构造叶权3、4、5、6、7、8、9的最优二叉树并求权。
解:一次合法霍夫曼合并为 。树权等于各次合并权之和 ,完整最优树如下。两个7分别来自原叶和第一次合并,不能把相同数字误当同一节点。
【习题7.38】判断原五个字符串集合是否前缀码。
解: 是; 是; 不是,因为1是11及101的前缀,001又是0011的前缀。
是:首字符为b、c的码不与其他组混淆,d组两码等长,a组三码等长,组内也没有前缀包含。 不是,因为a是后面所有a开头长码的前缀。非二进制字母码同样适用前缀定义,不能只检查0、1集合。
【习题7.39】用原二叉树产生一组二元前缀码。
解:固定左0右1,根叶路径依次给出 。七片叶恰对应七个码字,内部节点上的较短串不是码字,不能也纳入集合。
【习题7.40】哪类二叉树能产生等长前缀码?
解:准确条件是全部树叶都在同一层,因为每个码长就是叶的层数。若另限定为二叉正则树,这恰好是完全正则二叉树。但原题只说二叉树,允许单儿子时不能说“只有完全正则树”:例如根先经一条标0的单儿子边,再分出0、1两叶,就产生等长码00、01,却不是二叉正则树。
【习题7.41】字母a至g频率35%、20%、15%、10%、10%、5%、5%,求最佳前缀码、最优树及传输位数。
解:按频数构造,一种合并顺序的权为10、20、25、40、60、100,和为255,所以平均每个字母2.55位。一组具体对应为
,,,,,,。
按题设比例恰好出现的 个字母,,需要 位。相同频数的合并与左右安排可改变具体码字,只要前缀性质、对应频数及总权正确,不能判别的同权解为错;若频率仅是概率模型,这个公式表示期望位数。
【习题7.42】还原原表达式树的算式,并写前序波兰式、后序逆波兰式。
解:中序加必要括号后为 。第一部分是先除后乘g,第二部分的分母是整个 ;不是把除法和后面的乘法随意移出分母。
前序波兰式按记号分隔为 。
后序逆波兰式为 。两式都应恰含12个操作数、11个二元运算符。栈求值时,后缀式先弹出右操作数,前缀式从右向左扫描时先弹出左操作数;尤其不能把 倒置。原式要求 且 。
