8.3 平面图的判断

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【定义8.3.1:细分边、消去2度顶点与同胚】在边 上插入新顶点 ,就是删去这条边,改用两条边 ;新点 的度为2,这称为细分一条边。反向操作是:若 的两条关联边连接到 ,删去 及这两条边,补回一条 ,称消去2度顶点。若两个图同构,或经有限次这两种操作后同构,就称它们同胚。

细分只是在一条原边中间加入中转点,顶点数和边数都增加1,原有分支关系不变。消点时必须保留边的身份;若两点之间已存在另一条边,操作会产生平行边,不能擅自把两条边当成一条删掉。判定可平面性时,这些细分与逆操作都保持结论不变。

图8.3.1(a):七个2度顶点构成的圈,与K3同胚

圈的长度改变了,但可通过细分和消点变成三角形。这是同胚,不是同构:同构要求原图顶点数、边数已经相同。

图8.3.1(b):K4的两条边被细分,仍与K4同胚

图(b)有7点9边,四个分支顶点的度为3,其余三个点的度为2。斜线中间一点、右侧曲线上两点都是实际顶点;将它们消去后,四个分支点之间恰有六条边,得到 。不能把曲线靠近其他点的地方误看成连接。

【定理8.3.1:库拉托夫斯基定理,同胚子图判定】图 可平面,当且仅当它既不含与 同胚的子图,也不含与 同胚的子图。等价地,非平面图必含这两个图之一的某个细分作为子图。

必须检查“子图”,不能只检查 本身能否消点变成 或 :应先选出需要的顶点、边,再在所选子图内识别2度中转点。一个顶点在整个 中度数较高,也可能在所选子图中只保留两条边。反过来,只找到一个任意有交叉的子图,并不足以作为非平面证据。

从基本非平面图细分而得的图仍非平面,且非平面图的母图仍非平面,解释了这个判据的必要方向;“任何非平面图必有这样的子图”是其深刻的另一方向,完整证明超出本节范围,不能用一个例子代替定理证明。

【定理8.3.2:收缩形式的判定】 可平面,当且仅当它既不含 小图,也不含 小图。这里“小图”指先取子图,再做有限次边收缩所得的图;教材表述为“没有可以收缩到 或 的子图”。

收缩边 是把其两个端点合成一个点,原来接到任一端的其他边改接到合并后的点;它不同于只删边,也不同于只消去2度点。收缩可产生自环或重边,在讨论简单小图时可以再删去环、去掉多余平行边。不能随意合并两个不相邻顶点并称之为边收缩。两种判据的证据形式不同:前者给细分子图,后者给收缩序列。

【例8.3.1】证明彼得松图非平面。

abcdefghij
图8.3.2(a):彼得松图,10点15边;无圆点的交叉不是顶点

【解】图中外圈为 ,内星为 ,五条辐条为 。每个顶点度为3,这些标号决定下面删边、收缩的确切位置。

第一种方法:同时收缩五条互不相接的辐条 ,将合并后的点仍记为 。外圈保留 ,内星变成 ,这十条边正好覆盖五点的全部两两组合,没有少边或重复边,所得图就是 。由收缩判据,原图非平面。

abcde
图8.3.2(b):收缩五条辐条后得到K5

第二种方法:从原图删去 与 两条边,得到下图,余下10点13边。这里删的是 ,不是 或 ;删错一条,后面的分支关系就会改变。

abcdefghij
图8.3.2(c):删去jg和cd,得到K3,3的细分

此时 恰为四个2度中转点,其余 为六个3度分支点。取两部 、,对应九条连接路径为:从 到另一部用 ;从 用 ;从 用 。九条路径的内部顶点彼此不重合,消去四个中转点后恰成 ,所以原图也由同胚子图判据得证非平面。

【例8.3.2】从 出发,或在一条边上插入一个2度点,或另加一个点使其与原图若干点相邻,这两类操作一共得到多少种非同构的6阶简单连通非平面图?

【解】第一类仅一种。由于 的任意边可经顶点置换互换位置,细分哪条边都得到同构的图。新图有6点11边,度序列为 ;消去新点即可恢复 ,所以非平面。

图8.3.3(a):细分K5的一条边,边上的新增圆点是第六个顶点

第二类中,新点 要保证连通,必须与 的 个顶点相邻。 内任意同样大小的邻接点集可由置换互换,所以每个 只有一种同构类型,共五种。它们仍完整包含 子图,因而都非平面。

图8.3.3(b):新点接原图1点,6点11边
图8.3.3(c):新点接原图2点,6点12边
图8.3.3(d):新点接原图3点,6点13边
图8.3.3(e):新点接原图4点,6点14边
图8.3.3(f):新点接原图5点,得到K6,6点15边

第二类的五个图边数分别为11至15,互不同构。唯一需要再比较的是两个11边图:第二类 有一个度1点和一个度5点,度序列为 ,不同于第一类,因此合计 种。这只是题目限定的两种构造所得到的六种,不能误读为“所有6阶简单连通非平面图一共只有六种”。

【例8.3.3】在 的同一个六顶点集上加若干条简单边,连同不加边的情形,共有多少种非同构图?

【解】所有所得图均包含原来的 ,因此都非平面且连通。原图的两部各有3点,跨部的9条边已全部存在,可加边只在各部内部:每部最多3条,总共6条。下面实线始终为原来的9条边,虚线才是新增边;没有圆点的线段交叉仍不产生顶点。

为了说明枚举为何完整,考察每部内部形成的三顶点简单图:0边为空图;1边为一条边及一个孤立点;2边为三顶点路径;3边为三角形。每个边数对应唯一一种同构类型。允许在各部内任意置换顶点,并允许交换两部,所以只需列出两部新增边数的无序对 ,其中 。共有 对。

图8.3.4(a):新增边数(0,0),原来的K3,3
图8.3.4(b):新增边数(0,1),共加1边
图8.3.4(c):新增边数(1,1),两部各加1边
图8.3.4(d):新增边数(0,2),在同一部内加2边
图8.3.4(e):新增边数(0,3),一部成为三角形
图8.3.4(f):新增边数(1,2),共加3边
图8.3.4(g):新增边数(1,3),共加4边
图8.3.4(h):新增边数(2,2),两部各为三点路径
图8.3.4(i):新增边数(2,3),共加5边
图8.3.4(j):新增边数(3,3),加满6边,得到K6

还须排除不同无序对在更一般的顶点置换下意外同构。将各部内部的度都加上原来的跨部度3,可得图(a)至(j)的有序排列后的度序列依次为:

;;;;;;;;;。十个序列互不相同,故十图确实互不同构。

按新增边数0至6分组,同构类型数为 ,合计10。尤其新增2、3、4条边时各有两种,应分别保留,不能仅按“总边数相同”把它们合成一种;同样也不要把原图遗漏。这里列举的是包含一个跨部完全连接的 的这些超图,并未宣称覆盖所有六顶点非平面图。