图论 |
您所在的位置:网站首页 › 王冠平面图纸 › 图论 |
一、平面图
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.色多项式的应用(略) |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |