连通还是不连通

• 作者: 李晓明
• 来源期刊: 中小学教材教学
• 年，卷（期）: 2019,（9）
• 所属期刊栏目: 算法园地
• 页码范围: 75-80
• 页数: 6页
• 语种: 中文

摘要

第七期我们讨论了求欧拉回路的弗罗莱算法,其中初次涉及了若干图论中的术语(概念).由于图论中的图是现实中许多事物(例如网络)的一种自然的模型,以图为对象所形成的算法成为计算机算法百花园中一个极其重要的组成部分.这不仅因为它们足够丰富,还因为它们引人入胜.在"算法园地"的计划中,有相当比例的内容与图有关,其中,连通在许多场合都是一个中心概念.例如,在弗罗莱算法中,我们要求删去的边不能是桥(除了一种特殊情况外),本质上就是要避免不连通.