平面图

平面图
定义：如果能把图G画在一个平面上，使得任何两边不相交，称G是可平面图。可平面图在平面上的一个嵌入（画法）称为平面图。

定义：设G是平面图。由它的若干条边所围成的区域内如果不含任何其它边，则称该区域为G的一个面或域。包围这个域的边称为其边界。
平面图G外边的无限区域称为无限域，其他的域叫内部域。每个域的边界是一条闭路径（不一定是道路），其长度称为域的边界长度。

割边只是一个域的边界（无限域），非割边一定是两个域的公共边界。平面图的每条边对边界长度的贡献都是2，因此域的边界长度之和等于\(2|E|\)。

定理1(欧拉公式). 设G是平面连通图，则G的域个数是\(d=m-n+2\)。
证明：取G的一颗生成树T，逐一加入T的弦。
推论2(欧拉不等式). 对任意平面图（不一定连通），有\(n-m+d\ge 2.\)

推论3. 若G是阶不小于3的简单平面图，则\(m\le 3n-6\)。
证明：如果G不含回路，由连通性知\(m\le n-1\le 3n-6\)。否则，G的每个域边界数不小于3，因此\(3d\le 2m\)，带入欧拉不等式即得。
类似可以证明如果G的每个域边数不小于4，则\(m\le 2n-4\)。

定理4. \(K_5,\ K_{3,3}\)都是不可平面图。
证明：\(K_5\)边数为10，由推论3即得。\(K_{3,3}\)每个域的边界数不小于4，与\(m\le 2n-4\)推出矛盾。
\(K_5,\ K_{3,3}\)分别记作\(K^{(1)}, K^{(2)}\)图。本质上只有这两种非平面图。我们先介绍图同胚概念。

定义： 如果对图G进行如下若干操作：
1. 在图G某边中插入一个结点，使该边变成2条边；
2. 将G某个度为2的结点关联的两条边合并成一条。
得到的图\(G'\)称为与G同胚。图G可平面当且仅当G的任意同胚图可平面。
与\(K^{(1)},K^{(2)}\)所有同胚图分别称为\(K^{(1)},K^{(2)}\)型图，统称K型图。

定理5. 图G可平面的充要条件是G没有K型子图。

平面图的对偶图
定义：设G是平面图，如下定义的图\(G^*\)称为G的对偶图。
1. G的每个域\(f\)内设置一结点\(v^*\)作为\(G^*\)的结点；
2. 对G的非割边\(e\)，必为两域\(f_i, f_j\)的公共边界，取\(e^*\)连接\(v_i^*,v_j^*\)；
3. 对G的割边，必是某域\(f\)的边界，画\(G^*\)的一条自环\(e^*=(v^*,v^*)\)。

性质1. 平面图G的对偶图\(G^*\)唯一，且满足\(m^*=m,n^*=d, d^*=n\)。
性质2. \(G^*\)是连通图。
性质3. \((G^*)^*\)同构于G。
性质4. G的回路对应\(G^*\)的割集，G的割集对应\(G^*\)的回路。

    所属分类：离散数学     发表于2022-08-24