8.4 平面图的对偶图
本章目录 · 1 节
本章导读
【定义8.4.1:固定平面嵌入的对偶图】先固定平面图 的一个具体平面嵌入。在每个面 内放置一个顶点 ,外部面同样放置一个点;对原图每条边 ,画一条对应边 ,使它只穿过 一次,不穿过原图其他任何边,并把 两侧面内的点连接起来。所得图记为 ,称这个嵌入的对偶图。
若 的两侧属于同一个面,则 从该面内的点出发并回到它自身,是自环。在平面嵌入中,这种情况恰发生于原图的桥。无论面边界是否重复边,都必须“原图一条边对应对偶图一条边”,不能因为桥在边界中走了两次就画两条对偶边。
读图时,下面绿色实线与空心点为原图,棕色虚线与实心点为对偶图。两层线相交仅表示某条边与它的对偶边相交,不是新增加一个公共顶点;两层图的顶点集合本来不同。虚线转折也不是顶点,只有实心圆点才是对偶顶点。
两个原图都是“正方形加一条对角线,并在左上顶点接一片树叶”,都是5点6边3面,作为抽象图同构。 表示外部面, 为对角线分开的两个内部面。左图把树叶边置于外部面,其面次数为 ;右图把树叶边置于 内,面次数为 。桥所在面的次数多计2,其他原边关系保持不变。
所以左图对偶的度序列为 ,右图为 ,二者不同构。这是“对偶依赖具体平面嵌入”的明确证据:仅给出抽象图的邻接关系,尚不能不加选择地谈唯一一个对偶图。
【注8.4.1:对偶图的五个性质】第一,对偶图仍可平面,而且构造时可使对偶边之间只在共同端点相交。画出的对偶边可以弯折,不要求是直线;它们与原边相交是定义要求,不影响对偶图自身的平面性。
第二,对偶图总连通,即使原图不连通也一样。取任意两个面内的点,用一条避开原图顶点、横穿有限条边的曲线连接,经过的面依次给出一条对偶行走,从而连接对应的两个对偶顶点。原图的多个分支共处同一平面,仍只有一个外部面,不能为每个分支重复造一个“外部面点”。
第三,原图的自环对应对偶图的桥,原图的桥对应对偶图的自环。桥不分隔两个不同的面,因此对应的是同一对偶点上的环。原图的自环则把内外区域分开,任何从环内面走到环外面的对偶行走都必须经过该环所对应的唯一出口,故对偶边为桥。注意原图的“桥”与对偶图的“环”角色互换,并非都保持桥。
第四,对偶图一般允许重边与自环。两个面若共享两条不同原边,就产生两条连接同一对偶顶点对的边,必须分别保留;即使原图简单,对偶也不一定简单。比如一个长度至少3的圈,其内外两面之间会有与圈长相同数量的平行对偶边。
第五,同一个抽象平面图的不同平面嵌入,其对偶图不一定同构。上面的两个嵌入已经通过度序列证明了这一点。这里说的是“不一定”,不是声称任意两次嵌入的对偶都不同构。
【定理8.4.1:连通原图的点、边、面对应】设原图 连通,点数、边数、面数分别为 ;对偶图 的相应数量为 。则
若 位于原图面 内,还有
前两式直接来自一面一点、一边一边的构造。原图与对偶图都连通,分别应用欧拉公式,、。代入 ,得到 。
次数等式要把重复边界算清:若面边界中有 条桥和 条其他不同的边,则该面次数为 ;相应对偶点关联 个自环与 条非环边,自环各贡献度2,所以其度同样为 。非桥原边只在该面的边界出现一次;一个原自环的内外两侧分别对应两个面,按各自的一侧计算。
【定理8.4.2:非连通原图的推广】设原图有 个连通分支,则
并仍有 。补全证明:构造仍给出前两式以及次数对应;对偶图始终连通,故 ;原图满足 ,代入即得 。
不能把连通版的 原封不动用于 。例如原图由两个孤立点组成,有 ;对偶只有一个点且没有边,面数为1,确有 。孤立点不产生一条对偶边,也不额外增加一个原图面。
【定义8.4.2:自对偶图】若图 存在一个平面嵌入,使得抽象图 与此嵌入的对偶图 同构,则称 为自对偶图。定义要求“存在一个合适嵌入并有同构”,不要求它与每种嵌入的对偶都同构,更不是要求原图、对偶图的画面完全重合。
原图两边围出内外两面,对偶也只有两个点和两条平行边,二者同构。两层的点数、边数都为2,两个平行边必须各自保留。
原图为两点间一条边,并在其中一点附一个自环;桥对应对偶环,原环对应对偶桥,所以对偶仍是两点、一条连接边和一个自环,度序列同为 。两种边交换角色,整体图仍同构。
原图正方形的中心是实际空心顶点,四条辐条在此相接,不能把它当作两条无顶点的对角线。四个内部三角面各产生一个对偶点,这四点组成一个圈;外部面产生的第五点连接四点,所得对偶仍是同一个5阶轮图。原图与对偶都有5点8边5面。
【轮图及其自对偶性】对 ,在圈 内加一个中心点,使中心与圈上所有点相邻,称 阶轮图,记为 。本书下标 表示总顶点数,外圈只有 点。按总阶数 的奇偶称奇阶轮图、偶阶轮图,不能把外圈长度的奇偶直接替代它。
令外圈顶点依次为 ,中心为 ,下标模 。其内部面为三角形 ,另有一个外部面。于是 、、。相邻两个内部面共享一条辐条,故对应对偶点依次成圈;每个内部面又通过自己的一条外圈边与外部面相邻,故外部面对偶点与这个圈上所有点连接。由此对偶图正是 ,所有轮图都自对偶,特别地 。
【自对偶的必要计数条件】自对偶图必连通,因为它同构于总连通的对偶图。再由 和欧拉公式,得 ;若图同构,还须有相同的度序列及完整关联关系。只验证 或 并不能代替构造同构的证明。上面三个例子都已通过具体结构确认,而非只比点数和边数。
