习题8

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【习题8:读图和计数约定】本组保留教材8.1至8.27的顺序。图中只有圆点是顶点,无圆点的交叉不增加顶点;曲线和直线按端点确定边,平行边分别编号。面边界按闭合行走记录,桥在同一面的边界上经过两次。下面的平面嵌入只改变画法,原来的顶点、边和关联关系保持不变。

【8.1】证明题8.1图中的三个图都是平面图。

abcdef
题8.1(a):六点八边;中心交叉不是顶点
abcde
题8.1(b):上方曲线是一条完整边
abcdef
题8.1(c):六点九边;交叉点不添圆点

解:(a)的两部为 与 ,跨部边中仅缺 ,是 删去一条边所得的图。把 放在上下两端, 分别置于三条两边通路的中间,再把 放在 之间并连到二者,得到下一题的无交叉嵌入。

(b)为 删去 的图,有5点9边,可以重画成所有面均为三角形的平面嵌入。(c)由两个三角形 与 ,加三条匹配边 组成,是三棱柱的骨架图。把两个三角形一外一内放置,依次连接相应点即可。下面三幅无交叉图给出具体构造,所以证明不依赖“边数没有超过上界”这一必要条件。

【8.2】分别给出上一题三图的平面嵌入,并验证面次数之和等于边数两倍。

abcdef
题8.2(a):与题8.1(a)同一顶点标号、同一八条边

(a)有4个面,每个面次数为4,故 ,且 。中间的 是两个不同顶点,不能把它们合并。

题8.2(b):五点九边的无交叉嵌入

(b)有6个三角面,次数和为 ,且 。

abcdef
题8.2(c):三棱柱的平面嵌入

(c)有2个三角面、3个四边面,包括外部面,次数和为 ,且 。内外三角形各自的三个点以及三条连接边都完整保留。

【8.3】给三个平面嵌入的边编号,求所有面的边界和次数。

以下边界序列按图中 记录,可整体反向或循环换起点,但不得把重复出现的桥去重。

e1e2e3e4e5e6e7e8
题8.3(a):八条边已分别标号

(a)三个内部面的边界可取 、、,次数依次为3、3、4;外部面边界为 ,次数6。总和 。

e1e2e3e4e5e6e7e8
题8.3(b):e6是环;e7、e8为连续的两条桥

(b)三个内部面的边界为 、、,次数3、3、1。外部面边界可取 ,次数9。每条桥都往返一次,环的外侧还在外部面中出现一次,故 。

e1e2e3e4e5e6e7e8
题8.3(c):两个连通分支共用一个外部面

(c)内部方形面的边界为 ,次数4;环围出的内部面为 ,次数1。唯一外部面有两条边界行走:,长5;,长6。外部面的次数为 ,总和 。这里有8点8边2个分支3个面,。

【8.4】把题8.3(a)重画,使外部面次数分别为3和4。

题8.4第一种嵌入:外部边界为原图e1、e5、e6构成的三角形

保留原图全部6点8边,将原来的屋顶三角面作为外部面,其他顶点和边放到它内部。外部边界为 ,次数3;其他面的次数为3、4、6。

题8.4第二种嵌入:原图四边面成为外部面

将原来的方形面作为外部面,屋顶点和右侧附加点都移入该方形内。外部边界由 构成,次数4;其他面的次数为3、3、6。两图的面次数多重集同为 ,只是选择了不同的外部面,没有删边或添点。

【8.5】求题8.5图所有面的边界和次数。

abcdefg
题8.5:七个顶点、六条边的树

此图是一棵树,只有一个面。其边界可写为顶点行走 ,长度为12。每条边恰好往返一次,故面次数为 ,不是6。树枝所围出的视觉空隙不是新的有界面。

【8.6】证明定理8.1.4:极大平面图连通,阶数至少3时无割点、无桥。

若有两个不同分支,可重画后在两个分支外部面上的顶点间加边,仍无交叉,违背极大性。若有割点 ,在其周围取进入两个不同分支且局部相邻的两条边 ,则 原先不存在,否则两分支可绕过 连通。沿这两条边旁的小邻域补边 ,仍可平面,再次违背极大性。最后,至少3点的连通图若有桥,其至少一个端点必为割点,因此无桥。 的唯一边是桥,所以“至少3点”的限制必须保留。

【8.7】证明题图中两图都是极大平面图。

原画法中若有无圆点交叉,不据此添顶点,先保留关联关系重画。

题8.7(a)原关联图:六点十二边
题8.7(a)的平面嵌入:八个面全部为三角形

(a)的 ,八个面均为三角形,且 ,故为极大平面图。

题8.7(b)原关联图:八个外围点及一个中央圆点,共九点
题8.7(b)的平面嵌入:十四个三角面

(b)中央圆点是实际顶点,与其相接的线段要分别计边;无圆点的其余交叉不算顶点。正确计数为 。重画后包括外部面在内的14个面都为三角形,且 ,故也极大。不能误按八顶点图套边数界。

【8.8】验证 和 是极小非平面图。

两图均非平面。 的任意边可由顶点置换移到同一位置,所以只须展示删一条代表边后可平面; 的各边也在保两部的顶点置换下等价,同样只须一个代表。

题8.8:K5删去一条边后的平面嵌入,五点九边
题8.8:K3,3删去一条边后的平面嵌入,六点八边

两幅无交叉图分别给出证据,故两图都满足“删掉任意一条边即变为平面图”,是极小非平面图。极小不是要求删顶点,也不是仅检查某一条边会使图变平面。

【8.9】题图是极小非平面图吗?

abcde
题8.9:五个实际顶点,d与e之间有两条不同的边

不是。图有5点11边, 有两条平行边;任选删去其中一条,剩下的十条边恰构成五点的 ,仍非平面。因此它连“删任意边后都可平面”的要求都不满足。中央圆点 分开 和 ,外侧另有 ,不可把穿过 的两段擅自合成同一条边,也不能丢掉平行边。

【8.10】验证两幅平面嵌入满足欧拉公式。

题8.10(a):立方体骨架的平面嵌入

(a)外方形、内方形各4点,各有4边,另有4条对应连接边,故 。有4个侧方形面、一个内部方形面、一个外部方形面,故 ,;面次数之和 。

题8.10(b):六点十二边的平面嵌入,外侧三条曲线各自是一条边

(b)六个圆点之间共有12条边,8个面均为三角形,故 ,,且 。曲线上靠近其他点的位置不是新的端点。

【8.11】验证题图的非连通欧拉公式。

ABC
题8.11:A、B、C是同一个非连通平面图的三个分支

三个部分合起来计数,不能将每部分各自的外部面相加。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,则由面握手定理 ;由顶点握手定理和最小度条件,。允许原图不连通,设有 个分支,使用推广欧拉公式得

所以 ,与条件矛盾。这一证明没有偷偷增加“图连通”的前提。

题8.14反例:正十二面体骨架的平面嵌入,二十点三十边十二个五边面

当 ,取正十二面体骨架图:,每个顶点度为3,全部12个面次数均为5,包括外部面,所以不存在次数不超过4的面,正好说明严格不等号不可放宽。

【8.15】简单平面图 ,证明 。

反设每点度至少5,则 ,且此时 ,可以使用 。于是 ,从而 ,矛盾。故至少有一点度不超过4。这里讨论非空顶点集,空图不定义最小度。

【8.16】 的简单图 与补图 至少一个非平面。

若二者都可平面,则边数之和满足 ,即 。然而在 时左侧为2,此后每把 增加1,该式增加 ,所以对所有 都为正,矛盾。只是假定两图均简单平面,并未要求它们连通。

【8.17】证明题图三图均非平面。

abcdefghij
题8.17(a):内层五个顶点f、g、h、i、j之间是完整K5

(a)内层五点之间的十条边全部存在,直接含 子图,所以非平面。它不是前面仅有五条内星边的彼得松图;本题的内层还多出了其余五条边,不可套错图。

abcdefgh
题8.17(b):外方形、内方形与下方交叉连接
abcdefgh
题8.17(b)的证据子图:删去上方ab,保留其余十一条边

(b)删去 后, 的度变为2,消去这两点,以路径 替换为边 ,以路径 替换为边 。剩余六个分支点可分为 与 ;两部之间的九条连接路径分别为 ,,。内部中转点互不重复,故得到 的细分,原图非平面。

abcdef
题8.17(c):外围a、b、c与内层d、e、f完全跨部连接,另外有外围三条边

(c)取两部 与 ,跨部九条边完整存在。删除外围的 后即为 ,所以原图非平面。原图共6点12边,不把曲线交叉增算为顶点。

【8.18】上一题哪些图是极小非平面图?

三个都不是。(a)任删一条外围五边形边,内层 完整保留;(b)删掉 后仍含刚给出的 细分;(c)删掉任一外围三角形边,跨部 仍完整保留。每图找到一条“删后仍非平面”的边,就足以否定极小性,不需要声称所有边删后都非平面。

【8.19】画出全部非同构的六阶连通简单非平面图。

共有13种。前十种是在 上加边所得的全部十种,新增边只能位于原两部各自内部。按两部新增边数的无序对,依次为 。图中虚线为新增边,实线为原来的九条跨部边。

题8.19第1种:K3,3,九条边
题8.19第2种:新增边数(0,1),十条边
题8.19第3种:新增边数(1,1),十一条边
题8.19第4种:新增边数(0,2),十一条边
题8.19第5种:新增边数(0,3),十二条边
题8.19第6种:新增边数(1,2),十二条边
题8.19第7种:新增边数(1,3),十三条边
题8.19第8种:新增边数(2,2),十三条边
题8.19第9种:新增边数(2,3),十四条边
题8.19第10种:K6,十五条边

另有三种不包含 子图的六阶图:

题8.19第11种:细分K5的一条边,度序列(2,4,4,4,4,4)
题8.19第12种:在K5外附一个度1点,度序列(1,4,4,4,4,5)
题8.19第13种:新点与K5的两个点相邻,度序列(2,4,4,4,5,5)

完整性证明:六阶非平面图必含 或 的细分。 已占用六点,故其细分只能就是 ,得到上述十个超图。若含五点 子图,第六点为保持连通至少与原五点中的一点相邻;邻接数为1、2时给出第12、13种,为3至5时已含 ,归入前十种。

剩下只可能是把 的一条边 细分成 ,占用全部六点。若没有额外边,就是第11种。若补回 ,就回到含 子图的情形;若给 连接原来另外三点中的任一点 ,则以 与“及另外两点”为两部,跨部九边全部存在,又归入前十种。因此没有遗漏。十三图的度序列也互不相同,所以没有重复。对全部112种六阶连通简单图的独立枚举,非平面者也恰为这13种。

【8.20】求题图三种平面嵌入的对偶图。

下面分别画原图和对偶图;对偶图已单独重排位置,不是叠加在原图上的穿边示意。 表示外部面的对偶点, 为方形或三角形内部面的对偶点, 为原自环内部面或双边透镜面的对偶点。每条原边仍只对应一条对偶边。

题8.20(a)原图:方形、一个自环和一条树叶边
R0R1R2
题8.20(a)对偶:R0与R1间四条平行边,R0到R2一条桥,R0上一个环

(a)方形四边分别给出四条 边,原环给出 桥,树叶边给出 上的环。对偶共3点6边,度数分别为 ,对应原图面次数;自环对 的度贡献2。

题8.20(b)原图:左侧两条曲线是不同的平行边
R0R1R2
题8.20(b)对偶:R0与R1间三条平行边,另外两边连接透镜面点R2

(b)上、右、下三边给出三条 边;两条左曲线分别给出 和 。对偶3点5边,度数为 。两条平行原边之间确有一个2次面,不能把它们合成一条。

题8.20(c)原图:两个分支,共用一个外部面
R0R1R2
题8.20(c)对偶:三条R0R1边、一条R0R2边、R0上两个不同自环

(c)三角形给出三条 边,原环给出 桥,两分支中的两条桥各给出 上的一个环。对偶共3点6边,度数 ,仍连通。原图 ,对偶面数为 ,不可错用连通原图的 。

【8.21】两个同构原图的对偶也同构吗?

题8.21(a):树叶边画在左方形内部
R0R1R2
题8.21(a)对偶:环附在左方形面的点R1上
题8.21(b):同一条树叶边画在外部
R0R1R2
题8.21(b)对偶:环改附在外部面点R0上

不一定,这两幅就是反例。两原图都有7点8边3面。未计树叶时,两方形的外边界次数为6,两个内面次数各4;树叶在某面内会使该面次数增加2。因此(a)的面次数为 ,对偶度序列为 ;(b)为 ,对偶度序列为 ,不同构。两图中共享的中间边对应一条 边,左右各三条外围边分别给出三重的 与 边。

【8.22】证明非连通原图的对偶计数定理8.4.2。

构造给出 。对偶总连通,故 ;由原图 ,得到 。一个面边界的每一次边侧关联对应其对偶点的一次边端关联;桥的两侧在同一面,给出对偶环的两个边端。因此 ,对多条边界行走的同一个面也成立。

【8.23】验证轮图 自对偶。

题8.23:W6,五个外围点加一个中心点
T0T1T2T3T4R0
W6的对偶重排:五个内部面点成圈,R0连接它们
题8.23:W7,六个外围点加一个中心点
T0T1T2T3T4T5R0
W7的对偶重排:六个内部面点成圈,R0连接它们

有6点10边6面; 有7点12边7面。令外圈点为 、中心为 ,内部三角面为 ,下标分别模5、模6。原外圈边的对偶连接 ,原辐条 的对偶连接 。所以 构成同长度外圈, 为新中心,映射 保持所有邻接关系,确为图同构,不只是点数、边数相同。

【8.24】 阶 边自对偶平面图满足 。

自对偶图同构于连通的对偶图,所以原图也连通。又有 ,代入 ,即得 。不能在没有说明连通性时直接代入连通欧拉公式。

【8.25】 的极大平面图,其对偶是2边连通的3正则图。

极大平面图为简单连通图,每个面次数为3,所以每个对偶点度为3,得到3正则性。对偶总连通;原图没有自环,而原自环与对偶桥相对应,因此对偶没有桥。连通且删任一边仍连通,正是2边连通。这里说的是边连通,不能直接用它替代“无割点”的点连通结论。

【8.26】对偶图为欧拉图,当且仅当原图每个面次数均为偶数。

对偶图连通。有限连通无向多重图有欧拉回路,当且仅当全部顶点度为偶数;由 ,结论立即成立。原图的外部面也必须检查;若其边界有多条闭合行走,则先把这些长度相加得到整个面的次数。对偶自环贡献度2,不破坏奇偶性。

【8.27】什么时候原图 与二次对偶 一定不同构?

对顶点集非空的图,沿用第一次对偶构造所给的平面嵌入继续取对偶时,当且仅当 不连通。设 有 个分支,则 连通, 也连通,且

若 ,二次对偶的点数严格少于原图,连通分支数也不同,故一定不同构。若 ,可将每个原顶点对应到围绕它的对偶面;每条原边 对应二次对偶边 ,端点关联恢复,所以二次对偶与原图自然同构,环和桥的两次互换也恢复原状。若中途把抽象图 另作任意重新嵌入,再取另一个对偶,必须重新说明选择的嵌入,不能混用这一结论。