第八章图(可平面图)2.pptVIP

8.7 可平面图 Planar Graphs 8.7 可平面图 Planar Graphs 例： 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 8.7 可平面图 Planar Graphs 例： 8.7 可平面图 Planar Graphs 例： 8.7 可平面图 Planar Graphs 一个图的可平面表示把平面分割成一些面，包括一个无界的面。包围每个面的边界的长度称为面的次数，记为Deg(R)。 8.7 可平面图Planar Graphs EULER’S 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. Then r=e-v+2. 8.7 可平面图Planar Graphs 证明：用数学归纳法 ①归纳基础： 面数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 ②归纳步骤： 设图G’的面为r’时，r’=e’-v’+2成立。 证明面数为r=r’+1时，等式也成立。 (a)先构成图G’，其中点数为v’,边数为e’,面数为r’； (b)在G’中，加入一条长度为L的简单通路（L≥1）,且与G’共有二个结点，从而使G’变为G； 8.7 可平面图Planar Graphs (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 可平面图Planar Graphs COROLLARY If G is a connected planar simple graph with e edges and v vertices, where v≥3, then e≤3v-6。 8.7 可平面图Planar Graphs 证明： ①∵G为简单连通平面图 ∴每一面至少用三条或更多条边构成， =所有面的边的总数。 因此边的总数 ≥3r（ 包含重复计算的边） 8.7 可平面图Planar Graphs ②∵一条边是在至多二个面的边界中， ∴各面的实际总边数一定有3r≤（ ≤2e） 即 成立 8.7 可平面图Planar Graphs 8.7 可平面图Planar Graphs 例：证明K5图不是平面图 ∵ K5图中，v=5,e=10, 3*5-6=9≤10 ∴ K5图不为平面图 思考：证明K3,3不是平面图 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 simple graph has e edges and v vertices with v≥3 and no circuits of length three, then e≤2v-4. 8.7 可平面图Planar Graphs Elementary subdivision(初等细分) Removing an edge {u, v} and adding a new vertex w together with edges {u, w} and {w, v} The graphs G1 and G2 are called homeomorphic(同胚) if they can be obtained from the same graph by a sequence of elementary subdivisions. 8.7 可平面图Planar Graphs 例：同胚图 8.7 可平面图Planar Graphs THEOREM A graph is nonplanar if