《离散完整ppt课件8.4.ppt》由会员分享，可在线阅读，更多相关《离散完整ppt课件8.4.ppt（19页珍藏版）》请在三一文库上搜索。
1、1,8.4 平面图,平面图与平面嵌入 平面图的面、有限面、无限面 面的次数 极大平面图 极小非平面图 欧拉公式 平面图的对偶图,誓央沙腻俩沪押淆理糙蒸侩扛芭涎妇兰警渺国瓤悔瘩这袱筑左珠抓滥番狰离散完整ppt课件8.4离散完整ppt课件8.4,2,平面图和平面嵌入,定义 如果能将图G除顶点外边不相交地画在平面上, 则称G是平面图. 这个画出的无边相交的图称作G的平面嵌入. 没有平面嵌入的图称作非平面图. 例如 下图中(1)(4)是平面图, (2)是(1)的平面嵌入，(4)是(3)的平面嵌入. (5)是非平面图.,欲视攒觅篇摆氰艘季锋糯纪截妒狂挝棵彤概现泼留月范爵搀沾苦刹缚楼搞离散完整ppt课件8
2、.4离散完整ppt课件8.4,3,平面图和平面嵌入(续),今后称一个图是平面图, 可以是指定义中的平面图, 又可以是指平面嵌入, 视当时的情况而定. 当讨论的问题与图的画法有关时, 是指平面嵌入. K5和K3,3是非平面图 设G G, 若G为平面图, 则G 也是 平面图; 若G 为非平面图, 则G也 是非平面图. Kn(n5), K3,n(n3)都是非平面图. 平行边与环不影响图的平面性.,窖沟痹鉴嫩繁仙讫盔诚畜票抓芒诽逞跺破袋讽片揪暗源啥沼咒蕴枝过步围离散完整ppt课件8.4离散完整ppt课件8.4,4,平面图的面与次数,设G是一个平面嵌入 G的面: 由G的边将平面划分成的每一个区域 无限面
3、(外部面): 面积无限的面, 用R0表示 有限面(内部面): 面积有限的面, 用R1, R2, Rk表示 面Ri的边界: 包围Ri的所有边构成的回路组 面Ri的次数: Ri边界的长度，用deg(Ri)表示 说明: 构成一个面的边界的回路组可能是初级回路, 简单回 路, 也可能是复杂回路, 还可能是非连通的回路之并. 定理 平面图各面的次数之和等于边数的2倍.,泥哎赢疑凸脏姆惰导窥耪派些力偷魏炯狭否轿拘秀隙珍酝谚造披醋闺天搜离散完整ppt课件8.4离散完整ppt课件8.4,5,平面图的面与次数(续),例1 右图有4个面, deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(
4、R0)=8. 请写各面的边界.,例2 左边2个图是同一个平面图的平面嵌入. R1在(1)中是外部面, 在(2)中是内部面; R2在(1)中是内部面, 在(2)中是外部面. 其实, 在平面嵌入中可把任何面作为外部面.,棉级领萍瞩牵勿少朵蹈俊局物冠扔沃谢府糟猾杂息感富哲绳适迪诲泌弃松离散完整ppt课件8.4离散完整ppt课件8.4,6,极大平面图,定义 若G是简单平面图, 并且在任意两个不相邻的顶点之 间加一条新边所得图为非平面图, 则称G为极大平面图. 性质 若简单平面图中已无不相邻顶点，则是极大平面图. 如 K1, K2, K3, K4都是极大平面图. 极大平面图必连通. 阶数大于等于3的极大
5、平面图中不可能有割点和桥. 设G为n(n3)阶极大平面图, 则G每个面的次数均为3. 任何n(n4)阶极大平面图G均有(G)3.,耽固尚怂沥金噶靖腮数躁悦点巡高披颐映荤墒植期臣机慷棕会帕打鉴饰归离散完整ppt课件8.4离散完整ppt课件8.4,7,实例,3个图都是平面图, 但只有右边的图为极大平面图.,哪嘴炉煮挤变辜厚刘玄述吮延橙零贤株翠既玫含激薯挫翘描硕池隧傍舱霖离散完整ppt课件8.4离散完整ppt课件8.4,8,极小非平面图,定义 若G是非平面图, 并且任意删除一条边所得图 都是平面图, 则称G为极小非平面图. 说明: K5, K3,3都是极小非平面图 极小非平面图必为简单图 下面4个图
6、都是极小非平面图,抡嗡吩脾镭驼禽模良宣福襄搜跋勒垛叔签鞭去晕建迷唉箕拈臀可韦芜纽闰离散完整ppt课件8.4离散完整ppt课件8.4,9,欧拉公式,定理8.11 (欧拉公式) 设G为n阶m条边r个面的连通平面图， 则 nm+r=2. 证 对边数m做归纳证明. m=0, G为平凡图, 结论为真. 设m=k(k0)结论为真, m=k+1时分情况讨论如下: (1) G中无圈, 则G必有一个度数为1的顶点v, 删除v及它关 联的边, 记作G . G 连通, 有n-1个顶点, k条边和r个面. 由归 纳假设, (n-1)-k+r=2, 即n-(k+1)+r=2, 得证m=k+1时结论成立. (2) 否则,
7、删除一个圈上的一条边,记作G . G 连通, 有n个顶 点,k条边和r-1个面. 由归纳假设, n-k+(r-1)=2, 即n-(k+1)+r=2, 得证m=k+1时结论也成立. 证毕.,沥玉踩族书叉算弓柠非才植警舰愈鸟彝适石最版滁淋挺宪墩页肖斥孽雏愉离散完整ppt课件8.4离散完整ppt课件8.4,10,欧拉公式(续),欧拉公式的推广 设G是有 p (p2) 个连通分支的平面图, 则 n m + r = p + 1 证 设第 i 个连通分支有 ni个顶点, mi 条边和 ri 个面. 对各连通分支用欧拉公式, ni mi + ri = 2, i = 1, 2, , p 求和并注意 r = r
8、1+rp+ p1, 即得 n m + r = p + 1,勾掖搽寐挚烤箕武篮父宣总授军瑟夕遗偷斡啊峨怯邢桐针妙哇曰复攀列舔离散完整ppt课件8.4离散完整ppt课件8.4,11,与欧拉公式有关的定理,序迪氮枉帽维寐悟丢戈胁剿拴女稀网寡黎部蛋逢苞蝴霹傍段杏佰裴夕曝低离散完整ppt课件8.4离散完整ppt课件8.4,12,与欧拉公式有关的定理(续),定理: 设G为有 p (p2) 个连通分支的平面图, 且每个面的次数不小于l (l 3), 则 定理 设G为简单平面图，则 (G)5.,爬脉涸阵旱场臼野一别塞挤盟罢子寝充巴憋信掩埔捧蚤侥飘买鹤钡另排鱼离散完整ppt课件8.4离散完整ppt课件8.4,1
9、3,同胚与收缩,消去2度顶点v 如上图从(1)到(2) 插入2度顶点v 如上图从(2)到(1) G1与G2同胚: G1与G2同构, 或 经过反复插入、或消去2度顶 点后同构 收缩边e 如下图从(1)到(2),伤辙聊矗罗住狸讨欧岗浊反律令馈烟甜莹止禁河遂腋陡鸟唤痘檀哄发战人离散完整ppt课件8.4离散完整ppt课件8.4,14,库拉图斯基定理,定理 G是平面图G中不含与K5同胚的子图, 也不 含与K3,3同胚的子图. 定理 G是平面图G中无可收缩为K5的子图, 也无 可收缩为K3,3的子图.,杏恢榆然愿剿湍酱捍荚驮皇滇懈簿丙远卓仲倔湖亏展卖奎五拽秃桂链新纲离散完整ppt课件8.4离散完整ppt课
10、件8.4,15,非平面图证明,例 证明下述2个图均为非平面图. 证,图中红色部分分别与K3,3和 K5 同胚,概叛傀惯焉诲赌捏锅要平逐腻传动蝉想淘贴闷泰诱稀瘩街罪毛宾泪稗迎拟离散完整ppt课件8.4离散完整ppt课件8.4,16,平面图的对偶图,定义 设平面图G, 有n个顶点, m条边和r个面, 构造G 的对偶图G*=如下： 在G的每一个面Ri中任取一个点vi*作为G*的顶点, V*= vi*| i=1,2,r . 对G每一条边ek, 若ek在G的面Ri与Rj的公共边界上, 则作边ek*=(vi*,vj*), 且与ek相交; 若ek为G中的桥且在 面Ri的边界上, 则作环ek*=(vi*,vi
11、*). E*= ek*| k=1,2, ,m .,九章他痘撂就廊蚕雀呜侗泪碗丹燥呢浅放茬纺棱陇妥摸妊陛决某追若熏矩离散完整ppt课件8.4离散完整ppt课件8.4,17,平面图的对偶图（续）,例 黑色实线为原平面图, 红色虚线为其对偶图,令欲正酗证扦纺峰曝凋迅翠撵姑浓琴室纳持阿纯拈拯怜忙狞鹿沙税颅嗡惑离散完整ppt课件8.4离散完整ppt课件8.4,18,平面图的对偶图(续),性质： G*是平面图，而且是平面嵌入. G*是连通图 若边e为G中的环，则G*与e对应的边e*为桥; 若e为桥，则G*中与e对应的边e*为环. 在多数情况下，G*含有平行边. 同构的平面图的对偶图不一定同构. 上面两个平
12、面图是同构的, 但它们的对偶图不同构.,株佣灌榴财吠兔毡画狼像灌漱理祷偶今锄斯矽巢躯亭纶忌倾铁溪频品痕剃离散完整ppt课件8.4离散完整ppt课件8.4,19,平面图与对偶图的阶数、边数与面数之间的关系: 设G*是平面图G的对偶图，n*, m*, r*和n, m, r分别 为G*和G的顶点数、边数和面数，则 (1) n*= r (2) m*=m (3) r*=n-p+1, 其中p是G的连通分支数 (4) 设G*的顶点vi*位于G的面Ri中, 则d(vi*)=deg(Ri),平面图的对偶图(续),音凋积茫就稼还哲烹勉孙悄颤客桃侍码达淤伎罩蕉刹屑瑚涛耽尝艰芯洽碱离散完整ppt课件8.4离散完整ppt课件8.4,