可以在它的边互不相交的条件下画在平面上.pptVIP

11.3 平面图 定义11.3.1 设图G=(V, E)，若G 可以在它的边互不相交的条件下画在平面上，则称G为平面图，或称G为可嵌入平面的。 例 平面图 在图G的边(v1, v2)上插入一个顶点u是指：删去G的边(v1, v2)，然后添加一个新的顶点u以及新的边 (v1, u)和(u, v2)。 在图G的某些边上插入若干个顶点后得到图G1，则称G1是G的一个剖分。 库拉托斯基(Kuratowski)定理 定理11.3.1 图G为平面图的充要条件是G的任何子图都不含有K3, 3或K5及其的剖分。 定义11.3.2 设G为平面图，则G把平面划分成若干个连通区域，称这种连通区域为G的一个面，记作 f。该连通区域的边界称为 f 的边界。而f 的边界作为G中的圈，其长度称为 f 的度，记作d(f)。并记G的面的集合为F，于是平面图G可表示为G=(V, E, F)。 平面图G中无界的面称为G的外部面，而其余的面称为G的内部面， 例如，在图所表示的平面图G中，有7个顶点，9条边和4个面。其中 f1为G的外部面，f2, f3, f4为内部面，各个面的度分别为d(f1) =7, d(f2)=3, d(f3)=3而d(f4)=5。 注意，图G的边(3, 4)作为面f1的边界在计算长度时要计数2次。同样，对于面f4边界的边(2, 7)也计数2次。 定理11.3.2 设平面图G=(V, E, F)是连通的，则 推论11.3.1 设平面图G=(V, E, F)，且|V|≥3，则 |E|≤ 3|V|-6 证 只需对连通的平面图证明即可。设G为连通的平面图，则G的每个面都至少由3条边围城，即d( f ) ≥3，于是Sd( f ) ≥ 3|F|。再由定理11.3.2可知， 2|E|≥ 3|F|，结合欧拉公式|V|-|E|+|F|=2可得|E|≤ 3|V|-6。 推论11.3.2 设平面图G=(V, E, F)，且对于G的每个面都有d( f ) ≥ 4，则|E|≤ 2|V|-4 。 例11.3.2 证明完全二分图K3, 3和完全图K5不是平面图。 证 反证法 因为在完全图K5=(V, E, F)中，|V|=5，|E|=10，不满足推论11.3.1中的公式。 对于完全二分图K3, 3 =(V, E, F)有，|V|=6，|E|= 9，不满足推论11.3.2中的公式。 定理11.3.4 设G=(V, E, F)是连通的平面图，且|V|≥3，则存在顶点v，使d(v) ≤ 5。 证 反证法。假设对连通的平面图G中每个顶点v，都有d(v) ≥ 6，则由图的边数与顶点的度数之和的关系公式Sd( v ) = 2|E|以及|V|≥ 3，得 2|E|≥ 6|V|也即|E|≥3|V|3|V|-6，与推论11.3.1的结论矛盾。 * * 图G G的剖分 f1 f2 f3 f4 1 2 7 3 4 5 6 定理11.3.3 设平面图G=(V, E, F)是连通的，则 |V|-|E|+|F|=2 *