涂鸦定理及其他
2024-11-11
本文从一个简单的儿童游戏——一笔画问题出发，引出了图论中的欧拉路径问题。文章首先介绍了柯尼斯堡七桥问题和欧拉的解决方案，即一个图形可以一笔画完成的充要条件是所有节点的度数为偶数（最多有两个节点度数为奇数）。之后，文章探讨了平面图上一笔画且不交叉线的条件，并进一步引申到平面图的二着色问题，即任何平面图的区域都可以用两种颜色染色，相邻区域颜色不同。最后，文章将平面图的二着色问题转化为图的顶点着色问题，并引出了哈密顿回路和图的三着色问题，最终将这些问题与著名的P/NP问题联系起来。