求解建路图

idiot94

图论中有如下基本结论： （定义：平面图是指一个可以在平面上“实现”的图，也就是说：所有的顶点和边都在同一个平面上，而且任何两条边除了在顶点处，互不相交。不能在平面上实现的图就叫做非平面图。）   任何一个非平面图，都存在一个子图（就是从整个图中切下来个某个部分），要么和三阶完全偶图同构，要么和五阶完全图同构。   楼主的题目其实就是要证明三阶完全偶图不能在平面上实现。   一般图论中标准的证明都是通过那个著名的欧拉定理来证的，我们在中学立体几何里面学习过这个定理：三维空间中的简单多面体，如果记其面数为S, 边数为E, 顶点数为V, 那么 S+V-E=2. 当时这个定理的证明就是把多面体展平成为一个平面图来做的，简单而有趣 （大家不妨试着回忆一下。。）。 如果使用这个定理，在结合您的思路，就很容易写出一个简单明了的证明了。 ：）   哦，另外，图论中还有一个定理，就是说，任何一个图，都可以在三维空间中实现。     www.ddhw.com