在这篇文章中,我们介绍两个方面内容:
在一个 平面 画出一个图,如果图的每条边都 互不相交 ,则称这个图为平面图
在 完全图 的文章中,介绍了K 4 ,这里我们以此为例
本来以为K 4 不会是平面图,会有两条边相交,但是我们做个变形,将一条边画出去,就将K 4 画成了平面图
在K 4 内,图被分为4个 面 ( face of region ):A, B, C, D
K 4 内共有:
为了判断一个图是否为平面图,我们使用
在一个图中,有一个度为2的结点和两条边(v, v 1 )和(v, v 2 ),而且v 1 ≠ v 2 ,则称(v, v 1 )和(v, v 2 )是串联的
串联约减就是将结点v从图中删去,用(v 1 ,v 2 )代替(v, v 1 )和(v, v 2 )
上图就采用串联约减删去结点e,边(a, e)和(e, c)被替换为(a, c)
如果图G 1 可以通过串联约减(一步或多步)变为与G 2 同构的图,则称G 1 和G 2 是同胚的,反之也是
一个图G是平面图当且仅当G中不包含与K 5 或者K 3,3 同胚的子图
可用库拉托夫斯基定理判断图G是不是平面图,举个书本中的例子
移除图中的边(a, b),(e, f),(g, h),经过串联约减之后,就将图变为了K 3,3 ,所以不是平面图
给出一个 平面图 ,给图的每个面涂上颜色,使得每两个相邻的面的颜色不同,一共需要多少种颜色?
这张图用了四种颜色涂了五个面
用一个复杂一点的图试试
关于平面图的介绍就到这里了,谢谢大家!