图论-第六章_平面图判定

一、平面图

1.平面图定义

可平面图：若图G（可能交叉）可嵌入平面（能在平面画出图示的关系），则称G是可平面图（不一定是平面嵌入）

平面嵌入（n个）：可平面图G在平面上画出的无交叉边的图示（可以有曲线）

平面图（平面嵌入的一个，n个是同构的）：可平面图的任何一个平面嵌入都称为一个平面图

例子

 图e不是可平面图，即为不可平面图

2.平面图的面、边界和度数

设G是一个平面图，

面：每一个区域被称为面

有界面/内部面：面积有限

无界面/外部面：面积无限

边界：一个面的边集

面的度数：面的边集的数量（割边要计算两次、外部面），记作deg(f)

此时的面有两个，即内、外

例子：

3.极大可平面图

极大平面图的定义及性质

极大可平面图：设G为简单的可平面图，在G中任意不相邻的结点u,v，有G+(u，v)为不可平面图

极大平面图：极大平面的任何平面嵌入

完全图K,K2,K3,K4,K5-e，一定为极大可平面图

极大平面图必是连通图（证明：找一个两个连通分支的平面图）

当图的的阶数>=3,有割点或桥的平面图不是极大平面图

4.极小不可平面图

极小不可平面图：在不可平面图中任意去掉一条边所得到的图为可平面图，则称G为极小不可平面图

例子：

对偶图的定义

二、平面图的性质-欧拉公式

1.欧拉公式及其推广

欧拉公式定理1：设G是连通的平面图，n,m,r分别是其结点数、边数、面数，则n-m+r=2

自对偶平面图必是连通图，由于对偶图就是连通图

欧拉公式的推广形式定理2：设G是平面图，w为连通分支数，则n-m+r=w+1

定理3：

首先图的度数2m等于每个面的度相加，大于等于最小面的度数乘以面数

然后根据定理1得到m的关系式

推论4：

定理5：

和定理3是一样的推导过程

定理6：

定理7：

定理8：

2.极大平面图的判定

三、平面图的判断（不重要）

1.图的剖分、图的收缩、2度结点收缩

对边e=（u，v）的剖分：在e上加一个新的结点w，得到两条新边（u，w），（w，v),w

为新图的2度结点

图的剖分：对图的边进行一系列剖分

边e的收缩：删除图G的一条边e，并将e的两个端点粘合在一起，后的得到环和重边

2度结点内收缩（边剖分的逆操作）：设v是一个二度结点，将uv和vw删除，并用边替换

例子：

定理3.1

定理3.2

2.利用收缩和剖分和相应的定理去判断平面图

四、图的平面性检测（不重要）

DMP算法

五、对偶图与图的着色（不重要）

1.对偶图

对偶图的过程：

（1）在G中每一个面Ri设一个结点vi

（2）过Ri和Rj的公共边ek做一条仅一条边（vi，vj）与ek相交

（3）仅当ek（割边、或存在于一个面）只为Ri的边界时，在vi上做一个环与ek相交（即割边需要做一个环）

自对偶图：对偶图和自身G是同构的

对偶图一定是连通图

例子：

2.图的点着色

（点）着色：对图G每个结点指定一种颜色，使得相邻的两个结点被指定为不同的颜色

k（点）可着色：图中可用K种颜色着色

（点）色数：最少着色的颜色数量X（G）=k

对于图G=（V,E）一定是|V|可着色的，但不能直接称色数

3.图的边着色

边着色：对图G每个边指定一种颜色，使得相邻的两个边被指定为不同的颜色

K边可着色

边色数

六、图的色多项式

1.图的色多项式f(G,k)

f(G,k):表明图G有不同的k着色方式的总数，即当且存在一个结点v在两个k着色中被指定不同颜色

mi：i是指色数，表示恰好用i种颜色对图G的进行点着色的不同方案数

 例1：

例2：

f（Kn,k）=k(k−1)(k−2)…(k−(n−1))

2.色数的定义及计算

定理1：

推论2：

有这样的思路，将图G不断通过加边和粘合表示称若干个f（Kn,k）形式的色多项式之和

例子：

定理3：

3.色多项式的应用（略）