特殊平面图与平面图的对偶图学习教案.pptx

《特殊平面图与平面图的对偶图学习教案.pptx》由会员分享，可在线阅读，更多相关《特殊平面图与平面图的对偶图学习教案.pptx（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1特殊特殊(tsh)平面图与平面图的对偶图平面图与平面图的对偶图第一页，共32页。2 注：只有(zhyu)在单图前提下才能定义极大平面图。引理 设G是极大平面图，则G必然(brn)连通；若G的阶数大于等于3，则G无割边。极大平面图非极大平面图极大平面图 (1)先证明(zhngmng)G连通。若不然，G至少两个连通分支。设G1与G2是G的任意两个连通分支。第2页/共32页第二页，共32页。3 把G1画在G2的外部面上(min shn)，并在G1,G2上分别取一点u与v.连接u与v得到一个新平面图G*。但这与G是极大平面图相矛盾。(2)当G的阶数n3时，我们(w men)证明G中没有割边。若

2、不然，设G中有割边e=uv，则G-uv不连通(lintng)，恰有两个连通(lintng)分支G1与G2。uveG1G2Gf第3页/共32页第三页，共32页。4 设u在G1中，而v在G2中。由于n3,所以，至少(zhsho)有一个分支包含两个以上的顶点。设 G2至少(zhsho)含有两个顶点。又设 G1中含有点u的面是 f,将G2画在 f 内。由于G是单图，所以(suy)，在G2的外部面上存在不等于点v的点t。现在，在G中连接点u与t得新平面图G*,它比G多一条边。这与G的极大性相矛盾。vueG1G2G第4页/共32页第四页，共32页。5 下面(xi mian)证明极大平面图的一个重要性质。定

3、理1 设G是至少有3个顶点的平面图，则G是极大(j d)平面图，当且仅当G的每个面的次数是3且为单图。注：该定理可以(ky)简单记为是“极大平面图的三角形特征”，即每个面的边界是三角形。证明：“必要性”由引理知，G是单图、G无割边。于是G的每个面的次数至少是3。假设G中某个面 f 的次数大于等于4。记 f 的边界是v1v2v3v4vk。如下图所示:第5页/共32页第五页，共32页。6 如果v1与v3不邻接，则连接v1v3，没有破坏G的平面性，这与G是极大平面图矛盾。所以v1v3必须(bx)邻接，但必须(bx)在 f 外连线；同理v2与v4也必须(bx)在 f 外连线。但边v1v3与边v2v4在

4、 f 外交叉，与G是平面图矛盾！所以，G的每个面次数(csh)一定是3.定理(dngl)的充分性是显然的。v1v2v3v4v5vkf第6页/共32页第六页，共32页。7 推论(tuln)：设G是n个点，m条边和个面的极大平面图，且n3.则：(1)m=3n-6;(2)=2n-4.证明：因为G是极大平面图，所以(suy)，每个面的次数为 3.由次数公式：由欧拉公式(gngsh)：所以得：第7页/共32页第七页，共32页。8 所以(suy)得：又 所以(suy)：注：顶点(dngdin)数相同的极大平面图并不唯一。例如：正20面体非正20面体第8页/共32页第八页，共32页。9 还在研究中的问题是：

5、顶点数相同(xin tn)的极大平面图的个数和结构问题。2、极大(j d)外平面图及其性质 定义2 若一个(y)可平面图G存在一种平面嵌入，使得其所有顶点均在某个面的边界上，称该图为外可平面图。外可平面图的一种外平面嵌入，称为外平面图。外可平面图外平面图1f外平面图2f第9页/共32页第九页，共32页。10 注：对外可平面图G来说，一定(ydng)存在一种外平面嵌入，使得G的顶点均在外部面的边界上。这由球极投影法可以说明。下面研究(ynji)极大外平面图的性质。定义3 设G是一个简单外可平面图，若在G中任意不邻接顶点间添上一条(y tio)边后，G成为非外可平面图，则称G是极大外可平面图。极大

6、外可平面图的外平面嵌入，称为极大外平面图。极大外平面图第10页/共32页第十页，共32页。11 定理2 设G是一个有n(n3)个点，且所有点均在外部面上(min shn)的极大外平面图，则G有n-2个内部面。证明(zhngmng)：对G的阶数作数学归纳。当n=3时，G是三角形，显然(xinrn)只有一个内部面；设当n=k时，结论成立。当n=k+1时，首先，注意到 G必有一个2度顶点u在G的外部面上。(这可以由上面引理得到)考虑G1=G-v。由归纳假设，G1有k-2个内部面。这样G有k-1个内部面。于是定理2得证。引理 设G是一个连通简单外可平面图，则在G中有一个度数至多是2的顶点。第11页/共

7、32页第十一页，共32页。12 定理(dngl)3 设G是一个有n(n3)个点，且所有点均在外部面上的外平面图，则G是极大外平面图，当且仅当其外部面的边界是圈，内部面是三角形。注：这是极大(j d)外平面图的典型特征。证明(zhngmng)：先证明(zhngmng)必要性。(1)证明G的边界是圈。容易知道：G的外部面边界一定为闭迹，否则，G不能为极大外平面图。设W=v1v2vnv1是G的外部面边界。若 W不是圈，则存在i与j,使vi=vj=v.此时，G可以示意如下：W vi-1 v1vnv2vi+1vj-1vj+1v第12页/共32页第十二页，共32页。13 vi-1与vi+1不能邻接。否则

8、W不能构成G的外部面边界。这样(zhyng)，我们连接vi-1与vi+1：vi-1 v1vnv2vi+1vj-1vj+1v 得到一个(y)新外平面图。这与G的极大性矛盾。(2)证明(zhngmng)G的内部面是三角形。首先，注意到，G的内部面必须是圈。因为，G的外部面的边界是生成圈，所以G是2连通的，所以，G的每个面的边界必是圈。第13页/共32页第十三页，共32页。14 其次，设C是G中任意一个内部面的边界(binji)。如果C的长度大于等于4，则C中一定存在不邻接顶点，连接这两点得到一个新平面图，这与G的极大性矛盾。又由于G是单图，所以C的长度只能为3.下面(xi mian)证明充分性。设

9、G是一个外平面图，内部(nib)面是三角形，外部面是圈 W.如果G不是极大外平面图，那么存在不邻接顶点u与v,使得G+uv是外平面图。但是，G+uv不能是外平面图。因为，若边uv经过W的内部，则它要与G的其它边相交；若uv经过W的外部，导致所有点不能在G的同一个面上。所以，G是极大外平面图。第14页/共32页第十四页，共32页。15 定理4 每个至少有7个顶点的外可平面图的补图不是(b shi)外可平面图，且7是这个数目的最小者。我们用枚举(mi j)方法证明。证明：对于(duy)n=7的极大外可平面图来说，只有4个。如下图所示。直接验证：它们的补图均不是外可平面的。而当n=6时，我们可以找到

10、一个外可平面图G(见下图),使得其补图是外可平面图。第15页/共32页第十五页，共32页。16(二)、平面图的对偶(du u)图 1、对偶(du u)图的定义 定义4 给定平面图G，G的对偶(du u)图G*如下构造：(1)在G的每个面fi内取一个点vi*作为G*的一个顶点；(2)对G的一条边e,若e是面 fi 与 fj 的公共边，则连接 vi*与vj*，且连线穿过边e;若e是面 fi 中的割边，则以vi为顶点第16页/共32页第十六页，共32页。17作环，且让它与e相交(xingjio)。例如(lr)，作出平面图G的对偶图G*G第17页/共32页第十七页，共32页。18 2、对偶(du u)

11、图的性质 (1)、G与G*的对应(duyng)关系 1)G*的顶点(dngdin)数等于G的面数；2)G*的边数等于G的边数；3)G*的面数等于G的顶点数；4)d(v*)=deg(f)对偶图面边割边环边割集回路点边环割边回路边割集对 应平面图G第18页/共32页第十八页，共32页。19 (2)、定理(dngl)5 定理5 平面图G的对偶(du u)图必然连通 证明(zhngmng)：在G*中任意取两点vi*与vj*。我们证明(zhngmng)该两点连通即可！用一条曲线 l 把vi*和vj*连接起来，且 l 不与G*的任意顶点相交。显然，曲线 l 从vi*到vj*经过的面边序列，对应从vi*到v

12、j*的点边序列，该点边序列就是该两点在G*中的通路。注:(1)由定理5知：(G*)*不一定等于G;第19页/共32页第十九页，共32页。20 证明(zhngmng)：“必要性”(2)G是平面图，则 当且仅当G是连通(lintng)的。(习题第26题)由于G是平面图，由定理(dngl)5，G*是连通的。而由G*是平面图，再由定理(dngl)5，(G*)*是连通的。所以，由 得：G是连通的。“充分性”由对偶图的定义知，平面图 G与其对偶图G*嵌入在同一平面上，当G连通时，容易知道：G*的无界面 f*中仅含G的唯一顶点v,而除v外，G中其它顶点u均与G*的有限面形成一一对应，于是，G中顶点和G*顶点

13、在这种自然对应方式下一一对应，且对应顶点间邻接关系保持不变，故：第20页/共32页第二十页，共32页。21 (3)同构的平面图可以(ky)有不同构的对偶图。例如(lr)，下面的两个图：G1G2 但 这是因为：G2中有次数是1的面，而G1没有次数是1的面。所以，它们(t men)的对偶图不能同构。第21页/共32页第二十一页，共32页。22 第一次上交(shn jio)作业 第3章 习题(xt)3：1，7，9，16.第4章 习题(xt)4：3，7，10，12.第5章 习题5：1，2，6，7，13，19。第22页/共32页第二十二页，共32页。23 作业(zuy)P143-146 习题(xt)5：

14、3，4，5，6，8，25,26，27。其中(qzhng)25，26，27结合课件学习。第23页/共32页第二十三页，共32页。24Thank You!第24页/共32页第二十四页，共32页。25 例2 证明(zhngmng)：(1)B是平面图G的极小(j xio)边割集，当且仅当 是G*的圈。(2)欧拉平面图的对偶(du u)图是偶图。示意图第25页/共32页第二十五页，共32页。26 证明(zhngmng):(1)对B的边数作数学(shxu)归纳。示意图 当B的边数n=1时，B中边是割边 显然(xinrn)，在G*中对应环。所以，结论成立。设对B的边数nk 时，结论成立。考虑n=k的情形。设

15、c1 B,于是B-c1是G-c1=G1的一个极小边割集。由归纳假设：是G1*的一个圈。且圈C1*上的顶点对应于G1中的面f,f 的边界上有极小边割集 B-e1的边。第26页/共32页第二十六页，共32页。27 现在(xinzi)，把e1加入到G1中，恢复G。示意图G1 由于G是平面图，其作用相当于圈C1*上的一个顶点(dngdin)对应于G1中的一个平面区域 f,被e1划分成两个顶点(dngdin)f1*与f2*,并在其间连以e1所对应的边e1*。所以，B对应在G*中的C*仍然是一个圈。由归纳法，结论(jiln)得到证明。示意图第27页/共32页第二十七页，共32页。28 充分性：G*中的一个

16、圈，对应(duyng)于G中 的边的集合B显然(xinrn)是G中的一个边割集。示意图 若该割集不是(b shi)极小边割集，则它是 G中极小边割集之和。而由必要性知道：每个极小边割集对应G*的一个圈，于是推出 B在G*中对应的边集合是圈之并。但这与假设矛盾。(2)因欧拉图的任意边割集均有偶数条边。于是由(1),G*中不含奇圈。所以G*是偶图。第28页/共32页第二十八页，共32页。29 例3 设T是连通(lintng)平面图G的生成树，证明：T*=G*E*是G*中的生成(shn chn)树。(习题第27题)示意图第29页/共32页第二十九页，共32页。30 证明：情形(qng xing)1，

17、如果G是树。在这种情况下，E*=.则T*是平凡图，而G*的生成(shn chn)树也是平凡图，所以，结论成立；情形2，如果(rgu)G不是树。因G的每个面必然含有边 e不属于E(T),即G*的每个顶点必然和E*中的某边关联，于是T*必然是G*的生成子图。下面证明：T*中没有圈。若T*中有圈。则由例2知：T的余树中含有G的极小边割集。但我们又可以证明：如果T是连通图G的生成树，那么，T的余树不含G的极小边割集。这样，T*不能含G*的圈。第30页/共32页第三十页，共32页。31 又因在G中，每去掉(q dio)T的余树中的一条边，G的面减少一个，当T的余树中的边全去掉(q dio)时，G变成一颗树T.于是(ysh)，有：所以(suy)，T*是G*的生成树。第31页/共32页第三十一页，共32页。32感谢您的观看(gunkn)！第32页/共32页第三十二页，共32页。