补充资料：平面图

平面图
planar graph

平面表示的面的数目均一样。这可以用著名的欧拉公式进行计算;若n阶平面图G有m条边和k个分支，则G的一个平面表示的面数f=m一n+k+1。在无向图G的任一条边。上插人一个度为2的顶点，将。一分为二，或者从G中删去一个度为2的顶点v，将与v关联的两条边合二为一，可得到图G，，此时称G与G，同胚。波兰数学家Kuratowski给出了判断一个图是否为平面图的准则，即著名的库拉托夫斯基定理:无向图G是平面图当且仅当G没有同胚于图1或图2的子图(参见图论)。 给定平面图G的一个平面表示，在其每个面内找一顶点，若两个面有m条公共边，则用m条线连接这两个面内取定的顶点，并使其分别与m条公共边相交。由这些顶点和连线组成了边不在非顶点处相交的图形。称以该图形为其平面表示的平面图为G的对偶图。(张强)P ingm一antu平面图(Planarg，ph)能够在平面上画出，且边不在非顶点处相交的无向图。在平面上画出的边不在非顶点处相交的平面图G的图形称为G的平面表示。在平面图G的一个平面表示中，以G的边为边界的连通区域称为G的该平面表示的面。一个平面图可以有多个不同的平面表示，但其任何

说明：补充资料仅用于学习参考，请勿用于其它任何用途。