第八章 图 (可平面图)

《第八章 图 (可平面图)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、8.7可平面图PlanarGraphs18.7可平面图PlanarGraphs例：有六个结点的图如上，试问：能否转变成与其等价的，但没有任何相交线的平面上的图？结论：不能28.7可平面图PlanarGraphsDEFINITIONAgraphiscalledplanar(可平面的)ifitcanbedrawnintheplanewithoutanyedgescrossing.Suchadrawingiscalledaplanarrepresentation(平面表示)ofthegraph3例：8.7可平面图PlanarGraphs4例：8.7

2、可平面图PlanarGraphs58.7可平面图PlanarGraphs一个图的可平面表示把平面分割成一些面，包括一个无界的面。包围每个面的边界的长度称为面的次数，记为Deg(R)。68.7可平面图PlanarGraphsEULER’SFORMULALetGbeaconnectedplanarsimplegraphwitheedgesandvvertices.LetrbethenumberofregionsinaplanarrepresentationofG.Thenr=e-v+2.7证明：用数学归纳法①归纳基础：面数r=1，r=e-v+2成

3、立。面数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可平面图PlanarGraphs8②归纳步骤：设图G’的面为r’时，r’=e’-v’+2成立。证明面数为r=r’+1时，等式也成立。(a)先构成图G’，其中点数为v’,边数为e’,面数为r’；(b)在G’中，加入一条长度为L的简单通路（L≥1）,且与G’共有二个结点，从而使G’变为G；8.7可平面图PlanarGraphs9(c)e-v+2=(e’+L)-(v’+(L-1))+2=e’+L-v’-L+1+2=

4、e’-v’+2+1=r’+1=r∴定理成立8.7可平面图PlanarGraphsViVjG’r’e’v’L条边(L-1)个点G108.7可平面图PlanarGraphsCOROLLARYIfGisaconnectedplanarsimplegraphwitheedgesandvvertices,wherev≥3,thene≤3v-6。118.7可平面图PlanarGraphs证明：①∵G为简单连通平面图∴每一面至少用三条或更多条边构成，=所有面的边的总数。因此边的总数≥3r（包含重复计算的边）128.7可平面图PlanarGraphs②∵一条

5、边是在至多二个面的边界中，∴各面的实际总边数一定有3r≤（≤2e）即成立138.7可平面图PlanarGraphs③由欧拉定理：148.7可平面图PlanarGraphs例：证明K5图不是平面图∵K5图中，v=5,e=10,3*5-6=9≤10∴K5图不为平面图思考：证明K3,3不是平面图158.7可平面图PlanarGraphsCOROLLARYIfGisaconnectedplanarsimplegraph,thenGhasavertexofdegreenotexceedingfive.COROLLARYIfaconnectedplana

6、rsimplegraphhaseedgesandvverticeswithv≥3andnocircuitsoflengththree,thene≤2v-4.168.7可平面图PlanarGraphsElementarysubdivision(初等细分)Removinganedge{u,v}andaddinganewvertexwtogetherwithedges{u,w}and{w,v}ThegraphsG1andG2arecalledhomeomorphic(同胚)iftheycanbeobtainedfromthesamegraphbya

7、sequenceofelementarysubdivisions.178.7可平面图PlanarGraphs例：同胚图188.7可平面图PlanarGraphsTHEOREMAgraphisnonplanarifandonlyifitcontainsasubgraphhomeomorphictoK3,3orK5.198.7可平面图PlanarGraphsExample:Determinewhetherthefollowinggraphisplanar208.7可平面图PlanarGraphsExample:218.7可平面图PlanarGra

8、phsExample:22