《第八章图(可平面图).ppt》由会员分享，可在线阅读，更多相关《第八章图(可平面图).ppt（22页珍藏版）》请在三一办公上搜索。
1、1,8.7 可平面图 Planar Graphs,2,8.7 可平面图 Planar Graphs,例：,有六个结点的图如上，试问：能否转变成与其等价的，但没有任何相交线的平面上的图？结论：不能,3,8.7 可平面图 Planar Graphs,DEFINITION A graph is called planar(可平面的)if it can be drawn in the plane without any edges crossing.Such a drawing is called a planar representation(平面表示)of the graph,4,例：,8.7 可
2、平面图 Planar Graphs,5,例：,8.7 可平面图 Planar Graphs,6,8.7 可平面图 Planar Graphs,一个图的可平面表示把平面分割成一些面，包括一个无界的面。包围每个面的边界的长度称为面的次数，记为Deg(R)。,7,8.7 可平面图Planar Graphs,EULERS FORMULA Let G be a connected planar simple graph with e edges and v vertices.Let r be the number of regions in a planar representation of G.Th
3、en r=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 可平面图Planar Graphs,9,归纳步骤：设图G的面为r时，r=e-v+2成立。证明面数为r=r+1时，等式也成立。(a)先构成图G，其中点数为v,边数为e,面数为r；(b)在G中，加入一条长度为L的简单通路（L1）,且与G共有二个结点，从而使G变为G；,8.7 可平面图Planar Graphs,10,(c)e-v+2=(e+L)-(v+(L-1)+2=e+L-v-L
4、+1+2=e-v+2+1=r+1=r定理成立,8.7 可平面图Planar Graphs,L条边(L-1)个点,G,11,8.7 可平面图Planar Graphs,COROLLARY If G is a connected planar simple graph with e edges and v vertices,where v3,then e3v-6。,12,8.7 可平面图Planar Graphs,证明：G为简单连通平面图每一面至少用三条或更多条边构成，=所有面的边的总数。因此边的总数 3r（包含重复计算的边）,13,8.7 可平面图Planar Graphs,一条边是在至多二个面
5、的边界中，各面的实际总边数一定有3r（2e）即 成立,14,8.7 可平面图Planar Graphs,由欧拉定理：,15,8.7 可平面图Planar Graphs,例：证明K5图不是平面图 K5图中，v=5,e=10,3*5-6=910 K5图不为平面图思考：证明K3,3不是平面图,16,8.7 可平面图Planar Graphs,COROLLARY If G is a connected planar simple graph,then G has a vertex of degree not exceeding five.COROLLARY If a connected planar
6、simple graph has e edges and v vertices with v3 and no circuits of length three,then e2v-4.,17,8.7 可平面图Planar Graphs,Elementary subdivision(初等细分)Removing an edge u,v and adding a new vertex w together with edges u,w and w,vThe graphs G1 and G2 are called homeomorphic(同胚)if they can be obtained from
7、the same graph by a sequence of elementary subdivisions.,18,8.7 可平面图Planar Graphs,例：同胚图,19,8.7 可平面图Planar Graphs,THEOREM A graph is nonplanar if and only if it contains a subgraph homeomorphic to K3,3 or K5.,20,8.7 可平面图Planar Graphs,Example:Determine whether the following graph is planar,21,8.7 可平面图Planar Graphs,Example:,22,8.7 可平面图Planar Graphs,Example:,
