G是可平面图.pptVIP

  1. 1、本文档共19页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
G是可平面图.ppt

例:面,边界,度,周线,相邻 就下图讨论基本概念 边界为何不一定是圈? 因为割边的存在 例:对偶图 对偶图的性质 性质1:若G是平面图,则G必有对偶图G*,且G*是唯一的. 可平面图的不同平面嵌入可有不同构的对偶图. 性质2: G*是连通图. 即使G不连通. 性质3:若G是连通平面图,那么(G*)* ? G. 性质4:对连通平面图G及其对偶图G*: m ? m*, n ? d *, d ? n* 平面图的着色 面着色问题:对平面图的面涂色,要求相邻面具有不同颜色. 定理:每一个平面图G都是5-可着色的. 四色猜想:平面图的着色只需四色? 1976年四色定理得到证明:AppelHaken. 1996年Robertson, Sanders, Seymour和Thomas宣布了一个更简单的证明并于1997年发表. Lu Chaojun, SJTU Lu Chaojun, SJTU 平面图 * Lu Chaojun, SJTU 平面图 定义:图G若能画在平面上,使任何两条边在顶点之外都不相交, 就称G可嵌入平面,或称G是可平面图.否则称不可平面图. 定义:可平面图的一个平面嵌入称为平面图. 在平面上画出是图的一种表示方法. 在平面上以边不交叉的方式画出,即平面图. 平面图例 1.K4是可平面图. 2.立方体是可平面图. Lu Chaojun, SJTU * 面 定义: 平面图G的某些边围成一个封闭区域, 该区域内任意两点间都可作一曲线相连,且该曲线不与任何顶点和边相交,这种区域称为面. 面的边界:界定一个面的所有边. 边界的边数称为面的度(或次). 规定:割边计算两次. 面与它边界上的边和顶点相关联. 面的周线:由边界构成且把面包含在内的圈. 两个面若有公共边,则称相邻. G有且只有一个无界面,即G外的区域,称为外部面;其余面都称内部面. 面的度与边数 定理:平面图中面的度与图的边数m满足 ?f?F(G) d(f ) = 2m 计算面的度时, 割边要算2次. 推论:平面图中奇度面数必为偶数. 欧拉公式 定理(欧拉1852):设G是连通平面图,它的顶点数n, 边数m, 面数r 之间有 n – m + r = 2 证明思想:以每次加入一条边的方式来构造G,可得G1, G2, ... , Gm.归纳证明诸Gk保持nk – mk + rk ? 2不变. 推论:若平面图G有k个连通支,则 n – m + r = k + 1 ? 2 不可平面图 定理:设G是简单连通平面图.若每个面的度?k,则 kr/2 ? m ? (n – 2)k/(k – 2) 例: K5是不可平面图. K5是结点数最少的不可平面图. 例: K3,3是不可平面图. K3,3是n?6时边数最少的不可平面图. Lu Chaojun, SJTU * Kuratowski定理 加细:在图的边上任意增加一些度为2的顶点. 原图与加细图称为同胚. 定理(Kuratowski):G是可平面图 ? G没有同胚于K5和K3,3的子图. Lu Chaojun, SJTU * 极大可平面图 设G是平面图,若在任意不相邻结点u和v之间加入边(u,v)都会使G + (u,v)成为不可平面图,则称G是极大可平面图. 注意:这里指的是加入边(u,v)在本质上破坏了图的可平面性. 可能在一种平面表示下不能加,但在另一种表示下可以加. Lu Chaojun, SJTU * 极大可平面图的性质 极大可平面图的简单性质: (1)必连通:否则可加边,如... (2)必无割点:否则可加边,如... (3)必无割边:否则可加边,如... (4)各面的度不能超过3:否则可加边,如... Lu Chaojun, SJTU * 极大可平面图的性质 定理:设G是n?3阶简单连通平面图,则 G是极大可平面图 ? G的面的度都是3. 推论:设G是n?3阶简单平面图,则 m ? 3n – 6, r ? 2n – 4. 等号成立?G是极大平面图 推论:简单平面图G中存在度小于6的顶点. Lu Chaojun, SJTU * 对偶图 定义:给定图G,如下构造的图G*,称为G的对偶图(dual graph). 1.G中每个面Ri内放一个G*顶点v*i ; 2.对应面Ri和Rj的公共边e,作一条仅与e相交一次的边e* ? (v*i,v*j) ? E(G*); 3.若割边e在面Ri的边界上,则作v*i上仅与e相交一次的环e*. Lu Chaojun, SJTU * 有对偶图的充要条件 定理:G有对偶图 iff G是平面图. 证:?即性质1. ?即不可平面图没有对偶图.由Kuratowski定理,不可平面图G一定含有同胚于K5或K3,3的子图. 因此若K

文档评论(0)

ailuojue1 + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档