摘要欧拉定理告诉我们,哥尼斯堡七桥问题无解,4个节点的度数都是奇数,自然也就做不到一笔画,即不能返回原地,甚至也不可能从一个节点出发经每条边恰好一次,到另一个节点结束。在其他情形下,如果按照欧拉定理判断结果为“能”,具体怎么做呢?这就是我们要讨论的算法问题了。作者李晓明,北京大学计算机系原系主任
摘要“走迷宫”要求在一个复杂“道路”系统中根据指定起点与终点寻找可行路径。迷宫的形式非常多,本文只讨论二维矩形迷宫。作者陈道蓄,南京大学软件学院原院长,计算机系原主任。
摘要这一期,我们从图的计算机表示出发,以判断一个图是否连通为目标展开讨论,旨在通过这样一条简单的线索,让读者从数学和计算机处理两个方面,对图的含义形成比较深入的认识,尤其是体会数学概念和计算机处理之间的互动。作者李晓明,北京大学计算机系原系主任
摘要本文研究如何把一些节点连通起来的代价最小。可以想象这些节点是一些城市,它们之间的直飞航线是边,代价则是在它们之间开辟直航的成本。作者李晓明,北京大学计算机系原系主任