目录
12.1 平面图的基本概念
12.2 欧拉公式
12.3 平面图的判断
12.4 平面图的对偶图
12.5 平面的点着色与图的着色
1.平面图：若能把一个无向图G的所有结点和边画在平面上，使得任何两边除公共结点外没有其他交叉点。
2.对偶图
3.库拉托夫斯基定理
4.四色问题
12.1 平面图的基本概念
⭐面的定义：G的图形中由边围成的一个封闭区域，不能再分割成子区域。
··面r的边数——>面的度，记D(r)
有限面=内部面 无限面=外部面
文章来源地址https://www.toymoban.com/news/detail-467782.html
！！割边只能是一个面的边界
12.2 欧拉公式
定理1：设G=<V,E>是连通平面图，若它有n个结点，m条边和f个面，则有n-m+f=2
定理2：设G是一个(n,m)简单连通平面图，若m>1,则有m≤3n-6
推论1：任何简单连通平面图中，至少存在一个其度不超过5的结点
推论2：对于具有k(k≥2)个连通分支的平面图G，有n-m+f=k+1
⭐围长：一个图的围长为它包含的最短圈的长度；若不含圈，则规定圈长为
定理3：设G是一个(n,m)简单连通平面图，其围长k>2，则有
一个判断依据：
12.3 平面图的判断
⭐库拉托夫斯基定理
细分：在图G的边uv新增加一个二度结点，称为图G的细分。一条边上也可以同时增加有限个二度结点，所得的新图称为原来图的细分图。
定理：一个图是平面图的充分必要条件是它不包含与或细分图同构的子图。（此定理定性地说明了平面图的本质）
我们将和称为库拉托夫斯基图
12.4 平面图的对偶图
⭐对偶图
定义：若图G=<V,E>是一个平面图，构造图如下：
1.G的面F1,F2,......,Ff与中的结点一一对应；
2.若面Fi和Fj邻接，则与邻接；
3.若G中有一条边e只是面Fi的边界，则有一环。
12.5 平面的点着色与图的着色
文章来源：https://www.toymoban.com/news/detail-467782.html
定理1：地理G是k-面可着色的当且仅当它的对偶图G*是k-可着色的
定理2：任何连通平面图可五着色。
到了这里，关于离散数学 第十二章 平面图及其应用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
