8.1 平面图的基本概念

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【定义8.1.1:可平面性与平面嵌入】无向图能够画在平面上,使边只在其公共端点相遇、其他位置不相交,称可平面图,简称平面图;这样画出的具体无交叉图形称平面嵌入。不存在任何平面嵌入者称非平面图。

应区分图本身和某一次画法:画面上有交叉,并不能证明图非平面,可能只需重新安排顶点、把边改成曲线。反过来,无圆点的交叉不是自动增加一个顶点,若人为在那里添点,就已经改变原图。以下重画始终保留原来的顶点、边与关联关系。

图8.1.1(a):K4的一种有交叉画法
图8.1.1(d):同一K4的平面嵌入,外侧曲线是一条完整边

都可平面,前三者的通常画法已经无交叉。图(a)、(d)都只有4点6边;外侧曲线不经过右上顶点,不可把曲线看作分段连到那个点。

图8.1.1(b):K5删一条边后的通常画法
图8.1.1(e):同一个五顶点九边图的平面嵌入

也可平面, 表示任取一条被删边。两个图各有5点9边,只改变画法;弯曲的三条边各自仍只算一条。

图8.1.1(c):K2,3的通常画法
图8.1.1(f):K2,3的平面嵌入,三条两段路径共用上下端点

完全二部图 是星,当然可平面; 也可把两个部中的两点作为共同端点,其余各点分别放在互不相交的两边路径上,故可平面, 如图。非平面性的两个基本例子为 与 ,其证明将在8.2的边数界中给出,不应把它们与前面的可平面例图混淆。

【定理8.1.1:对子图的封闭性】平面图的任意子图仍为平面图;非平面图的任意母图仍为非平面图。前者直接在原嵌入中删除不用的边和顶点,交叉不会凭空出现;后者取逆否命题即可。因而 以及 的所有子图都可平面;包含 或 作为子图的图不可平面,特别是 与 。

【定理8.1.2:加重边和环不改变可平面性】对已有平面嵌入,在一条边旁的细窄区域中画一条平行边,或在某顶点旁不含其他边的小区域内画自环,仍不会与其他边交叉。反向删去这些边当然也不破坏可平面性。所以研究是否可平面时可先忽略环和重复边;但研究面数、面的次数时必须把它们补回,不能认为它们对所有数量都没有影响。

【定义8.1.2:面、边界、次数】固定一个平面嵌入后,图把平面分成若干连通区域,称面。唯一无界者为外部面 ,其余为内部面 。同一外部面可以绕着多个不相交的图分支,不会因图分支多就变成多个外部面。

一个面的边界由一个或多个闭合边界行走构成,面次数 按边在边界行走中出现的次数计算,不能先把边去重。边界未必是圈:可能重复顶点,也可能重复边;桥两侧属于同一面,所以同一条桥要在该面的边界上计算两次。一个环可以独自围成次数1的面。

abcdefghijklR1R2R3R4R0
图8.1.2:两个分支、五个面;a至l是边号,不是顶点名称

这幅图有10个顶点、12条边、2个连通分支、5个面。按图中字母边号, 的边界依次为 ,次数4; 为 ,次数3; 为环 ,次数1; 为 ,次数3。

外部面有两条边界行走:左分支为 ,长7;右分支为 ,长6。桥 在后一行走中走了两次,环 的外侧出现一次。因此 ,不能把桥只计一次而误得12。这里序列给的是边号,不是“相邻字母组成顶点对”。

【定理8.1.3:面次数握手定理】全部面的次数之和为 。把每条边看成有两个侧面:若两侧分别属于不同面,它在两个面中各计一次;若两侧属于同一面,它在该面边界中计两次。环、平行边和桥都依此计算。图8.1.2给出 ,与全部12条边逐一计两侧一致。

【定义8.1.3:极大平面图】简单平面图若在固定顶点集上,任意两不相邻顶点之间再添一条边就不可平面,称极大平面图。教材把 明列其中;它们已经没有可加的简单边。 也为极大平面图,唯一缺边一旦加回就成为非平面的 。这里不能通过不断加平行边、加自环来讨论“极大”,定义已限定简单图。

【定理8.1.4:极大平面图的连通性】极大平面图必连通;阶数至少3时没有割点或桥。若不连通,可把两个分支摆开放置,再连接各自外部面上的一个顶点,仍可平面,矛盾。若有割点 ,绕 取分别进入两个不同分支、在局部相邻的两条边,其另一端 不可能原来相邻;可以沿这两边旁边的狭窄区域加 ,仍无交叉,再次矛盾。简单连通图至少3点时,一条桥必使其至少一个端点成为割点,故也没有桥。

【定理8.1.5:三角剖分的判定】 的简单连通平面图为极大平面图,当且仅当其每个面的次数都是3,包括外部面。

必要性:由上一定理,极大平面图没有割点,其面边界是简单圈。若有边界长至少4的面,取边界上依次出现的四点 。若 不存在,可在面内加边,违背极大性;因此它必已在此面外。同理 也必在面外。两条连接交替端点的外部边必须相交,与平面嵌入矛盾,因此面只能为三角形。

v1v2v3v4R×
图8.1.3:取四个交替端点示意反证;左侧×不是顶点,此图不是平面嵌入

图中故意把两条假设的面外连接画成交叉,以呈现矛盾,不能把它当成一个正确平面嵌入。对边界更多顶点的面,同样选四个交替端点即可。

充分性在8.2借助欧拉公式完成:若全为三角面, 与 给出 ;再加边会超过简单平面图的边数上界,任何重新画法也无法补救,故已经极大。仅说“眼前这个画法无处加边”还不够,因为可平面性允许重画,须用这个对所有画法都成立的上界。

abcdef
图8.1.4(a):六顶点十一边,仍有一个四边面

为说明方便补上顶点名,图(a)中 围成四边面,可在其中加入 ,所以不是极大平面图。

abcdef
图8.1.4(b):内面虽已三角化,外部面仍是四边面

图(b)的外部边界为 ,还可沿左侧外部区域加入 ,故也不是极大平面图。只检查内部面会漏判。

abcdefgh
图8.1.4(c):八顶点十八边,所有面均为三角形

图(c)的三条曲线均为完整的原边,不在经过附近点时自动接上;全部12个面都是三角形,所以三例中只有(c)是极大平面图。

【定义8.1.4:极小非平面图】一个非平面图,若删掉任一条边都会变为可平面图,称极小非平面图。 和 都是例子。这里的极小按删边定义,不等于宣称它们是所有非平面图中顶点数、边数同时最少的两种,也不能反过来说只要某次删边后仍非平面就已经极小;必须检查“任意一条边”。