高度连通的网络中总是存在循环
2024-06-08
文章主要介绍了数学家证明了一类被称为扩展图的图形一定包含哈密顿循环。哈密顿循环是指在图中访问每个点恰好一次并返回起点的路径。长期以来，数学家一直试图解开保证哈密顿循环存在的条件。2002年，Michael Krivelevich和Benny Sudakov猜想，所有扩展图都包含哈密顿循环。经过20多年的努力，Sudakov与其他数学家终于在2024年2月证明了这一猜想。他们利用了Pósa旋转和排序网络等技术，成功地将一组长路径连接成一个哈密顿循环。这一发现对数学和计算机科学具有重要意义，因为它建立了两个核心概念之间的基本联系，并可能在未来带来重要的应用。