《图论特殊平面图与平面图的对偶图精.ppt》由会员分享，可在线阅读，更多相关《图论特殊平面图与平面图的对偶图精.ppt（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图论课件特殊平面图与平面图的对偶图1 1第1页，本讲稿共34页本次课主要内容本次课主要内容(一一)、一些特殊平面图、一些特殊平面图(二二)、平面图的对偶图、平面图的对偶图特殊平面图与平面图的对偶图特殊平面图与平面图的对偶图 1、极大平面图及其性质、极大平面图及其性质 2、极大外平面图及其性质、极大外平面图及其性质2第2页，本讲稿共34页 1、极大平面图及其性质、极大平面图及其性质(一一)、一些特殊平面图、一些特殊平面图 对于一个简单平面图来说，在不邻接顶点对间加边，当边数对于一个简单平面图来说，在不邻接顶点对间加边，当边数增加到一定数量时，就会变成非平面图。这样，就启发我们研增加到一定数量时，
2、就会变成非平面图。这样，就启发我们研究平面图的极图问题。究平面图的极图问题。定义定义1 设设G是简单可平面图，如果是简单可平面图，如果G是是Ki(1i4),i4),或者或者在在G G的任意非邻接顶点间添加一条边后，得到的图均是非可平面图，的任意非邻接顶点间添加一条边后，得到的图均是非可平面图，则称则称G G是极大可平面图。是极大可平面图。极大可平面图的平面嵌入称为极大平面图。极大可平面图的平面嵌入称为极大平面图。3第3页，本讲稿共34页 注：只有在单图前提下才能定义极大平面图。注：只有在单图前提下才能定义极大平面图。引理引理 设设G G是极大平面图，则是极大平面图，则G G必然连通；若必然连通
3、；若G G的阶数大于等的阶数大于等于于3 3，则，则G G无割边。无割边。极大平面极大平面图图非极大平非极大平面图面图极大平面极大平面图图 (1)(1)先证明先证明G G连通。连通。若不然，若不然，G G至少两个连通分支。设至少两个连通分支。设G G1 1与与G G2 2是是G G的任意两个连通分的任意两个连通分支。支。4第4页，本讲稿共34页 把把G G1 1画在画在G G2 2的外部面上，并在的外部面上，并在G G1 1,G,G2 2上分别取一点上分别取一点u u与与v.v.连接连接u u与与v v得到一个新平面图得到一个新平面图G G*。但这与。但这与G G是极大平面图相矛盾。是极大平面
4、图相矛盾。(2)(2)当当G G的阶数的阶数n3n3时，我们证明时，我们证明G G中没有割边。中没有割边。若不然，设若不然，设G G中有割边中有割边e=uve=uv，则，则G-uvG-uv不连通，恰有两个连通不连通，恰有两个连通分支分支G G1 1与与G G2 2。设设u在在G1中，而中，而v在在G2中。由于中。由于n3,所以，至少有一个分支所以，至少有一个分支包含两个以上的包含两个以上的顶顶点。点。设设G2至少含有两个至少含有两个顶顶点。又点。又设设G1中含有点中含有点u的面是的面是 f,将将G2画在画在 f 内。内。由于由于G是单图，所以，在是单图，所以，在G2的外部面上存在不等于点的外部
5、面上存在不等于点v的点的点t。现在，在。现在，在G中连接点中连接点u与与t得新平面图得新平面图G*,它比它比G多一条边。这多一条边。这与与G的极大性相矛盾。的极大性相矛盾。5第5页，本讲稿共34页 下面证明极大平面图的一个重要性质。下面证明极大平面图的一个重要性质。定理定理1 设设G是至少有是至少有3个顶点的平面图，则个顶点的平面图，则G是极大平面图，是极大平面图，当且仅当当且仅当G的每个面的次数是的每个面的次数是3且为单图。且为单图。注：该定理可以简单记为是注：该定理可以简单记为是“极大平面图的三角形特征极大平面图的三角形特征”，即，即每个面的边界是三角形。每个面的边界是三角形。证明：证明：
6、“必要性必要性”由引理知，由引理知，G是单图、是单图、G无割边且无割边且G的每个面的次数至少是的每个面的次数至少是3。假设假设G中某个面中某个面f的次数大于等于的次数大于等于4。记。记f的边界是的边界是v1v2v3v4vk。如下图所示。如下图所示。6第6页，本讲稿共34页 如果如果v1与与v3不邻接，则连接不邻接，则连接v1v3，没有破坏，没有破坏G的平面性，这与的平面性，这与G是极大平面图矛盾。所以是极大平面图矛盾。所以v1v3必须邻接，但必须在必须邻接，但必须在 f 外连外连线；同理线；同理v2与与v4也必须在也必须在f外连线。但边外连线。但边v1v3与边与边v2v4在在 f 外交外交叉，
7、与叉，与G是平面图矛盾！是平面图矛盾！所以，所以，G的每个面次数一定是的每个面次数一定是3.定理的充分性是显然的。定理的充分性是显然的。v1v2v3v4v5vkf7第7页，本讲稿共34页 推论：设推论：设G是是n个点，个点，m条边和条边和个面的极大平面图，且个面的极大平面图，且n3.n3.则：则：(1)m=3n-6;(2)(1)m=3n-6;(2)=2n-4.=2n-4.证明：因为证明：因为G是极大平面图，所以，每个面的次数为是极大平面图，所以，每个面的次数为3.由次数由次数公式：公式：由欧拉公式：由欧拉公式：所以得：所以得：8第8页，本讲稿共34页 所以得：所以得：又又 所以：所以：注：顶点
8、数相同的极大平面图并不唯一。例如：注：顶点数相同的极大平面图并不唯一。例如：正正20面体面体非正非正20面体面体9第9页，本讲稿共34页 还在研究中的问题是：顶点数相同的极大平面图的个数和结还在研究中的问题是：顶点数相同的极大平面图的个数和结构问题。构问题。2、极大外平面图及其性质、极大外平面图及其性质 与极大平面图相对应的图是极小平面图。与极大平面图相对应的图是极小平面图。定义定义2 若一个可平面图若一个可平面图G存在一种平面嵌入，使得其所有顶点存在一种平面嵌入，使得其所有顶点均在某个面的边界上，称该图为外可平面图。外可平面图的一种外均在某个面的边界上，称该图为外可平面图。外可平面图的一种外
9、平面嵌入，称为外平面图。平面嵌入，称为外平面图。外可平面图外可平面图外平面图外平面图1外平面图外平面图210第10页，本讲稿共34页 注：对外可平面图注：对外可平面图G来说，一定存在一种外平面嵌入，使得来说，一定存在一种外平面嵌入，使得G的顶点均在外部面的边界上。这由球极投影法可以说明。的顶点均在外部面的边界上。这由球极投影法可以说明。下面研究极大外平面图的性质。下面研究极大外平面图的性质。定义定义3 设设G是一个简单外可平面图，若在是一个简单外可平面图，若在G中任意不邻接顶点中任意不邻接顶点间添上一条边后，间添上一条边后，G成为非外可平面图，则称成为非外可平面图，则称G是极大外可平是极大外可
10、平面图。极大外可平面图的外平面嵌入，称为极大外平面图。面图。极大外可平面图的外平面嵌入，称为极大外平面图。极大外平面图极大外平面图11第11页，本讲稿共34页 引理引理 设设G是一个连通简单外可平面图，则在是一个连通简单外可平面图，则在G中有一个度数中有一个度数至多是至多是2的顶点。的顶点。证明证明 我们对我们对G的阶数的阶数n作数学归纳。作数学归纳。当当n33时，引理结论显然成立；当时，引理结论显然成立；当n=4n=4时，由于时，由于K K4 4不能是外不能是外可平面图，所以，四阶的外可平面图至少有一个顶点度数不超可平面图，所以，四阶的外可平面图至少有一个顶点度数不超过过2 2。事实上，更强
11、一点的结论是：当。事实上，更强一点的结论是：当n=4n=4时，有两个不邻时，有两个不邻接顶点，其度数不超过接顶点，其度数不超过2.2.设当设当G是一个阶数小于是一个阶数小于n的简单连通外可平面图时，存在两个的简单连通外可平面图时，存在两个不邻接顶点，其度数不超过不邻接顶点，其度数不超过2。考虑考虑G是一个阶数等于是一个阶数等于n的简单连通外可平面图。的简单连通外可平面图。情形情形1，如果，如果G有割点有割点x12第12页，本讲稿共34页 由归纳假设，由归纳假设，G-x的两个不同分支中分别有一个异于的两个不同分支中分别有一个异于x的顶的顶点点z与与z1,使得度数不超过使得度数不超过2。这说明。这
12、说明G中有两个不邻接顶点中有两个不邻接顶点,使使得度数都不超过得度数都不超过2；x 情形情形2 若若G是是2连通的。连通的。考虑考虑G的任意一种外平面嵌入。则的任意一种外平面嵌入。则G的外部面边界一定是圈。的外部面边界一定是圈。否则，容易推出否则，容易推出G有割点。有割点。设设C是是G的外平面嵌入的外部面边界。若除的外平面嵌入的外部面边界。若除C外，图中没外，图中没有其它的边，则有其它的边，则G=C,显然显然G中有不邻接点，度数不超过中有不邻接点，度数不超过2；13第13页，本讲稿共34页 若除若除C外，图中至少有边外，图中至少有边xy。如下图所示：。如下图所示：xy 则在则在C上的两条上的两
13、条xy路上的点在路上的点在G中的两个导出子图中的两个导出子图H1与与H2是外平面图。是外平面图。有归纳假设，在有归纳假设，在H1,H2中分别存在异于中分别存在异于x,y的点的点z与与z1,使得，使得，它们的度数不超过它们的度数不超过2.xyzz114第14页，本讲稿共34页 定理定理2 设设G是一个有是一个有n(n3)个点，且所有点均在外部面上的极个点，且所有点均在外部面上的极大外平面大外平面图图，则则G有有n-2个内部面。个内部面。证明：对证明：对G的阶数作数学归纳。的阶数作数学归纳。当当n=3时，时，G是三角形，显然只有一个内部面；是三角形，显然只有一个内部面；设当设当n=k时，结论成立。
14、时，结论成立。当当n=k+1时，首先，注意到时，首先，注意到G必有一个必有一个2度顶点度顶点u在在G的外部面上。的外部面上。(这可以由上面引理得到这可以由上面引理得到)考虑考虑G1=G-v。由归纳假设，。由归纳假设，G1有有k-2个内部面。这样个内部面。这样G有有k-1个个内部面。于是定理内部面。于是定理2得证。得证。15第15页，本讲稿共34页 定理定理3 设设G是一个有是一个有n(n3)个点，且所有点均在外部面上的外个点，且所有点均在外部面上的外平面平面图图，则则G是极大外平面是极大外平面图图，当且，当且仅仅当其外部面的当其外部面的边边界是圈，界是圈，内部面是三角形。内部面是三角形。注：这
15、是极大外平面图的典型特征。注：这是极大外平面图的典型特征。证明：先证明必要性。证明：先证明必要性。(1)证明证明G的边界是圈。的边界是圈。设设W=v1v2vnv1是是G的外部面边界。若的外部面边界。若W不是圈，则存在不是圈，则存在i与与j,使使得：得：1i,jn,i,jn,且且j-i1(modn),j-i1(modn),使使v vi i=v=vj j=v.=v.此时，此时，G G可以示意可以示意如下：如下：W vi-1 v1vnv2vi+1vj-1vj+1v16第16页，本讲稿共34页 vi-1与与vi+1不能邻接。否则不能邻接。否则W不能构成不能构成G的外部面边界。这样，我的外部面边界。这样
16、，我们连接们连接vi-1与与vi+1：vi-1 v1vnv2vi+1vj-1vj+1v 得到一个新外平面图。这与得到一个新外平面图。这与G的极大性矛盾。的极大性矛盾。(2)证明证明G的内部面是三角形。的内部面是三角形。首先，注意到，首先，注意到，G的内部面必须是圈。因为，的内部面必须是圈。因为，G的外部面的边界的外部面的边界是生成圈，所以是生成圈，所以G是是2连通的，所以，连通的，所以，G的每个面的边界必是圈。的每个面的边界必是圈。17第17页，本讲稿共34页 其次，设其次，设C是是G中任意一个内部面的边界。如果中任意一个内部面的边界。如果C的长度大于等的长度大于等于于4，则，则C中一定存在不
17、邻接顶点，连接这两点得到一个新平中一定存在不邻接顶点，连接这两点得到一个新平面图，这与面图，这与G的极大性矛盾。又由于的极大性矛盾。又由于G是单图，所以是单图，所以C的长度只的长度只能为能为3.下面证明充分性。下面证明充分性。设设G是一个外平面图，内部面是三角形，外部面是圈是一个外平面图，内部面是三角形，外部面是圈W.如果如果G不是极大外平面图，那么存在不邻接顶点不是极大外平面图，那么存在不邻接顶点u与与v,使得使得G+uv是外平面图。是外平面图。但是，但是，G+uv不能是外平面图。因为，若边不能是外平面图。因为，若边uv经过经过W的内部，则的内部，则它要与它要与G的其它边相交；若的其它边相交
18、；若uv经过经过W的外部，导致所有点不能在的外部，导致所有点不能在在在G的同一个面上。的同一个面上。所以，所以，G是极大外平面图。是极大外平面图。18第18页，本讲稿共34页 定理定理4 每个至少有每个至少有7个顶点的外可平面图的补图不是外可个顶点的外可平面图的补图不是外可平面图，且平面图，且7是这个数目的最小者。是这个数目的最小者。我们用枚举方法证明。我们用枚举方法证明。证明：对于证明：对于n=7的极大外可平面图来说，只有的极大外可平面图来说，只有4个。如下图所个。如下图所示。示。直接验证：它们的补图均不是外可平面的。直接验证：它们的补图均不是外可平面的。而当而当n=6时，我们可以找到一个外
19、可平面图时，我们可以找到一个外可平面图G(见下图见下图),使得使得其补图是外可平面图。其补图是外可平面图。19第19页，本讲稿共34页(二二)、平面图的对偶图、平面图的对偶图 1、对偶图的定义、对偶图的定义 定义定义4 给定平面图给定平面图G，G的对偶图的对偶图G*如下构造：如下构造：(1)在在G的每个面的每个面fi内取一个点内取一个点vi*作为作为G*的一个顶点；的一个顶点；(2)对对G的一条边的一条边e,若若e是面是面 fi 与与 fj 的公共边，则连接的公共边，则连接vi*与与vj*，且连线穿过边且连线穿过边e;若若e是面是面fi中的割边，则以中的割边，则以vi为顶点为顶点20第20页，
20、本讲稿共34页作环，且让它与作环，且让它与e相交。相交。例如，作出平面图例如，作出平面图G的对偶图的对偶图G*G21第21页，本讲稿共34页 2、对偶图的性质、对偶图的性质 (1)、G与与G*的对应关系的对应关系 1)G*的顶点数等于的顶点数等于G的面数；的面数；2)G*的边数等于的边数等于G的边数；的边数；3)G*的面数等于的面数等于G的顶点数；的顶点数；4)d(v*)=deg(f)对偶图面边割边环边割集回路点边环割边回路边割集对 应平面图G22第22页，本讲稿共34页 (2)、定理、定理5 定理定理5 平面图平面图G的对偶图必然连通的对偶图必然连通 证明：在证明：在G*中任意取两点中任意取
21、两点vi*与与vj*。我们证明该两点连通即可！。我们证明该两点连通即可！用一条曲线用一条曲线 l 把把vi*和和vj*连接起来，且连接起来，且 l 不与不与G*的任意顶点相的任意顶点相交。交。显然，曲线显然，曲线 l 从从vi*到到vj*经过的面边序列，对应从经过的面边序列，对应从vi*到到vj*的点边的点边序列，该点边序列就是该两点在序列，该点边序列就是该两点在G*中的通路。中的通路。注注:(1)由定理由定理5知：知：(G*)*不一定等于不一定等于G;23第23页，本讲稿共34页 证明：证明：“必要性必要性”(2)G是平面图，则是平面图，则 当且仅当当且仅当G是连通的。是连通的。(习题习题第
22、第26题题)由于由于G是平面图，由定理是平面图，由定理5，G*是连通的。而由是连通的。而由G*是平面图，是平面图，再由定理再由定理5，(G*)*是连通的。是连通的。所以，由所以，由 得：得：G是连通的。是连通的。“充分性充分性”由对偶图的定义知，平面图由对偶图的定义知，平面图G与其对偶图与其对偶图G*嵌入在同一平面上，嵌入在同一平面上，当当G连通时，容易知道：连通时，容易知道：G*的无界面的无界面 f*中仅含中仅含G的唯一顶点的唯一顶点v,而除而除v外，外，G中其它顶点中其它顶点u均与均与G*的有限面形成一一对应，且对应顶点间邻的有限面形成一一对应，且对应顶点间邻接关系保持不变，即：接关系保持
23、不变，即：24第24页，本讲稿共34页 (3)同构的平面图可以有不同构的对偶图。同构的平面图可以有不同构的对偶图。例如，下面的两个图：例如，下面的两个图：G1G2 但但 这是这是因为：因为：G2中有次数是中有次数是1的面，而的面，而G1没有次数是没有次数是1的面。的面。所以，它们的对偶图不能同构。所以，它们的对偶图不能同构。25第25页，本讲稿共34页 例例2 证明：证明：(1)B是平面图是平面图G的极小边割集，当且仅当的极小边割集，当且仅当 是是G*的圈。的圈。(2)欧拉平面图的对偶图是偶图。欧拉平面图的对偶图是偶图。示意图示意图26第26页，本讲稿共34页 证明证明:(1)对对B的边数作数
24、学归纳。的边数作数学归纳。示意图示意图 当当B的边数的边数n=1时，时，B中边是割边中边是割边 显然，在显然，在G*中对应环。所以，结论成立。中对应环。所以，结论成立。设对设对B的边数的边数nk 时，结论成立。考虑时，结论成立。考虑n=k的情形。的情形。设设c1 B,于是于是B-c1是是G-c1=G1的一个极小边割集。由归纳假的一个极小边割集。由归纳假设：设：是是G1*的一个圈。且圈的一个圈。且圈C1*上的顶点对应于上的顶点对应于G1中的面中的面f,f 的边界上有的边界上有极小边割集极小边割集B-e1的边。的边。27第27页，本讲稿共34页 现在，把现在，把e1加入到加入到G1中，恢复中，恢复
25、G。示意图示意图G1 由于由于G是平面图，其作用相当于圈是平面图，其作用相当于圈C1*上的一个顶点对应于上的一个顶点对应于G1中中的一个平面区域的一个平面区域 f,被被e1划分成两个顶点划分成两个顶点f1*与与f2*,并在其间连以并在其间连以e1所所对应的边对应的边e1*。所以，所以，B对应在对应在G*中的中的C*仍然是一个圈。由归纳法，结论仍然是一个圈。由归纳法，结论得到证明。得到证明。示意图示意图28第28页，本讲稿共34页 充分性：充分性：G*中的一个圈，对应于中的一个圈，对应于G中中 的边的集合的边的集合B显然是显然是G中的一个边割中的一个边割集。集。示意图示意图 若该割集不是极小边割
26、集，则它是若该割集不是极小边割集，则它是G中极小边割集之和。而中极小边割集之和。而由必要性知道：每个极小边割集对应由必要性知道：每个极小边割集对应G*的一个圈，于是推出的一个圈，于是推出B在在G*中对应的边集合是圈之并。但这与假设矛盾。中对应的边集合是圈之并。但这与假设矛盾。(2)因欧拉图的任意边割集均有偶数条边。于是由因欧拉图的任意边割集均有偶数条边。于是由(1),G*中不含中不含奇圈。所以奇圈。所以G*是偶图。是偶图。29第29页，本讲稿共34页 例例3 设设T是连通平面图是连通平面图G的生成树，的生成树，证明：证明：T*=G*E*是是G*中的生成树。中的生成树。(习题第习题第27题题)示
27、意图示意图30第30页，本讲稿共34页 证明：情形证明：情形1，如果，如果G是树。是树。在这种情况下，在这种情况下，E*=.则则T T*是平凡图，而是平凡图，而G*G*的生成树也是平的生成树也是平凡图，所以，结论成立；凡图，所以，结论成立；情形情形2，如果，如果G不是树。不是树。因因G的每个面必然含有边的每个面必然含有边e不属于不属于E(T),即即G*的每个顶点必然和的每个顶点必然和E*中的某边关联，于是中的某边关联，于是T*必然是必然是G*的生成子图。的生成子图。下面证明：下面证明：T*中没有圈。中没有圈。若若T*中有圈。则由例中有圈。则由例2知：知：T的余树中含有的余树中含有G的极小边割集
28、。但的极小边割集。但我们又可以证明：我们又可以证明：如果如果T是连通图是连通图G的生成树，那么，的生成树，那么，T的余树不的余树不含含G的极小边割集的极小边割集。这样，。这样，T*不能含不能含G*的圈。的圈。31第31页，本讲稿共34页 又因在又因在G中，每去掉中，每去掉T的余树中的一条边，的余树中的一条边，G的面减少一个，的面减少一个，当当T的余树中的边全去掉时，的余树中的边全去掉时，G变成一颗树变成一颗树T.于是，有：于是，有：所以，所以，T*是是G*的生成树。的生成树。32第32页，本讲稿共34页 作业作业 P143-146 习题习题5：3，4，5，6，8，25,26，27。其中其中 25，26，27结合课件学习。结合课件学习。33第33页，本讲稿共34页Thank You!34第34页，本讲稿共34页