图的厚度与厚度问题
**图的厚度与厚度问题**
图的厚度是图论中衡量图“非平面性”的重要参数,它源于一个非常自然的想法:如果一个图不是平面图(即不能画在平面上使得边仅在顶点处相交),那么最少需要多少个平面图叠加以使得原图的每条边都出现在至少一个平面子图中?这个最少的平面子图的数量,就称为图的厚度,通常记为 θ(G)。
我们来一步步拆解这个概念。
**第一步:从平面图到非平面图**
1. **平面图回顾**:首先,我们明确什么是平面图。如果一个图G可以画在平面上,并且其任意两条边除了在公共顶点处外都不相交,
2025-11-01 18:33:39
0