《离散数学平面图优秀PPT.ppt》由会员分享，可在线阅读，更多相关《离散数学平面图优秀PPT.ppt（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1现在学习的是第1页，共19页平面图和平面嵌入平面图和平面嵌入 定定义义 如如果果能能将将图图G除除顶顶点点外外边边不不相相交交地地画画在在平平面面上上,则则称称G是是平平面面图图.这这个个画画出出的的无无边边相相交交的的图图称称作作G的的平平面面嵌嵌入入.没有平面嵌入的图称作没有平面嵌入的图称作非平面图非平面图.例例如如 下下图图中中(1)(4)是是平平面面图图,(2)是是(1)的的平平面面嵌嵌入入，(4)是是(3)的平面嵌入的平面嵌入.(5)是非平面图是非平面图.2现在学习的是第2页，共19页平面图和平面嵌入平面图和平面嵌入(续续)今今后后称称一一个个图图是是平平面面图图,可可以以是是指指
2、定定义义中中的的平平面面图图,又又可可以以是是指指平平面面嵌嵌入入,视视当当时时的的情情况况而而定定.当当讨讨论论的的问问题题与与图图的的画画法法有有关关时时,是是指指平面嵌入平面嵌入.K5和和K3,3是非平面图是非平面图设设G G,若若G为平面图为平面图,则则G 也是也是 平面图平面图;若若G 为非平面图为非平面图,则则G也也 是非平面图是非平面图.Kn(n 5),K3,n(n 3)都是非平面图都是非平面图.平行边与环不影响图的平面性平行边与环不影响图的平面性.K5K3,33现在学习的是第3页，共19页平面图的面与次数平面图的面与次数设设G是一个平面嵌入是一个平面嵌入G的面的面:由由G的边将
3、平面划分成的每一个区域的边将平面划分成的每一个区域无限面无限面(外部面外部面):面积无限的面面积无限的面,用用R0表示表示有限面有限面(内部面内部面):面积有限的面面积有限的面,用用R1,R2,Rk表示表示 面面Ri的边界的边界:包围包围Ri的所有边构成的回路组的所有边构成的回路组面面Ri的次数的次数:Ri边界的长度，用边界的长度，用deg(Ri)表示表示 说明说明:构成一个面的边界的回路组可能是初级回路构成一个面的边界的回路组可能是初级回路,简单回简单回路路,也可能是复杂回路也可能是复杂回路,还可能是非连通的回路之并还可能是非连通的回路之并.定理定理 平面图各面的次数之和等于边数的平面图各面
4、的次数之和等于边数的2倍倍.4现在学习的是第4页，共19页平面图的面与次数平面图的面与次数(续续)例例1 右图有右图有4个面个面,deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8.请写各面的边界请写各面的边界.例例2 左边左边2个图是同一个平面图个图是同一个平面图的平面嵌入的平面嵌入.R1在在(1)中是外部面中是外部面,在在(2)中是内部面中是内部面;R2在在(1)中是内中是内部面部面,在在(2)中是外部面中是外部面.其实其实,在平面嵌入中可把任何面作为在平面嵌入中可把任何面作为外部面外部面.5现在学习的是第5页，共19页极大平面图极大平面图 定义定义 若若G是简
5、单平面图是简单平面图,并且在任意两个不相邻的顶点之并且在任意两个不相邻的顶点之间加一条新边所得图为非平面图间加一条新边所得图为非平面图,则称则称G为为极大平面图极大平面图.性质性质n若简单平面图中已无不相邻顶点，则是极大平面图若简单平面图中已无不相邻顶点，则是极大平面图.如如 K1,K2,K3,K4都是极大平面图都是极大平面图.n极大平面图必连通极大平面图必连通.n阶数大于等于阶数大于等于3的极大平面图中不可能有割点和桥的极大平面图中不可能有割点和桥.n设设G为为n(n 3)阶极大平面图阶极大平面图,则则G每个面的次数均为每个面的次数均为3.n任何任何n(n 4)阶极大平面图阶极大平面图G均有
6、均有(G)3.6现在学习的是第6页，共19页实例实例3个图都是平面图个图都是平面图,但只有右边的图为极大平面图但只有右边的图为极大平面图.7现在学习的是第7页，共19页极小非平面图极小非平面图 定义定义 若若G是非平面图是非平面图,并且任意删除一条边所得图并且任意删除一条边所得图都是平面图都是平面图,则称则称G为为极小非平面图极小非平面图.说明说明:K5,K3,3都是极小非平面图都是极小非平面图 极小非平面图必为简单图极小非平面图必为简单图下面下面4个图都是极小非平面图个图都是极小非平面图 8现在学习的是第8页，共19页欧拉公式欧拉公式 定理定理8.11(欧拉公式欧拉公式)设设G为为n阶阶m条
7、边条边r个面的连通平面图，个面的连通平面图，则则 n m+r=2.证证 对边数对边数m做归纳证明做归纳证明.m=0,G为平凡图为平凡图,结论为真结论为真.设设m=k(k 0)结论为真结论为真,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)否则否则,删除一个圈上的一条边删除一个圈上的一条边,记作
8、记作G .G 连通连通,有有n个顶个顶点点,k条边和条边和r-1个面个面.由由归纳假设归纳假设,n-k+(r-1)=2,即即n-(k+1)+r=2,得证得证m=k+1时结论也成立时结论也成立.证毕证毕.9现在学习的是第9页，共19页欧拉公式欧拉公式(续续)欧拉公式的推广欧拉公式的推广 设设G是有是有 p(p 2)个连通分支的平面图个连通分支的平面图,则则 n m+r=p+1证证 设第设第 i 个连通分支有个连通分支有 ni个顶点个顶点,mi 条边和条边和 ri 个面个面.对各连通分支用欧拉公式对各连通分支用欧拉公式,ni mi+ri=2,i=1,2,p求和并注意求和并注意 r=r1+rp+p
9、1,即得即得 n m+r=p+110现在学习的是第10页，共19页与欧拉公式有关的定理与欧拉公式有关的定理 K5K3,3定理定理 设设G为为n阶连通平面图阶连通平面图,有有m条边条边,且每个面的次数不且每个面的次数不小于小于l(l 3),则则 证证 由定理由定理(各面次数之和等于边数的各面次数之和等于边数的2倍倍)及欧拉公式得及欧拉公式得 2m lr=l(2+m-n)可解得所需结论可解得所需结论.推论推论 K5 和和 K3,3不是平面图不是平面图.证证 用反证法用反证法,假设它们是平面图假设它们是平面图,则则 K5:n=5,m=10,l=3 K3,3:n=6,m=9,l=4与定理矛盾与定理矛盾
10、.11现在学习的是第11页，共19页与欧拉公式有关的定理与欧拉公式有关的定理(续续)定理定理:设设G为有为有 p(p 2)个连通分支的平面图个连通分支的平面图,且每个面的次数不小于且每个面的次数不小于l(l 3),则则定理定理 设设G为简单平面图，则为简单平面图，则 (G)5.12现在学习的是第12页，共19页同胚与收缩同胚与收缩 消去消去2度顶点度顶点v 如上图从如上图从(1)到到(2)插入插入2度顶点度顶点v 如上图从如上图从(2)到到(1)G1与与G2同胚同胚:G1与与G2同构同构,或或经过反复插入、或消去经过反复插入、或消去2度顶度顶点后同构点后同构收缩边收缩边e 如下图从如下图从(1
11、)到到(2)13现在学习的是第13页，共19页库拉图斯基定理库拉图斯基定理定理定理 G是平面图是平面图G中不含与中不含与K5同胚的子图同胚的子图,也不也不含与含与K3,3同胚的子图同胚的子图.定理定理 G是平面图是平面图G中无可收缩为中无可收缩为K5的子图的子图,也无也无可收缩为可收缩为K3,3的子图的子图.14现在学习的是第14页，共19页非平面图证明非平面图证明例例 证明下述证明下述2个图均为非平面图个图均为非平面图.证证图中红色部分分别与图中红色部分分别与K3,3和和 K5 同胚同胚15现在学习的是第15页，共19页平面图的对偶图平面图的对偶图 定义定义 设平面图设平面图G,有有n个顶点
12、个顶点,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*).E*=ek*|k=1,2,m.16现在学习的是第16页，共19页平面图的对偶图（续）平面图的对偶图（续）例例 黑色实线为原平面图黑色实线为原平面图,红色虚线
13、为其对偶图红色虚线为其对偶图 17现在学习的是第17页，共19页平面图的对偶图平面图的对偶图(续续)性质：性质：nG*是平面图，而且是平面嵌入是平面图，而且是平面嵌入.nG*是连通图是连通图n若若边边e为为G中中的的环环，则则G*与与e对对应应的的边边e*为为桥桥;若若e为为桥桥，则则G*中与中与e对应的边对应的边e*为环为环.n在多数情况下，在多数情况下，G*含有平行边含有平行边.n同构的平面图的对偶图不一定同构同构的平面图的对偶图不一定同构.上面两个平面图是同构的上面两个平面图是同构的,但它们的对偶图不同构但它们的对偶图不同构.18现在学习的是第18页，共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)平面图的对偶图平面图的对偶图(续续)19现在学习的是第19页，共19页