历安毛子代枚大学 XIDIAN UNIVERSITY 上面的例子都涉及同一个图论问题：能否把一个图画在平面上，使得边与 边之间没有交叉？ 针对这一问题，我们引入如下概念 定义1如果能把图G画在平面上，使得除顶点外，边与边之间没有交叉，称G 可以嵌入平面，或称G是可平面图。可平面图G的边不交叉的一种画法，称为G 的一种平面嵌入，G的平面嵌入表示的图称为平面图。 G H2 H3 H3 H1 H2 图G 图G的平面嵌入 上面的例子都涉及同一个图论问题：能否把一个图画在平面上，使得边与 边之间没有交叉？ 针对这一问题，我们引入如下概念 定义1 如果能把图G画在平面上，使得除顶点外，边与边之间没有交叉，称G 可以嵌入平面，或称G是可平面图。可平面图G的边不交叉的一种画法，称为G 的一种平面嵌入，G的平面嵌入表示的图称为平面图。 H1 H2 H3 G W E 图G H3 H1 H2 G W E 图G的平面嵌入