第7章平面图.ppt

1、您可以在平面上绘制图论及其应用程序节目、第9章平面、图论及其应用程序节目、2，9.1平面和平面，以及可包含图G(embededable)。因此，边只能在端点相交。(牙齿几何实现名为G的“平面包含”(planar embedding)或“平面”(plane graph)。g是“平面”(planar graph)的示例。K5、K3，3及其剖分都是非平面视图。除了他们中的任何一个，都是平面图。附注：楼板平面图和贴花之间的差异。后者是前者的几何实现(具体画法)。清理Jordan曲线：平面中的所有Jordan曲线J(连续不相交的闭合曲线)将其馀平面分为两个不相交的开集：J的内部(interior)和J的

2、外部(exterior)，分别记录为int J和ext J。(闭包分别写为Int J和Ext J。)将Int J中的一点连接到ext J中的一点的所有曲线必须在J和一点相交。图论及其应用，3，9.1平面和平面定理9.1，定理9.1 K5为非平面。证明：假设反证，g是K5的平面图。使g的五个顶点成为v1，V5。圆C=v1v2v3v1是平面上的约旦曲线，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必须与

3、C在一点相交。这与G是平面的假设相矛盾。其他情况同样导致冲突。#定理9.1 K3，3是非平面。证明：类似，有点。平面嵌入的概念可以扩展到其他平面。图G可以包含在曲面S中。g可以在S上绘制，因此边只能在端点相交。是的。K5和K3，3都可以嵌入圆环。K3，3可以嵌入莫比乌斯带。每个图都可以“包含”在三维空间R3中。图论及其应用、4，9.1平面和平面定理9.2、定理9.2 G可以嵌入平面。g可以嵌入球体。证明：使用球极平面投影略微。#，图论及其应用，5，9.1平面和平面练习，9.1.1证明：5没有区域地图，每个区域对都是相邻的。9.1.2证明：K5 e和K3，3 e是平面图。其中E是一边。图论及其应

4、用节目、6，9.2双度、平面G的面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)为一个轮子。图论及其应用程序节目，7，9.2双度，例如B(F1)=V1 E1 V2 e5v 4 E8 V6 E9 V6 E9 V6 E8

5、V4 E4 V1 E6 V7 E7 V7 E6 V1。B(f5)=v1e1v2e2v3e3v4e4v1。在平面G中，面F与周界的边和顶点相关。g的边e“间隔”(seperate)牙齿关联的面。面f的度dG(f)=与面f关联的面数(切面2)，例如d(f1)=9。E为G的切割边E只与G的一侧连接。E为G的非切割边E与G的两个面完全相关联。e是G的两个面、图论和应用、8，9.2双度、平面G的双度G*是这样的图。G的边e G*的边e*。然后，G*的顶点f1*和f2*通过边e*连接G的面f1和f2被边e分隔。例如，左上角显示的平面G的双精度G*=(V*，E*)为V*=f1*，f5*，e *=E1 *=f

6、1 * F5 *，E2 *=F5 *，图论及其应用，9，9.2对偶图，平面G的对偶图G*是平面图。实际上，具有G*的平面嵌入(称为几何对偶)如下：在G的每个面f上放置顶点f*，然后绘制与G的每个面e相对应的边e*，以准确地通过e。例如，以上示例平面G的双图形G*与右图相同。如上所述，G不为空时，G*必须是连接的平面。而e为G的环e*是G*的切割边。e是G的切割边，e*是G*的回路。图论及其应用，10，9.2对偶图，为了下面的方便，我们把平面G的几何对偶G*视为G的对偶图。如果此时连接了G(练习9.2.4(a)，则有G*=(G* )*G。(如果g不连接，常识就不成立。)“平面G H G* H*”

7、不一定成立。例如，右边的平度是同构，但它们的双重度徐璐是不同的结构。因此，双线的概念仅对平面有意义，不能扩展到平面。图论及其应用，11，9.2双度，通过G*的定义很容易理解：(G *)=(G)(G *)=(G)=(G)=(G)清理如果9.4设置为G，则证明：#，9.2.2 .如果同构了1平面图及其对偶图，则牙齿平面图被称为自对偶。(a)如果g是自己的对偶，则=2-2。(b)对于每个n 4，找到N顶点的自己的双平面。9.2.3 .(a)证明：B是平面G的键e* E(G*) | e B是G*的圆。(b)证明：C是平面G的圆e* E(G*) | e C是G*的键。(c)检验：欧拉平面的对偶图。9.2

8、.4 .如果将G设定为平面图，则证明(a) (G* )* G G是连接图。(b) (g * * *)=(g)。图论及其应用、13，9.2双度练习(继续)、9.2.5。T是连接平面G的生成树，E*=证明：T*=G*E*是G*的生成树。9.2.6。每个面的角度为3的平面称为平面三角剖分。证明：每个3的简单平面图是简单平面三角剖分图的生成子图。9.2.7 .将g设定为4的简单平面三角剖分。G*是简单的双边连接3-一般平面视图。9.2.8 .*证明：所有平面三角剖分图形均包含具有2 (G)/3面的偶数图形。图论及其应用，14，9.3 Euler公式定理9.5，如果定理9.5(Euler)将g设置为连接

9、平面，则-=2。对证明：进行归纳。=1时，g的每条边都是切割边(因为每条边仅分离一个面)。另外，因为G是连接的，G是树(定理2.4)，所以=-1，定理成立。假设定理对n成立(G)=n 2。承担g的非切割边E(必须存在，否则由于定理2.4，=1，矛盾)。因此，G- e仍然是连接的平面图。e分隔G的两个面是(G-e)=n-1。(由e分隔的G的两个面在G-e中合并为一个面。)。因此，归纳假设为(G-e)-(G-e) (G-e)=2。但(g-e)=(g)；(G-e)=(G)-1；(G-e)=(G)-1，代表他们常识和获得证据。#，图论及其应用，15，9 . 3 Euler公式推断，9.5.1对平面G的

10、两个平面内置H和R都(H)=(R)证明：由于H R，顶点数和边数相等。再次通过本定理获得证据。#估计值为9 . 5 . 2 . 2 3时，如果G是简单平面图，则可以将3-6证明：G设置为连接图。因为g是简单图形，所以从d(f) 3 f F .定理9.4中得到2=3=3(-2)。得到证据。#如果将估算的9.5.3 g设置为简单平面图，则为5 .证明：两点分明成立。3点，定理1.1和推理9.5.2有=2 6-12 6，5。#，图论及其应用，16，9.3 Euler公式练习，9.3.1。(a)证明：如果g是长度为k 3的连接平面图，则为k(-2)/(k-2)。(b) (a)使用证明：彼得森地图是非平

11、面的。9.3.2。证明：每个平面可以着色六个顶点。9.3.3 .(a)如果证明G是11的简单平面图，则Gc找到非平面(b)牙齿8的简单平面图，并使Gc也成为平面图。9.3.4。如果G可以用多个平面的并行度表示，则牙齿平面的最小数目称为G的厚度，并以(G)记录。所以(G)=1 G是平面图。(a)证明：(g)/(3-6)；(b)考试：(K) (-1)/6(-2)和练习9.3.3(b)，证明等式对所有8都成立。9.3.5。练习9.2.5。利用结果导出欧拉公式。9.3.6。s设定是平面上n 3点的集合，其中两点之间的距离为1。证明：最多3n 6个点在该距离正好1。图论及其应用，17，9.3欧拉公式练习

12、(继续)，9.3.7。对于平面三角剖分g，全部=3-6；=2-4；*4 .9.3.8。“完全正则”简单图形是每个顶点的角度为D(常数)的平面图形。每个面的角度为df(常数)，证明以下规则成立：=4df (2d df (d 2)在牙齿图中只能有5种茄子。即9.3.9。如果简单平面g没有三角形，则为3；4.图论及其应用、18，9.4 Kuratowski定理、面的两个引理：引理9.10.1 G为非平面视图G的每个剖分图，非平面视图引理9.10.2 G为平面图G的每个子图形为平面图定理9.10 (Kuratowski，1930)G。3的剖分(证明：省略)Wagner定理G将非平面G的可压缩性配置为K

13、5或K3，3的子图形(证明：省略) (简单图G的默认压缩)图G可以压缩为图H。也就是说，G经过一系列基本压缩，可以变成H。)请参见示例。Petersen图是非平面的。因为包含K3，3的剖分。也可以压缩到K5。图论及其应用、19，9.4五色定理和四色猜想、定理9.11(head wood，1890)每个平面都可以着色为5-(顶点)。证明：反证，假设定理不成立。把图G最小化为反例。很明显，G是简单的连接图，是6。选择顶点u以创建d(u)=。推论为9.5.3。我知道，5。正如对G的假设，G-u有正常5-明暗处理(V1，V5)。如果u仅与颜色为4茄子的顶点相邻，则G为5-可着色，矛盾。因此，u必须正好

14、与其他5个颜色顶点相邻。可以顺时针设置v1、V5和每个VI Vi。记住Gij=GVi Vj I j、1 I和j 5。如果I存在，j将确保VI和VJ不在Gij的同一分支中。然后，在Gij中，可以用J替换包含VI的分支中的颜色I，以获得G-u的新5-阴影。其中，U仅与4茄子颜色相邻，因此G是5-可着色的，矛盾的。因此，每个Gij都有一个(VI，VJ)公路Pij，它由颜色I和J顶点交错组成。环形C=uv1P13v3u。因为C区分v2和v4，所以Jordan曲线定理要求P24与C相交一点。但是，G是平面图，它可能是G的顶点。但是，这是不可能的(因为P24只有颜色2和4，C没有牙齿异色)，矛盾。#、图论

15、及其应用、20，9.4五色定理和四色猜想、“四色猜想”的所有(非环)平面均可实现四顶点着色。名为平面g的“k面着色”(k-face colouring) k-颜色分布在g的所有面上(不一定是正常面着色)。平面G可以着色为k面的G具有正常的k面面部数(face chromatic number)，显然所有平面G具有*(G)=(G*)。图论及其应用，21，9.4 5色定理和4色猜想，定理9.12以下的命题是相同的。每个平面都可以进行4-(顶点)着色。每个平面都可以进行四面着色。每个简单、2边连接、3-一般、平面是3边着色的证据：明显。将g设定为简单、双边连接、3-一般或平面。嵌入那个平面。可以着色

16、为四面。触摸2整数字段中的矢量c0=(0，0)、C1=(0，1)、C2=(1，0)、C3=(1，1)表示4茄子颜色。牙齿对的边着色如下：每个边用两个分离面的颜色总和着色。(与顶点V相关的三个面的颜色为ci，CJ，CK。与顶点V相关的三个面的颜色为ci CJ，CJ CK，CK ci。)的每个边缘都是未切割的边缘，因此没有c0颜色的边缘，因此上述边缘描影是13-边缘描影。另外，与每个顶点关联的三条边徐璐以不同的颜色显示。因此，上面的边缘描影是一般3边缘描影。，图论及其应用，22，9.4五色定理和四色猜想：反证，假设不成立的话，有一个简单的平面G (G)=5。嵌入那个平面。在练习问题9.2.6和9.2.7中为简单平面三角剖分h生成的子图形。而H的几何对偶H*是简单、双边连接