可平面图
可平面图
条目
可平面图(planar graph)是一类特殊的图，指同构于某一平面图的图。如果一个图能够画在平面上，使得顶点集合及边集合分别是相同的，而如果边相交仅在边的端点处，则称这个图是可嵌人平面的，或称作可平面图(planar graph)；否则称作不可平面图，可平面图G的这样一种画法称为G 的一个平面嵌入(planar embedding) 。库拉托夫斯基定理给出了可平面图的特征，其内容为：图G是可平面图当且仅当G没有同胚于完全图K5和完全二部图K3,3的子图，同胚于K5和K3,3的图称为库拉托夫斯基图。这一定理是由库拉托夫斯基(Kuratowski，K.)于1930年证明的，若可平面图G不是任何同阶其他可平面图的 子图，则称G为极大可平面图，极大可平面图所对应的平面图的每个面都必为三角形；同构于外平面图的图称为外可平面图；3正则的可平面图称为3正则平面图；G是外可平面的当且仅当G没有与完全图K4同胚的子图。
基本定义
如果一个图能够画在平面上，使得顶点集合及边集合分别是相同的，而如果边相交仅在边的端点处，则称这个图是 可嵌人平面的，或称作 可平面图(planar graph)；否则称作 不可平面图，可平面图G的这样一种画法称为
的一个 平面嵌入(planar embedding)。
如果一个可平面图重新画在平面上，使得没有两条边相交，除非在顶点处，则称这个图是 平面图(plane graph) 。