问题描述:
给一个图， 能否“一笔画成”（不可中断与重复）？
比如给一个正方形， 可以从其中一个顶点出发， 沿着周长转一圈， 再回到这个顶点， 就可以实现“一笔画”。
这个问题是七桥问题的衍生问题,
由欧拉发现并解决.
为了给出解决"一笔画"问题的一般规律, 先要明白以下概念:
- 连通图: 在一个图中, 从顶点i到顶点j有至少一条路径相连, 则此图为连通图.
- 奇点: 在一个图中, 经过一个顶点i的线有奇数个, 则此点为奇点.
- 偶点: 在一个图中, 经过一个顶点i的线有偶数个, 则此点为偶点.
那么一个图能否"一笔画成"? 如果此图有如下特征, 就可以, 否则不行:
- 此图为连通图
- 此图中奇点个数为0(即全为偶点)或2
- 画法:
- 若全为偶点, 从图中任意一点出发都可以"一笔画".
- 若奇点个数为2, 从其中一个奇点出发, 到另一个奇点结束.
有了上面的结论, 来解决如下问题:
能否一笔画 “田” 字状图形?
分析: 田字中心的点和4个角对应的点为偶点, 其它点都为奇点, 奇点个数为4, 所以不能"一笔画".
参考:
- https://baike.baidu.com/item/七桥问题/2580504
欢迎补充指正!
