地图着色问题的联想

来源：百度知道 编辑：UC知道 时间：2024/06/27 18:07:46
做到地图着色问题，想到每一种地图都可以转化成图的邻接问题，但是不是所有的一种图的邻接表示都有一种地图与之对应呢？？
如果不是，那么满足什么要求的邻接表示才可能有一个地图与之对应呢？？？？

不是，只有平面图才可以
不如ABCDEF六个点，每两个点之间都有边，这样的图不是平面图，因此，它不能与地图对应

要判断一个图是平面图是很麻烦的一件事情，有一些相关结论也非常复杂，这里说不清楚。推荐看一下图论的相关书籍。