离散数学_第8章 图__平面图

一 平面图定义： 

图G是 无向图， 把图G画在平面上， 如果是 除顶点外任意两条边都不相交， 称G为平面图。

 

看题目

判断下列各图是否为平面图

 

上述图中，都是平面图。

哪些图不是平面图呢？？

完全图K₅，  K₃,₃ 都不是平面图。   注意这里是K₃,₃ 不是K₃  ！

原因：  K5, K₃,₃ 这两个图不管怎样把中间交叉的线，往外扯， 始终存在交叉！！！

所以就不是平面图。

 

二.  平面图的结论 

2.1   平面图所有面的次数和 = 边数的2倍。

2.2  欧拉公式:  G为任意连通平面图， 则 n - m + r = 2.    其中n： 顶点数， m: 边数，  r:面数。

     公式的推广：G为任意平面图， 有K个连通分支（K>=2）， n - m +r = K+1

 

三  平面图的对偶图