第章平面图.ppt

图论及其应用 第九章 平面图 9.1平图和平面图 称 图G可嵌入（embededable）于平面中? G可画在平面上，使它的边只在端点处才可能相交叉。 （该几何实现称为G的一个 平面嵌入（planar embedding） 或 平图（plane graph））? G为平面图（planar graph） 例：K5，K3,3 以及它们的剖分都是非平面图。它们中任一个去掉任一边后都是平面图。 注意：平面图和平图间的区别。后者是前者的一个几何实现（具体画法）。 Jordan 曲线定理：平面中任一Jordan 曲线J（连续不自交的闭曲线），将余下的平面划分成二不相交开集：J的内部（interior）和 J的外部（exterior），分别记为 int J和ext J。（它们的闭包分别记为Int J 和 Ext J）。连接int J中一点到ext J中一点的任一条曲线一定与J交于某一点。 9.1平图和平面图——定理9.1 定理9.1 K5为非平面图。 证明：反证，假设G为K5的一个平图。令G 的五个顶点为v1，… ，v5。注意到圈C = v1v2v3v1 为平面上的一条Jordan 曲线，且v4必在int C 或ext C中。若v4 ? int C：则边v4v1， v4v2，与v4v3将int C划分成三个区域int C1，int C2，和int C3。这时v5 一定在上述三个区域及区域 ext C之一。若v5 ? ext C，则因v4 ? int C，边v4v5 必与C交于某一点，这与G为平面图的假设相矛盾。 其它情形类似地也导致矛盾。 # 定理9.1’ K3,3为非平面图。 证明：类似，略。 平面嵌入的慨念可推广到其它平面上。称图G可嵌入于曲面S上 ?G可画在S上，使它的边仅在端点处才可能相交叉。 例。K5和K3,3都可嵌入于环面上； K3,3可嵌入于Mobius带上；每个图都可“嵌入”于三维空间R3中。 9.1平图和平面图——定理9.2 定理9.2 G可嵌入于平面上 ? G可嵌入于球面上。 证明：利用球极平面射影，略。 # 9.1平图和平面图——习题 9.1.1 证明：不存在5区域地图，其中每对区域都相邻。 9.1.2 证明： K5 – e及K3,3 – e为平面图，其中e为其任一边。 9.2 对偶图 平图G的面（face） ? G将平面划分出来的连通区域的闭包。 外部面（exterior face） ? G中唯一的无界面。 定理9.3. 对平面图G 的任一顶点，都存在G的一个平面嵌入，使它在该嵌入的外部面。 证明： 先将G嵌入于球面上，并将球面的北极放在包含该顶点的G的一个面中，再利用球极平面射影。 # 记号 F(G) = 平图G的面的集合。 ?(G) = 平图G的面数。  b(f) = 面f的周界。　 当G连通时，b(f)可当作一闭途径，其中G在b(f)中的每一割边在该途径中都恰被走过两次。 当G为2-连通时，b(f) 为一圈。 9.2 对偶图 例： b(f1) = v1e1v2e5v4e8v6e9v6e8v4e4v1e6v7e7v7e6v1 。 b(f5) = v1e1v2e2v3e3v4e4v1 。 在平图G中 称面f与它的周界上的边和顶点相关联。G的一边e分隔（seperate）与它相关联的面。面f的度（degree） dG(f) = 与面f 相关联的边数（割边记为2） 例如，d(f1) = 9。易见：e为G的割边 ? e只与G的一个面相关联 ? e恰分隔G的一个面e为G的非割边 ? e恰与G的两个面相关联 ? e恰分隔G的两个面 9.2 对偶图 平图G的对偶图（dual graph）G*是这样的一个图：它们之间有如下的一一对应关系 G的面f ? G*的顶点f* ； G的边e ? G*的边e* 。且 G*的顶点f1* 与f2* 被边e* 连接 ? G的面f1与f2 被边e分隔。 例如，左上所示平图G的对偶图G* = (V* , E*) 为V*={f1*，……，f5*} ，E*={e1*= f1*f5*,e2*=f5*f5*,e3*=f2*f5*,……,e8*=f2*f3*} 。 9.2 对偶图 平图G的对偶图G*是一平面图：事实上存在G* 的一个平面嵌入（称为几何对偶）如下：在G的每个面f中放置顶点f*，对应于G的每一边e，画一条边e* 使它穿过e恰