论文部分内容阅读
[摘要] 图是用点和边来描述事物和事物之间的关系,是对实际问题的一种抽象。图论中最基本的思想就是搭建合适的模型,深刻挖掘问题的本质,分析和利用图论模型各种性质,从而到达解决问题的目的。“模型”是图论基本思想的精华,是解决图论问题的关键。在搭建图论模型时,是通过图中的点和边来体现原问题的特点。特殊的数学模型搭建的模型务必要真实的、贴切的和透彻地反映出原问题的本质,同时也要做到力求简练、清晰。
[关键词] 图 数学模型 实际问题
数据结构是算法与程序设计的基石,其中的图是用点和边来描述事物和事物之间的关系,是对实际问题的一种抽象。之所以用图来解决问题,是因为图能够把纷杂的信息变得有序、直观、清晰。因而,图论中最基本的思想就是搭建合适的模型,深刻挖掘问题的本质,分析和利用图论模型各种性质,从而到达解决问题的目的。
在解决一道实际问题时,往往先将实际问题抽象成一个数学模型,然后在模型上寻找合适的解决方法,最后再将解决方法还原到实际问题本身。而图论模型就是一种。在搭建图论模型时,是通过图中的点和边来体现原问题的特点。特殊的数学模型搭建的模型务必要真实的、贴切的和透彻的反映出原问题的本质,同时也要做到力求简练、清晰。图论问题往往关系错综复杂,变化多端,因此,搭建一个合适的模型实非易事。建立模型仿佛是为算法设计搭建一个平台,接下来的工作是在这个平台上充分挖掘和利用原题的性质,设计一个解决问题的好算法。如何挖掘和利用模型的性质呢?下面用一个具体实例来说明。
例:爱丽丝和鲍勃。
爱丽丝和鲍勃在玩一个游戏。爱丽丝画了一个有n(n≤ 10000)个顶点的凸多边形,多边形上的顶点从1到n按任意顺序标号。然后她在多边形中画了几个不相交的对角线(公共点为顶点不算相交)。她把每条边和对角线的端点标号告诉了鲍勃,但没有告诉他哪条是边,哪条是对角线。鲍比必须猜出顶点顺(逆)时针的标号序列,任意一个符合条件的序列即可。
例如,n = 5,给出的边或对角线是(1,4),(4,2),(1,2),(5,1),(2,5),(5,3),(1,3)。那么,一个可能的顶点标号顺序为(1, 3, 5, 2, 4)。对应的多边形如图1:
根据题目意思,不难得到它的图论模型:凸多边形对应了一个有n个顶点的图G,多边形的边和对角线对应着图G中的边。而且十分明显的是,图G是一个平面图,根据欧拉公式,图中边的数量级为O(n)。
研究图G的平面图性质可以发现结论1:一条对角线将凸多边形分成了两部分,每部分都至少含有一个除对角线外顶点,而且这两部分分居在对角线的两侧。由此可知,在图G中只存在惟一的一条哈密顿回路。因为对角线会将多边形分成不相关连的两部分,所以,对角线不可能存于哈密顿回路上。因此,哈密顿回路上的边都是由多边形上的边组成,而多边形的边只有n条,可知哈密顿回路也就只有一条。不妨设这条哈密顿回路为H1,H2,H3……Hn。问题的目标就是要找到这个哈密顿回路。下面讨论如何利用这些性质来设计算法。
我们利用边的连通性。
由结论1可知,如果一条边是对角线,那么,将对角线的两个端点从图G中删除,图G一定会变成两个互不可达的连通分块;而如果一条边是多边形上的边,那么,将这条边的两个端点删除,图G将仍然是连通的。也就是说,能够根据图G中边的连通性,来判断一条边是对角线还是边。因此,得到算法:
1.枚举图中的每条边(u, v),进行如下判断:将u和v两个顶点从图G中删除得到新图G’。在新图G’任选一点a,然后从a开始对图G’进行遍历。如果a能够到达图G’中的其它点,那么,就说明图G’是连通的,(u, v)是多边形的边;否则,图G’不连通,(u, v)是多边形的对角线。
2.将图G中所有对角线删除,得到新图C。这时的新图C便是图G中的哈密顿回路,因此,只要对其进行一次遍历就可以得到多边形顶点的标号序列了。
分析一下算法的复杂度:步骤1中,要枚举的边最多为2n条,每判断一次图的连通性为O(n),所以复杂度为O(n2);步骤2中,删除边和遍历新图的复杂度都为O(n)。所以总的复杂度为O(n2)。
“模型”一词曾在无数论文中被提及,它是图论基本思想的精华,是解决图论问题的关键。建立模型要求我们熟悉经典模型,同时又要求我们能够勇于探索,大胆创新,敢于跳出经典模型的框框。利用模型的特性需要我们独具慧眼,能够抓住问题的本质,击中问题的要害。
同时,文章中还介绍了三种解决问题的方法:定义法、分析法和综合法。这些方法和“模型”一样,具有解决信息学奥赛问题的普适性。它们不仅仅是一种方法,更是一种思维的方式和思考的角度。灵活地运用和掌握它们,有利于我们研究算法、探索科学。
例题的解析过程,体现了图论的基本思想,算法与数据结构的结合是优秀程序设计的必然要求,是知识融会贯通的体现。
[关键词] 图 数学模型 实际问题
数据结构是算法与程序设计的基石,其中的图是用点和边来描述事物和事物之间的关系,是对实际问题的一种抽象。之所以用图来解决问题,是因为图能够把纷杂的信息变得有序、直观、清晰。因而,图论中最基本的思想就是搭建合适的模型,深刻挖掘问题的本质,分析和利用图论模型各种性质,从而到达解决问题的目的。
在解决一道实际问题时,往往先将实际问题抽象成一个数学模型,然后在模型上寻找合适的解决方法,最后再将解决方法还原到实际问题本身。而图论模型就是一种。在搭建图论模型时,是通过图中的点和边来体现原问题的特点。特殊的数学模型搭建的模型务必要真实的、贴切的和透彻的反映出原问题的本质,同时也要做到力求简练、清晰。图论问题往往关系错综复杂,变化多端,因此,搭建一个合适的模型实非易事。建立模型仿佛是为算法设计搭建一个平台,接下来的工作是在这个平台上充分挖掘和利用原题的性质,设计一个解决问题的好算法。如何挖掘和利用模型的性质呢?下面用一个具体实例来说明。
例:爱丽丝和鲍勃。
爱丽丝和鲍勃在玩一个游戏。爱丽丝画了一个有n(n≤ 10000)个顶点的凸多边形,多边形上的顶点从1到n按任意顺序标号。然后她在多边形中画了几个不相交的对角线(公共点为顶点不算相交)。她把每条边和对角线的端点标号告诉了鲍勃,但没有告诉他哪条是边,哪条是对角线。鲍比必须猜出顶点顺(逆)时针的标号序列,任意一个符合条件的序列即可。
例如,n = 5,给出的边或对角线是(1,4),(4,2),(1,2),(5,1),(2,5),(5,3),(1,3)。那么,一个可能的顶点标号顺序为(1, 3, 5, 2, 4)。对应的多边形如图1:
根据题目意思,不难得到它的图论模型:凸多边形对应了一个有n个顶点的图G,多边形的边和对角线对应着图G中的边。而且十分明显的是,图G是一个平面图,根据欧拉公式,图中边的数量级为O(n)。
研究图G的平面图性质可以发现结论1:一条对角线将凸多边形分成了两部分,每部分都至少含有一个除对角线外顶点,而且这两部分分居在对角线的两侧。由此可知,在图G中只存在惟一的一条哈密顿回路。因为对角线会将多边形分成不相关连的两部分,所以,对角线不可能存于哈密顿回路上。因此,哈密顿回路上的边都是由多边形上的边组成,而多边形的边只有n条,可知哈密顿回路也就只有一条。不妨设这条哈密顿回路为H1,H2,H3……Hn。问题的目标就是要找到这个哈密顿回路。下面讨论如何利用这些性质来设计算法。
我们利用边的连通性。
由结论1可知,如果一条边是对角线,那么,将对角线的两个端点从图G中删除,图G一定会变成两个互不可达的连通分块;而如果一条边是多边形上的边,那么,将这条边的两个端点删除,图G将仍然是连通的。也就是说,能够根据图G中边的连通性,来判断一条边是对角线还是边。因此,得到算法:
1.枚举图中的每条边(u, v),进行如下判断:将u和v两个顶点从图G中删除得到新图G’。在新图G’任选一点a,然后从a开始对图G’进行遍历。如果a能够到达图G’中的其它点,那么,就说明图G’是连通的,(u, v)是多边形的边;否则,图G’不连通,(u, v)是多边形的对角线。
2.将图G中所有对角线删除,得到新图C。这时的新图C便是图G中的哈密顿回路,因此,只要对其进行一次遍历就可以得到多边形顶点的标号序列了。
分析一下算法的复杂度:步骤1中,要枚举的边最多为2n条,每判断一次图的连通性为O(n),所以复杂度为O(n2);步骤2中,删除边和遍历新图的复杂度都为O(n)。所以总的复杂度为O(n2)。
“模型”一词曾在无数论文中被提及,它是图论基本思想的精华,是解决图论问题的关键。建立模型要求我们熟悉经典模型,同时又要求我们能够勇于探索,大胆创新,敢于跳出经典模型的框框。利用模型的特性需要我们独具慧眼,能够抓住问题的本质,击中问题的要害。
同时,文章中还介绍了三种解决问题的方法:定义法、分析法和综合法。这些方法和“模型”一样,具有解决信息学奥赛问题的普适性。它们不仅仅是一种方法,更是一种思维的方式和思考的角度。灵活地运用和掌握它们,有利于我们研究算法、探索科学。
例题的解析过程,体现了图论的基本思想,算法与数据结构的结合是优秀程序设计的必然要求,是知识融会贯通的体现。