《图论平面图与对偶图.ppt》由会员分享，可在线阅读，更多相关《图论平面图与对偶图.ppt（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章 平面图与对偶图4.1 平面图4.2 平面图上的欧拉公式4.3 对偶图4.1 平面图平面上的图(plane graph)：指的是画在平面上的一个图形，它的所有的边都不相交（除顶点外）。平面图(planar graph)：如果一个图经过重画之后，可以画成平面上的一个边不相交的图形，则该图便称为平面图（可嵌入平面(embeding)）。Jordan curve：自身不相交的连续曲线。Jordan closed curve：Jordan curve 两个端点重合。Jordan curve theorem：C 为在平面上的Jordan closed curve，平面的其余部分被分成不相交的开集，
2、分别称为C 的外部和内部，则连接内部和外部点的任何连续曲线必与C 相交。Th4.1：k5和k3.3不是平面图。同胚(homeomorphism):1）如果两个图能够从一个图G 出发，通过在G 的边上插入有限多个2次顶点得到，则称这两个图是同胚。2）如果两个图是同构的或通过反复插入或消去2次顶点后是同构的，则称这两个图是同胚。Th4.2：一个图为平面图当且仅当它不含与k5或k3.3同胚的子图。Th4.3：一个图为平面图当且仅当它不含可以缩成k5或k3.3的子图。交叉数：为G 画在平面上时，它的边出现相交的最少可能的数目。记为：Cr(G)。4.2 平面图上的欧拉公式平面上的一个点x不与相交的点：x
3、既不是的顶点也不是的任何一条边上的点。的包含的面：为平面上所有可以从出发通过一条不与相交的Jordan 曲线而能达到的点的集合。无穷面可嵌入曲面：如果一个图能够画在一张曲面上，使得它的边除了顶点外再无其它交点。Th:一个图是可嵌入平面 它是可嵌入球面。Th4.4：设是一个连通的平面上的图，n，m 和f 分别表示图的顶点数，边数和面数，则n-m+f=2。Cor.5：设为具有n个顶点，m 条边，f 个面和k个分图的平面上的图，则n-m+f=k+1。Cor.：为简单连通平面图|V|=n（n2）和|E|=m）m3n-6；）如果G 中不含三角形，则m 2n-4。Cor.7：k5和k3.3不是平面图。Th4.8：每个简单平面图均包含一个次数最多为5的顶点。下面内容见书：一个图的厚度：Th4.9