离散数学 第十二章 平面图及其应用 | 您所在的位置:网站首页 › 节点平面图是什么 › 离散数学 第十二章 平面图及其应用 |
目录 12.1 平面图的基本概念 12.2 欧拉公式 12.3 平面图的判断 12.4 平面图的对偶图 12.5 平面的点着色与图的着色 1.平面图:若能把一个无向图G的所有结点和边画在平面上,使得任何两边除公共结点外没有其他交叉点。 2.对偶图 3.库拉托夫斯基定理 4.四色问题 12.1 平面图的基本概念⭐面的定义:G的图形中由边围成的一个封闭区域,不能再分割成子区域。 ··面r的边数——>面的度,记D(r) 有限面=内部面 无限面=外部面
!!割边只能是一个面的边界 12.2 欧拉公式定理1:设G=是连通平面图,若它有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,则有 一个判断依据: ⭐库拉托夫斯基定理 细分:在图G的边uv新增加一个二度结点,称为图G的细分。一条边上也可以同时增加有限个二度结点,所得的新图称为原来图的细分图。 定理:一个图是平面图的充分必要条件是它不包含与 我们将 ⭐对偶图 定义:若图G=是一个平面图,构造图 1.G的面F1,F2,......,Ff与 2.若面Fi和Fj邻接,则 3.若G中有一条边e只是面Fi的边界,则
定理1:地理G是k-面可着色的当且仅当它的对偶图G*是k-可着色的 定理2:任何连通平面图可五着色。
|
CopyRight 2018-2019 实验室设备网 版权所有 |