一笔画与跳跃点(图论)
一笔画的问题相信大家都很熟悉,普通的图想一笔画成也很简单,只要用七桥问题的结论(推论)就可以轻松解决。
⒈凡是由偶点组成的连通图,一定可以一笔画成。画时可以把任一偶点为起点,最后一定能以这个点为终点画完此图。
⒉凡是只有两个奇点的连通图(其余都为偶点),一定可以一笔画成。画时必须把一个奇点为起点,另一个奇点终点。
但如果我在图中加入两个跳跃点(即走到一个点时会自动跳到另外一个点上),这两个的结论好像就不适用了,这时候,有什么方法能方便地找出一笔画的路线吗?
[解决办法]
无非就是多了一条线嘛。
如果有2N个奇点,连通任意两个奇点就是了。
每连通一次减少两个奇点。