◆二、平面图的特征 ◆找出一个图是平面图的充分必要条件的 研究曾经持续了几十年,直到1930年库 拉托斯基( Kuratowski)给出了平面图的 一个非常简洁的特征
二、平面图的特征 找出一个图是平面图的充分必要条件的 研究曾经持续了几十年, 直到 1930 年库 拉托斯基 (Kuratowski) 给出了平面图的 一个非常简洁的特征
◆首先介绍剖分的概念: ◆给定图G的一个剖分是对G实行有限次下 述过程而得到的图: ◆删去它的一条边{uy后添加一个新的点 w以及新的边{wu和{w,v} ◆也就是说在G的边上插入有限个点便得 到G的一个剖分。 ◆下图中给出了K的一个剖分
首先介绍剖分的概念： 给定图G的一个剖分是对G实行有限次下 述过程而得到的图: 删去它的一条边{u,v}后添加一个新的点 w以及新的边{w,u}和{w,v}。 也就是说在G的边上插入有限个点便得 到 G的一个剖分。 下图中给出了K5的一个剖分
◆定理:(1)若图G的一个子图是Kn的剖分 则G中至少有n个顶点度数大于等于n1; ◆(2)若图G的一个子图是Kn的剖分,则G 中至少有2n个顶点度数大于等于n ◆例:G=(V,E),ⅣV=7,若G中含有K的剖 分,则G不含有K或K3的剖分 ◆定理63(库拉托斯基定理:图G是平面图 当且仅当它的任何子图都不是K或K3 的剖分。 上例中G是非平面图,而G是平面图
定理：(1)若图G的一个子图是Kn的剖分， 则G中至少有n个顶点度数大于等于n-1； (2)若图G的一个子图是Kn,n的剖分，则G 中至少有2n个顶点度数大于等于n。 例：G=(V,E)，|V|=7，若G中含有K5的剖 分，则 不含有K5或K3,3的剖分. 定理 6.3 (库拉托斯基定理):图G是平面图 当且仅当它的任何子图都不是K5或 K3,3 的剖分。 上例中G是非平面图，而 是平面图 G G
◆此定理告诉我们: ◆(1)一个图是平面图,则不含有K的剖分, 也不含有K3的剖分。 ◆(2)若图G不含有K的剖分,也不含有K33 的剖分。则G一定是平面图。 ◆(3)若图G含有K的剖分,则G一定不是 平面图;若图G含有K3的剖分,则G 定不是平面图 ◆(4)若图G不是平面图,则或者G含有Ks 的剖分,或者G含有K3的剖分
此定理告诉我们： (1)一个图是平面图，则不含有K5的剖分， 也不含有K3,3的剖分。 (2)若图G不含有K5的剖分，也不含有K3,3 的剖分。则G一定是平面图。 (3)若图G含有K5的剖分，则G一定不是 平面图；若图G含有K3,3的剖分，则G一 定不是平面图。 (4)若图G不是平面图，则或者G含有K5 的剖分，或者G含有K3,3的剖分
Q·库拉托斯基定理虽然很漂亮但是在具体 不能起作用。因此以后仍有许多这方面 的研究工作
库拉托斯基定理虽然很漂亮, 但是在具体 判定一个图是不是平面图时,这个定理并 不能起作用。因此以后仍有许多这方面 的研究工作
三、对偶图 定义63:设G是平面图G的平面嵌入,则G的几何对偶G 构造如下 (1)在G的每一个面f内恰放唯一的一个顶点f (2)对G的两个面ff的公共边x作边x*={**;与x相交; 得到图记为G*即G的几何对偶简称G的对偶) 易知,若x是(的一条桥桥的定义见习题513),则G*有一个 自环并且这个自环关联的顶点在x所在面内并规定自环经过 桥一次且仅一次
三、对偶图 定义 6.3：设G ~ 是平面图 G 的平面嵌入, 则 G 的几何对偶 G * 构造如下: (1)在G ~ 的每一个面 f 内恰放唯一的一个顶点 f*; (2)对G ~ 的两个面 fi ,fj的公共边 xk,作边 xk*={fi*,fj*}与 xk相交; 得到图记为 G*,即 G 的几何对偶(简称 G 的对偶)。 易知, 若 x 是G ~ 的一条桥(桥的定义见习题 5.13), 则 G*有一个 自环,并且这个自环关联的顶点在 x 所在面内,并规定自环经过 桥一次且仅一次
例如下图中G的边用实线表示G*的边用红线表示,这一例子 中G就是G。显然G*有多重边当且仅军中存在两个面至少 有两条公共边
例如下图中 G 的边用实线表示,G*的边用红线表示, 这一例子 中G ~ 就是 G。显然 G*有多重边当且仅当G ~ 中存在两个面至少 有两条公共边
◆在这里几何对偶常简称为对偶。 ◆由定义可知若G是连通平面图,则G也 是连通平面图而且G和G的顶点数,面 数和边数有下列简单的关系。 ◆定理64:设G是有n个顶点,e条边f个面 的连通平面图又设G的几何对偶G有n 个顶点,e条边,个面,则n*=f,e=e,=n
在这里几何对偶常简称为对偶。 由定义可知,若G是连通平面图, 则G*也 是连通平面图,而且G和G*的顶点数, 面 数和边数有下列简单的关系。 定理 6.4：设G是有n个顶点,e条边,f个面 的连通平面图;又设G的几何对偶G*有n* 个顶点,e*条边,f*个面,则 n*=f,e*=e,f*=n
同样 E 2 是连 G方单的 D I Ga 图6.5 的任何 两个几何对偶必同构。 又平面图G1与G2同构,但未必G1*与G2 同构。关键是嵌入方式不同
由于平面图G的对偶G*也是平面图, 同样 可对G*作几何对偶,记为G**。若G是连 通的, 则G**与G之间有一个特别简单的 关系, 如下所述。 定理 6.5：G是连通平面图当且仅当 G** 同构于G。 由定义 6.3 的过程可知, 平面图G的任何 两个几何对偶必同构。 又平面图G1与G2同构, 但未必G1 *与 G2 * 同构。关键是嵌入方式不同