8.3 平面图的判断
本章目录 · 1 节
本章导读
【定义8.3.1:细分边、消去2度顶点与同胚】在边 上插入新顶点 ,就是删去这条边,改用两条边 ;新点 的度为2,这称为细分一条边。反向操作是:若 的两条关联边连接到 ,删去 及这两条边,补回一条 ,称消去2度顶点。若两个图同构,或经有限次这两种操作后同构,就称它们同胚。
细分只是在一条原边中间加入中转点,顶点数和边数都增加1,原有分支关系不变。消点时必须保留边的身份;若两点之间已存在另一条边,操作会产生平行边,不能擅自把两条边当成一条删掉。判定可平面性时,这些细分与逆操作都保持结论不变。
圈的长度改变了,但可通过细分和消点变成三角形。这是同胚,不是同构:同构要求原图顶点数、边数已经相同。
图(b)有7点9边,四个分支顶点的度为3,其余三个点的度为2。斜线中间一点、右侧曲线上两点都是实际顶点;将它们消去后,四个分支点之间恰有六条边,得到 。不能把曲线靠近其他点的地方误看成连接。
【定理8.3.1:库拉托夫斯基定理,同胚子图判定】图 可平面,当且仅当它既不含与 同胚的子图,也不含与 同胚的子图。等价地,非平面图必含这两个图之一的某个细分作为子图。
必须检查“子图”,不能只检查 本身能否消点变成 或 :应先选出需要的顶点、边,再在所选子图内识别2度中转点。一个顶点在整个 中度数较高,也可能在所选子图中只保留两条边。反过来,只找到一个任意有交叉的子图,并不足以作为非平面证据。
从基本非平面图细分而得的图仍非平面,且非平面图的母图仍非平面,解释了这个判据的必要方向;“任何非平面图必有这样的子图”是其深刻的另一方向,完整证明超出本节范围,不能用一个例子代替定理证明。
【定理8.3.2:收缩形式的判定】 可平面,当且仅当它既不含 小图,也不含 小图。这里“小图”指先取子图,再做有限次边收缩所得的图;教材表述为“没有可以收缩到 或 的子图”。
收缩边 是把其两个端点合成一个点,原来接到任一端的其他边改接到合并后的点;它不同于只删边,也不同于只消去2度点。收缩可产生自环或重边,在讨论简单小图时可以再删去环、去掉多余平行边。不能随意合并两个不相邻顶点并称之为边收缩。两种判据的证据形式不同:前者给细分子图,后者给收缩序列。
【例8.3.1】证明彼得松图非平面。
【解】图中外圈为 ,内星为 ,五条辐条为 。每个顶点度为3,这些标号决定下面删边、收缩的确切位置。
第一种方法:同时收缩五条互不相接的辐条 ,将合并后的点仍记为 。外圈保留 ,内星变成 ,这十条边正好覆盖五点的全部两两组合,没有少边或重复边,所得图就是 。由收缩判据,原图非平面。
第二种方法:从原图删去 与 两条边,得到下图,余下10点13边。这里删的是 ,不是 或 ;删错一条,后面的分支关系就会改变。
此时 恰为四个2度中转点,其余 为六个3度分支点。取两部 、,对应九条连接路径为:从 到另一部用 ;从 用 ;从 用 。九条路径的内部顶点彼此不重合,消去四个中转点后恰成 ,所以原图也由同胚子图判据得证非平面。
【例8.3.2】从 出发,或在一条边上插入一个2度点,或另加一个点使其与原图若干点相邻,这两类操作一共得到多少种非同构的6阶简单连通非平面图?
【解】第一类仅一种。由于 的任意边可经顶点置换互换位置,细分哪条边都得到同构的图。新图有6点11边,度序列为 ;消去新点即可恢复 ,所以非平面。
第二类中,新点 要保证连通,必须与 的 个顶点相邻。 内任意同样大小的邻接点集可由置换互换,所以每个 只有一种同构类型,共五种。它们仍完整包含 子图,因而都非平面。
第二类的五个图边数分别为11至15,互不同构。唯一需要再比较的是两个11边图:第二类 有一个度1点和一个度5点,度序列为 ,不同于第一类,因此合计 种。这只是题目限定的两种构造所得到的六种,不能误读为“所有6阶简单连通非平面图一共只有六种”。
【例8.3.3】在 的同一个六顶点集上加若干条简单边,连同不加边的情形,共有多少种非同构图?
【解】所有所得图均包含原来的 ,因此都非平面且连通。原图的两部各有3点,跨部的9条边已全部存在,可加边只在各部内部:每部最多3条,总共6条。下面实线始终为原来的9条边,虚线才是新增边;没有圆点的线段交叉仍不产生顶点。
为了说明枚举为何完整,考察每部内部形成的三顶点简单图:0边为空图;1边为一条边及一个孤立点;2边为三顶点路径;3边为三角形。每个边数对应唯一一种同构类型。允许在各部内任意置换顶点,并允许交换两部,所以只需列出两部新增边数的无序对 ,其中 。共有 对。
还须排除不同无序对在更一般的顶点置换下意外同构。将各部内部的度都加上原来的跨部度3,可得图(a)至(j)的有序排列后的度序列依次为:
;;;;;;;;;。十个序列互不相同,故十图确实互不同构。
按新增边数0至6分组,同构类型数为 ,合计10。尤其新增2、3、4条边时各有两种,应分别保留,不能仅按“总边数相同”把它们合成一种;同样也不要把原图遗漏。这里列举的是包含一个跨部完全连接的 的这些超图,并未宣称覆盖所有六顶点非平面图。
