习题8
本章目录 · 1 节
本章导读
【习题8:读图和计数约定】本组保留教材8.1至8.27的顺序。图中只有圆点是顶点,无圆点的交叉不增加顶点;曲线和直线按端点确定边,平行边分别编号。面边界按闭合行走记录,桥在同一面的边界上经过两次。下面的平面嵌入只改变画法,原来的顶点、边和关联关系保持不变。
【8.1】证明题8.1图中的三个图都是平面图。
解:(a)的两部为 与 ,跨部边中仅缺 ,是 删去一条边所得的图。把 放在上下两端, 分别置于三条两边通路的中间,再把 放在 之间并连到二者,得到下一题的无交叉嵌入。
(b)为 删去 的图,有5点9边,可以重画成所有面均为三角形的平面嵌入。(c)由两个三角形 与 ,加三条匹配边 组成,是三棱柱的骨架图。把两个三角形一外一内放置,依次连接相应点即可。下面三幅无交叉图给出具体构造,所以证明不依赖“边数没有超过上界”这一必要条件。
【8.2】分别给出上一题三图的平面嵌入,并验证面次数之和等于边数两倍。
(a)有4个面,每个面次数为4,故 ,且 。中间的 是两个不同顶点,不能把它们合并。
(b)有6个三角面,次数和为 ,且 。
(c)有2个三角面、3个四边面,包括外部面,次数和为 ,且 。内外三角形各自的三个点以及三条连接边都完整保留。
【8.3】给三个平面嵌入的边编号,求所有面的边界和次数。
以下边界序列按图中 记录,可整体反向或循环换起点,但不得把重复出现的桥去重。
(a)三个内部面的边界可取 、、,次数依次为3、3、4;外部面边界为 ,次数6。总和 。
(b)三个内部面的边界为 、、,次数3、3、1。外部面边界可取 ,次数9。每条桥都往返一次,环的外侧还在外部面中出现一次,故 。
(c)内部方形面的边界为 ,次数4;环围出的内部面为 ,次数1。唯一外部面有两条边界行走:,长5;,长6。外部面的次数为 ,总和 。这里有8点8边2个分支3个面,。
【8.4】把题8.3(a)重画,使外部面次数分别为3和4。
保留原图全部6点8边,将原来的屋顶三角面作为外部面,其他顶点和边放到它内部。外部边界为 ,次数3;其他面的次数为3、4、6。
将原来的方形面作为外部面,屋顶点和右侧附加点都移入该方形内。外部边界由 构成,次数4;其他面的次数为3、3、6。两图的面次数多重集同为 ,只是选择了不同的外部面,没有删边或添点。
【8.5】求题8.5图所有面的边界和次数。
此图是一棵树,只有一个面。其边界可写为顶点行走 ,长度为12。每条边恰好往返一次,故面次数为 ,不是6。树枝所围出的视觉空隙不是新的有界面。
【8.6】证明定理8.1.4:极大平面图连通,阶数至少3时无割点、无桥。
若有两个不同分支,可重画后在两个分支外部面上的顶点间加边,仍无交叉,违背极大性。若有割点 ,在其周围取进入两个不同分支且局部相邻的两条边 ,则 原先不存在,否则两分支可绕过 连通。沿这两条边旁的小邻域补边 ,仍可平面,再次违背极大性。最后,至少3点的连通图若有桥,其至少一个端点必为割点,因此无桥。 的唯一边是桥,所以“至少3点”的限制必须保留。
【8.7】证明题图中两图都是极大平面图。
原画法中若有无圆点交叉,不据此添顶点,先保留关联关系重画。
(a)的 ,八个面均为三角形,且 ,故为极大平面图。
(b)中央圆点是实际顶点,与其相接的线段要分别计边;无圆点的其余交叉不算顶点。正确计数为 。重画后包括外部面在内的14个面都为三角形,且 ,故也极大。不能误按八顶点图套边数界。
【8.8】验证 和 是极小非平面图。
两图均非平面。 的任意边可由顶点置换移到同一位置,所以只须展示删一条代表边后可平面; 的各边也在保两部的顶点置换下等价,同样只须一个代表。
两幅无交叉图分别给出证据,故两图都满足“删掉任意一条边即变为平面图”,是极小非平面图。极小不是要求删顶点,也不是仅检查某一条边会使图变平面。
【8.9】题图是极小非平面图吗?
不是。图有5点11边, 有两条平行边;任选删去其中一条,剩下的十条边恰构成五点的 ,仍非平面。因此它连“删任意边后都可平面”的要求都不满足。中央圆点 分开 和 ,外侧另有 ,不可把穿过 的两段擅自合成同一条边,也不能丢掉平行边。
【8.10】验证两幅平面嵌入满足欧拉公式。
(a)外方形、内方形各4点,各有4边,另有4条对应连接边,故 。有4个侧方形面、一个内部方形面、一个外部方形面,故 ,;面次数之和 。
(b)六个圆点之间共有12条边,8个面均为三角形,故 ,,且 。曲线上靠近其他点的位置不是新的端点。
【8.11】验证题图的非连通欧拉公式。
三个部分合起来计数,不能将每部分各自的外部面相加。A为三角形内接一条树叶边,有4点4边;B为三点两边的路径;C为两点、两条平行边和一个自环,有2点3边。总计 。
有界面分别是A中边界带一次树叶往返的5次面、C的2次平行边面和1次环面,另有唯一外部面。外部面的三条边界行走长度分别为3、4、3,故其次数为10。于是 ,,且 。A中的树叶画在三角形内部,故不能把这个内部面的次数误记为3。
【8.12】利用简单平面图边数界证明 非平面。
若可平面,则应有 。代入 得 ,矛盾。
【8.13】为什么同一边数界不能证明 非平面?
代入 只得到真不等式 ,没有矛盾。 实际非平面,因此 是必要条件而非充分条件。要证明它非平面,可利用二部图无奇圈的更强界 ,得到 的矛盾。
【8.14】设简单平面图面数 ,且 ,证明存在次数不超过4的面;说明 时可以不成立。
反设每个面次数均至少5,则由面握手定理 ;由顶点握手定理和最小度条件,。允许原图不连通,设有 个分支,使用推广欧拉公式得
所以 ,与条件矛盾。这一证明没有偷偷增加“图连通”的前提。
当 ,取正十二面体骨架图:,每个顶点度为3,全部12个面次数均为5,包括外部面,所以不存在次数不超过4的面,正好说明严格不等号不可放宽。
【8.15】简单平面图 ,证明 。
反设每点度至少5,则 ,且此时 ,可以使用 。于是 ,从而 ,矛盾。故至少有一点度不超过4。这里讨论非空顶点集,空图不定义最小度。
【8.16】 的简单图 与补图 至少一个非平面。
若二者都可平面,则边数之和满足 ,即 。然而在 时左侧为2,此后每把 增加1,该式增加 ,所以对所有 都为正,矛盾。只是假定两图均简单平面,并未要求它们连通。
【8.17】证明题图三图均非平面。
(a)内层五点之间的十条边全部存在,直接含 子图,所以非平面。它不是前面仅有五条内星边的彼得松图;本题的内层还多出了其余五条边,不可套错图。
(b)删去 后, 的度变为2,消去这两点,以路径 替换为边 ,以路径 替换为边 。剩余六个分支点可分为 与 ;两部之间的九条连接路径分别为 ,,。内部中转点互不重复,故得到 的细分,原图非平面。
(c)取两部 与 ,跨部九条边完整存在。删除外围的 后即为 ,所以原图非平面。原图共6点12边,不把曲线交叉增算为顶点。
【8.18】上一题哪些图是极小非平面图?
三个都不是。(a)任删一条外围五边形边,内层 完整保留;(b)删掉 后仍含刚给出的 细分;(c)删掉任一外围三角形边,跨部 仍完整保留。每图找到一条“删后仍非平面”的边,就足以否定极小性,不需要声称所有边删后都非平面。
【8.19】画出全部非同构的六阶连通简单非平面图。
共有13种。前十种是在 上加边所得的全部十种,新增边只能位于原两部各自内部。按两部新增边数的无序对,依次为 。图中虚线为新增边,实线为原来的九条跨部边。
另有三种不包含 子图的六阶图:
完整性证明:六阶非平面图必含 或 的细分。 已占用六点,故其细分只能就是 ,得到上述十个超图。若含五点 子图,第六点为保持连通至少与原五点中的一点相邻;邻接数为1、2时给出第12、13种,为3至5时已含 ,归入前十种。
剩下只可能是把 的一条边 细分成 ,占用全部六点。若没有额外边,就是第11种。若补回 ,就回到含 子图的情形;若给 连接原来另外三点中的任一点 ,则以 与“及另外两点”为两部,跨部九边全部存在,又归入前十种。因此没有遗漏。十三图的度序列也互不相同,所以没有重复。对全部112种六阶连通简单图的独立枚举,非平面者也恰为这13种。
【8.20】求题图三种平面嵌入的对偶图。
下面分别画原图和对偶图;对偶图已单独重排位置,不是叠加在原图上的穿边示意。 表示外部面的对偶点, 为方形或三角形内部面的对偶点, 为原自环内部面或双边透镜面的对偶点。每条原边仍只对应一条对偶边。
(a)方形四边分别给出四条 边,原环给出 桥,树叶边给出 上的环。对偶共3点6边,度数分别为 ,对应原图面次数;自环对 的度贡献2。
(b)上、右、下三边给出三条 边;两条左曲线分别给出 和 。对偶3点5边,度数为 。两条平行原边之间确有一个2次面,不能把它们合成一条。
(c)三角形给出三条 边,原环给出 桥,两分支中的两条桥各给出 上的一个环。对偶共3点6边,度数 ,仍连通。原图 ,对偶面数为 ,不可错用连通原图的 。
【8.21】两个同构原图的对偶也同构吗?
不一定,这两幅就是反例。两原图都有7点8边3面。未计树叶时,两方形的外边界次数为6,两个内面次数各4;树叶在某面内会使该面次数增加2。因此(a)的面次数为 ,对偶度序列为 ;(b)为 ,对偶度序列为 ,不同构。两图中共享的中间边对应一条 边,左右各三条外围边分别给出三重的 与 边。
【8.22】证明非连通原图的对偶计数定理8.4.2。
构造给出 。对偶总连通,故 ;由原图 ,得到 。一个面边界的每一次边侧关联对应其对偶点的一次边端关联;桥的两侧在同一面,给出对偶环的两个边端。因此 ,对多条边界行走的同一个面也成立。
【8.23】验证轮图 自对偶。
有6点10边6面; 有7点12边7面。令外圈点为 、中心为 ,内部三角面为 ,下标分别模5、模6。原外圈边的对偶连接 ,原辐条 的对偶连接 。所以 构成同长度外圈, 为新中心,映射 保持所有邻接关系,确为图同构,不只是点数、边数相同。
【8.24】 阶 边自对偶平面图满足 。
自对偶图同构于连通的对偶图,所以原图也连通。又有 ,代入 ,即得 。不能在没有说明连通性时直接代入连通欧拉公式。
【8.25】 的极大平面图,其对偶是2边连通的3正则图。
极大平面图为简单连通图,每个面次数为3,所以每个对偶点度为3,得到3正则性。对偶总连通;原图没有自环,而原自环与对偶桥相对应,因此对偶没有桥。连通且删任一边仍连通,正是2边连通。这里说的是边连通,不能直接用它替代“无割点”的点连通结论。
【8.26】对偶图为欧拉图,当且仅当原图每个面次数均为偶数。
对偶图连通。有限连通无向多重图有欧拉回路,当且仅当全部顶点度为偶数;由 ,结论立即成立。原图的外部面也必须检查;若其边界有多条闭合行走,则先把这些长度相加得到整个面的次数。对偶自环贡献度2,不破坏奇偶性。
【8.27】什么时候原图 与二次对偶 一定不同构?
对顶点集非空的图,沿用第一次对偶构造所给的平面嵌入继续取对偶时,当且仅当 不连通。设 有 个分支,则 连通, 也连通,且
若 ,二次对偶的点数严格少于原图,连通分支数也不同,故一定不同构。若 ,可将每个原顶点对应到围绕它的对偶面;每条原边 对应二次对偶边 ,端点关联恢复,所以二次对偶与原图自然同构,环和桥的两次互换也恢复原状。若中途把抽象图 另作任意重新嵌入,再取另一个对偶,必须重新说明选择的嵌入,不能混用这一结论。
