首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

一笔划与跳跃点(图论)

2012-12-30 
一笔画与跳跃点(图论)一笔画的问题相信大家都很熟悉,普通的图想一笔画成也很简单,只要用七桥问题的结论(推

一笔画与跳跃点(图论)
一笔画的问题相信大家都很熟悉,普通的图想一笔画成也很简单,只要用七桥问题的结论(推论)就可以轻松解决。
⒈凡是由偶点组成的连通图,一定可以一笔画成。画时可以把任一偶点为起点,最后一定能以这个点为终点画完此图。
⒉凡是只有两个奇点的连通图(其余都为偶点),一定可以一笔画成。画时必须把一个奇点为起点,另一个奇点终点。

但如果我在图中加入两个跳跃点(即走到一个点时会自动跳到另外一个点上),这两个的结论好像就不适用了,这时候,有什么方法能方便地找出一笔画的路线吗?
[解决办法]
无非就是多了一条线嘛。
如果有2N个奇点,连通任意两个奇点就是了。
每连通一次减少两个奇点。

热点排行