【离散数学】图论(八)平面图以及涂色问题

如题所述

第1个回答  2022-06-10

在这篇文章中,我们介绍两个方面内容:

在一个 平面 画出一个图,如果图的每条边都 互不相交 ,则称这个图为平面图

在 完全图 的文章中,介绍了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 ,所以不是平面图

给出一个 平面图 ,给图的每个面涂上颜色,使得每两个相邻的面的颜色不同,一共需要多少种颜色?

这张图用了四种颜色涂了五个面

用一个复杂一点的图试试

关于平面图的介绍就到这里了,谢谢大家!