资源描述
1,8.7可平面图PlanarGraphs,2,8.7可平面图PlanarGraphs,例:,有六个结点的图如上,试问:能否转变成与其等价的,但没有任何相交线的平面上的图?结论:不能,3,8.7可平面图PlanarGraphs,DEFINITIONAgraphiscalledplanar(可平面的)ifitcanbedrawnintheplanewithoutanyedgescrossing.Suchadrawingiscalledaplanarrepresentation(平面表示)ofthegraph,4,例:,8.7可平面图PlanarGraphs,5,例:,8.7可平面图PlanarGraphs,6,8.7可平面图PlanarGraphs,一个图的可平面表示把平面分割成一些面,包括一个无界的面。包围每个面的边界的长度称为面的次数,记为Deg(R)。,7,8.7可平面图PlanarGraphs,EULERSFORMULALetGbeaconnectedplanarsimplegraphwitheedgesandvvertices.LetrbethenumberofregionsinaplanarrepresentationofG.Thenr=e-v+2.,8,证明:用数学归纳法归纳基础:面数r=1,r=e-v+2成立。面数r=2,G为一多边形,且e=v=3(e=v=4),得e-v+2=3-3+2=r成立,或e-v+2=4-4+2=r成立;,8.7可平面图PlanarGraphs,9,归纳步骤:设图G的面为r时,r=e-v+2成立。证明面数为r=r+1时,等式也成立。(a)先构成图G,其中点数为v,边数为e,面数为r;(b)在G中,加入一条长度为L的简单通路(L1),且与G共有二个结点,从而使G变为G;,8.7可平面图PlanarGraphs,10,(c)e-v+2=(e+L)-(v+(L-1)+2=e+L-v-L+1+2=e-v+2+1=r+1=r定理成立,8.7可平面图PlanarGraphs,L条边(L-1)个点,G,11,8.7可平面图PlanarGraphs,COROLLARYIfGisaconnectedplanarsimplegraphwitheedgesandvvertices,wherev3,thene3v-6。,12,8.7可平面图PlanarGraphs,证明:G为简单连通平面图每一面至少用三条或更多条边构成,=所有面的边的总数。因此边的总数3r(包含重复计算的边),13,8.7可平面图PlanarGraphs,一条边是在至多二个面的边界中,各面的实际总边数一定有3r(2e)即成立,14,8.7可平面图PlanarGraphs,由欧拉定理:,15,8.7可平面图PlanarGraphs,例:证明K5图不是平面图K5图中,v=5,e=10,3*5-6=910K5图不为平面图思考:证明K3,3不是平面图,16,8.7可平面图PlanarGraphs,COROLLARYIfGisaconnectedplanarsimplegraph,thenGhasavertexofdegreenotexceedingfive.COROLLARYIfaconnectedplanarsimplegraphhaseedgesandvverticeswithv3andnocircuitsoflengththree,thene2v-4.,17,8.7可平面图PlanarGraphs,Elementarysubdivision(初等细分)Removinganedgeu,vandaddinganewvertexwtogetherwithedgesu,wandw,vThegraphsG1andG2arecalledhomeomorphic(同胚)iftheycanbeobtainedfromthesamegraphbyasequenceofelementarysubdivisions.,18,8.7可平面图PlanarGraphs,例:同胚图,19,8.7可平面图PlanarGraphs,THEOREMAgraphisnonplanarifandonlyifitcontainsasubgraphhomeomorphictoK3,3orK5.,20,8.7可平面图PlanarGraphs,Example:Determinewhetherthefollowinggraphisplanar,21,8.7可平面图PlanarGraphs,Example:,22,8.7可平面图PlanarGraphs,Example:,
展开阅读全文