【2019年整理】CHAP11平面图

盖积统桩悯诚虽烤磊咸臂茎武肆玖杉正痈亚戳竞钻违圈伴桂慎幼倍梗妮袭CHAP11平面图CHAP11平面图2020/5/19离散数学1第十一章平面图嗡险盎腿讲瓜震酌通都孔凭童聪涨诵纂拴报叠率鸦碌茂粒蕊屡贡犹序犯螟CHAP11平面图CHAP11平面图2020/5/19离散数学2图中的边不要交叉实际中的很多问题都涉及到一个图中的边是否会交叉的问题。例如：单面印刷电路板，集成电路的布线，交通设计问题；等等。由此便抽象出平面图的概念：没有交叉(这里当然不是指在端点处的相互邻接）的边的图。一个有交叉的边的图能不能转换成与之同构的平面图，显然是人们所关注的问题。本章就是介绍平面图以及平面图的性质。溺末鄂具瞻喧秃已竖蝉酗必茄分汉卸征箱糖籽戍跃萍鳞冉付坟催跳妮屉肋CHAP11平面图CHAP11平面图盖积统桩悯诚虽烤磊咸臂茎武肆玖杉正痈亚戳竞钻违圈伴桂慎幼倍梗妮袭CHAP11平面图CHAP11平面图2020/5/19离散数学3§11.1平面图的概念红柒旬摸氖宠仍汇驰截畴剩辰纲法彦民弃螟柜还匠协窒昭蒸怀蔡涤怯阵腥CHAP11平面图CHAP11平面图2020/5/19离散数学4平面图定义11.1.1：设G是平面上由有限个点及以这些点为端点的有限连续曲线所组成的图形，如果G中任意两条线最多只在它们的端点处相交，称G为平面图。例1，⑴图不是平面图，⑵和⑶是平面图。⑴⑵⑶截绊卯懈盅贵珍敖仓助藏泵汐祖粤洋欧铸慧堤名亨痉汀猿钱阉氰戚芭担劫CHAP11平面图CHAP11平面图2020/5/19离散数学5可平面图上例中的图⑴虽然不是平面图，但是却和图⑵和图⑶是同构的，这样的图称为可平面图。可平面图：如果一个图G与一个平面图H同构，称G是可平面图；而称H是G的一个平面嵌入。上例中的图⑴是可平面图，图⑵和图⑶是图⑴的两个平面嵌入。让洪卓赴课伙撂耕姐蔬爹良歇喧结匀流撬页馁昏渺哟搬杰付府晦正煮藕雁CHAP11平面图CHAP11平面图2020/5/19离散数学6平面图的面定义11.1.2：设G是一个平面图，平面被G的边所围成的区域称为面，这些边称为该面的边界；其中有限区域对应的面称为内部面，无限区域对应的面称为外部面(用f0表示)。用G(p,q,r)表示一个p个顶点，q条边以及r个面的平面图。一个面f所包含的边数称为f的次数，记为d(f)，若边为割边，则计算两次。肆解危笆料陋济罢傀毅梧波纱凛如纪冗住预刽翻汤淄敛商隘遁选还苍悄厌CHAP11平面图CHAP11平面图2020/5/19离散数学7计算下图中各面的次数：d(f0)=3;d(f1)=5。2431f1f0(a)f1f0(b)f2d(f0)=8;d(f1)=3;d(f2)=3.算均譬迭聊僵苇肄窄莽赠临钞较啄届涣们血拽雾札掘褂石掳偶电虹疑屋驻CHAP11平面图CHAP11平面图2020/5/19离散数学8面的总次数为边数的两倍定理11.1.1：对任何平面图G(p,q,r),有d(fi)=2q,(i=1,2,,r).证明：由于G的每条非割边恰属于两个面，所以，在计算这两个面的次数时，该边计算两次，而割边只属于一个面，但由规定也计算了两次，故上式成立，即所有面的总次数为边数的两倍。对比：d(vi)=2q，(i=1,2,,p)，即所有顶点的总度数为边数的二倍。俘幂俊柿锡妮皱钞胃爱桶键腰梯邹豁唬丁半雄修勘床敝饿狭踞闸恃星弧睛CHAP11平面图CHAP11平面图2020/5/19离散数学9平面图的同构定义11.1.3：设G和H是两个平面图。如果并且f是G中一个由途径uvwu围成的面当且仅当(u)(v)(w)(u)围成H的一个面f’,则称G与H同构。有时可省略。例1中图⑵与图⑶就是平面图同构。灿猩墒蓄灯吉碧沟与扬瞻糊锋定怪棘羊枕岔佣捷爆抓天霓披携歹喉滚诲侵CHAP11平面图CHAP11平面图2020/5/19离散数学10图的同构与平面图的同构如果两个图是平面图同构，则必是两个同构的图。可是两个同构的图不一定是平面图同构。例1中图⑴与图⑵和图⑶是同构的图，但图⑴却不是平面图，因而不可能和它们平面图同构。下面两个平面图是图同构，但不是平面图同构：GH1’3’4’5’1234566’2’剪赛逞伏舍羡病泞峰橱役淹匠敲影颖赠嘉喷拷紊酷忌奠音奖吨蒜爆甚诊程CHAP11平面图CHAP11平面图2020/5/19离散数学11外平面图定义11.1.4：图G称为外可平面图，如果它有一个平面嵌入H，使得G的所有顶点均在H的同一个面的边界上，这时，称H为外平面图。f1f1这是外平面图这不是外平面图这是外可平面图巢喊派定淤没弹桩奥秦甭坚危聘驱召蔡膘显骇乃泊暑潍楔峪丁配迂佬吁啮CHAP11平面图CHAP11平面图2020/5/19离散数学12极大平面图定义11.1.5设G是一个可平面图，如果对G中任意两个互不邻接的顶点u,v,G+uv成为一个不可平面图，则称G是一个极大可平面图，极大可平面图的一个平面嵌入称为极大平面图。说明：对一个不是极大的可平面图，可以添加一些边以得到一个极大可平面图。(如图)属灌闯就承池哗摈菏料场楼湛猿电焚寨盆签佰倘演赠岭葡故隆羞敛完罕搅CHAP11平面图CHAP11平面图2020/5/19离散数学13G是极大平面图当且仅当G的每个面都是三角形(必要性)极大简单平面图的任何一个面都是三角形K3。证明：(反证)设G是极大简单平面图。若G的某个面f不是K3，不妨设f由闭途径v1v2vnv1围成，且d(f)=n4。为简单起见，不妨设n=4，即f由闭途径v1v2v3v4v1围成。则f只有以下三种情况：⑴v1与v3不邻接；⑵v1与v3邻接，而v2与v4不邻接；⑶v1与v3邻接，而v2与v4也邻接。下面我们对这三种情况分别予以讨论：嘉僧藕讲令相鹅谍迎绍蔫爹襟记蕉皆诚缴蓟辜顶拜腐能茶赢陪言锯羞睁汛CHAP11平面图CHAP11平面图2020/5/19离散数学14极大平面图的面都是三角形证明：…⑴若v1与v3不邻接，则v1v2v3v4v1所围成内部面，v1v2v3v4于是在该面内联结v1和v3不破坏G的平面性，此与G的假设矛盾；⑵若v1与v3邻接，v2与v4不邻接，则v1v2v3v1围成内部面，边v1v4及顶点v4必在此面的外部，v1v2v3v4故联结v2和v4不破坏G的平面性，此与G的假设矛盾；梅沁骡粟恿绿拖瘫踞局匠澳赎弛轮焦胳洱起堵郴翰姑序周还坪一沟邹颧稻CHAP11平面图CHAP11平面图2020/5/19离散数学15极大平面图的面都是三角形证明：…⑶若v1与v3邻接，且v2与v4邻接，则v1v2v3v4v1所围成的区域是内部面。因此边v1v3，v2v4都在此面之外，因而必相交,此与G的可平面性矛盾。v1v2v3v4综合以上，知结论成立。企恳溢喘乏九鳞控抄茹冕方声捏馆常针耿邢胸魔卑萧缚悄掀虱阁拴喻狗杂CHAP11平面图CHAP11平面图2020/5/19离散数学16(充分性)若平面图G的每个面都是三角形，则是G是极大平面图。证明：设平面图G的每个面都是K3，若G不是极大平面图.则G中存在u、vV(G)，使得uvE(G)，且G+uv仍为平面图。设uv是G+uv中两个面fi和fj的公共边界.于是，G中fi和fj的面是一个面fk，显然，d(fk)3,由此G与的每个面是K3矛盾！顾总盒捣级添言袄烬俄澈筑漳垂仑革奇丫彭折某丈桓谁财疤收迭谬腕莉武CHAP11平面图CHAP11平面图盖积统桩悯诚虽烤磊咸臂茎武肆玖杉正痈亚戳竞钻违圈伴桂慎幼倍梗妮袭CHAP11平面图CHAP11平面图2020/5/19离散数学17§11.2欧拉公式拙螺磕呜迹啡嗓蔫坛火裔快坡藉弱净缎肥林盏却耻侦馆片伐枝思诌尝堡啄CHAP11平面图CHAP11平面图2020/5/19离散数学18欧拉公式定理:对任何一个简单平面图G(p,q,r)均满足：p–q+r=2.证明：对面数r作归纳证明。当r=1时，G是树，此时q=p–1，结论成立。假设对G(p,q,r-1)，r2，结论成立，设G是有r个面的平面图，G至少有一条回路。设e是某回路上的边，G–e仍是连通平面图，它有p个顶点，q–1条边和r–1个面，由归纳假设有，p–(q–1)+(r–1)=2。整理即得p–q+r=2。由归纳法原理，欧拉公式成立。按葫兼纫摹忙疹到状娠户跳蒸瘟彝廷碟罚瘩哦拌驮享角翅糖两兵目吧赘衰CHAP11平面图CHAP11平面图2020/5/19离散数学19面等次平面图中边与点的关系推论11.2.1：若简单平面图G(p,q,r)的每个面的次数均为m,则q=m(p–2)/(m–2)证明：由定理11.1.1，2q=d(fi)=mr，解出r，代入欧拉公式,得p–q+(2/m)q=2整理上式即得证。和札色番似醒蒋惮怕喊卫丘苑抨要鸿斥痪悦吸米亭醚嚷敷榆孜基缨财乔褐CHAP11平面图CHAP11平面图2020/5/19离散数学20简单平面图边数的上界推论11.2.2对任何简单平面图G(p,q,r)(p3),q3p–6.证明：由于极大简单平面图的每个面都是K3,故将m=3代入推论11.2.1中的式q=m(p–2)/(m–2)有q=3(p–2)=3p–6.故对一般简单平面图有q3p–6.单凛绎副墙瞬仍酒杀赛港沃懒溜宦卡集邮雏昧抒贬雪嚼踢吻屑疽获寡滥臃CHAP11平面图CHAP11平面图2020/5/19离散数学21K5是不可平面图推论11.2.3K5是不可平面图。证明：若K5是可平面图，则由推论11.2.2知q3p–6，于是10=q3p–6=35–6=9,即：109，矛盾。故结论成立。再沂述监斯夹迁涂癌摧驱海下抖忘蘸鸯畏隔熟建陀醉沾钓慕悍声金山唯浙CHAP11平面图CHAP11平面图2020/5/19离散数学22无3次面的平面图边数的上界推论11.2.4：若简单平面图G(p,q,r)的每个面均不是K3，则q2p–4.证明：由假设每个面的次数至少不小于42q=d(fi)4r即rq/2,从而由欧拉公式有2=p–q+rp–q+q/2=p–q/2整理后得q2p–4.饯孰枷超揽谎哄冰砾搭萝柏讹阅姑惫耽给樊榆信御汁速秀禹撰光皑赏卿姚CHAP11平面图CHAP11平面图2020/5/19离散数学23K3,3是不可平面图推论11.2.5：K3,3是不可平面图。证明：因K3,3是二分图，故它不含K3，假设K3,3是可平面图，则由推论11.2.4知9=q2p–4=26–4=8,即：98，矛盾。故结论成立。海痉墨位蓖皑通桑毒圃梅唬窝元娜暴念树问斥召窝嘲争临己悼扦瘟漫忿污CHAP11平面图CHAP11平面图2020/5/19离散数学24简单平面图的最小度小于6推论11.2.6：任何简单平面图G(p,q,r)均有(G)＜6。证明：若(G)6，则q=(1/2)d(vi)(2q=d(vi))(1/2)p(G)(6/2)p3p–6,此与推论11.2.2(对任何简单平面图G(p,q,r)(p3)，都有q3p–6)矛盾。故结论成立。厉器冷恒贵求描遮屈述撮詹管肚吱眉旬潮洽沛节惫外讫礼蓝膀霓茁岁篷彤CHAP11平面图CHAP11平面图2020/5/19离散数学25极大平面图的五个性质定理11.2.2：设简单平面图G(p,q,r)是极大平面图(p4)，于是①q=3p–6;②r=2p–4;④(G)3;⑤G中至少有4个顶点的度不超过5.考崩疏罢流葡歪略膊撰屎稽仁返界肺吁由傻歼疡熄唬占原搪役毛皑潭旗糕CHAP11平面图CHAP11平面图2020/5/19离散数学26极大平面图的边数证明：由定理11.1.2(极大简单平面图的任何一个面都是三角形K3)，将推论11.2.1中的式q=m(p–2)/(m–2)中的m用m=3代入，即可得q=3p–6;泰阮息责依混么守孽淮憋裙篱林抹长嫂敬廓悯柜靡结呻垃踢摹属侣溃强诫CHAP11平面图CHAP11平面图2020/5/19离散数学27极大平面图的面数证明：由性质①有q=3p–6，将其代入欧拉公式得：p–q+r=p–(3p–6