历些毛子种枝大皇 XIDIAN UNIVERSITY 例子3：3间房子和3种设施问题 问题：要求把3种公用设施（煤气，水和电）分别用煤气管道、水管和电线连 接到3间房子里，要求任何一根线或管道不与另外的线或管道相交，能否办到？ 上面问题可以模型为如下图： H1 H2 H3 问题转化为，能否把上图画在平面上，使得边与边之间不会交叉？
问题：要求把3种公用设施(煤气，水和电)分别用煤气管道、水管和电线连 接到3间房子里，要求任何一根线或管道不与另外的线或管道相交，能否办到？ 例子3：3间房子和3种设施问题 上面问题可以模型为如下图： H1 H2 H3 G W E 问题转化为，能否把上图画在平面上，使得边与边之间不会交叉？
历安毛子代枚大学 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的平面嵌入