有向图的增强——一个适合以问题求解为导向教学的例子

作者：李晓明

来源：计算机教育, 2019, (02): 1-4.

DOI：10.16512/j.cnki.jsjjy.2019.02.002

• 有向图
• 强连通图
• DAG
• 强连通分量
• 完全二部图
• 问题求解

<正>过去几年,在北大有一门通选课,叫"社会科学中的计算思维方法"。每次上课的时候,我总会给出一个小小的有向图的例子,让同学们观察,看最少添加几条边,可以让那个图变成强连通的,这个看起来像是一个趣味数学游戏的活动常常会引起学生们的积极参与。由于例子很小,大家通常在两三分钟里就能给出正确的结果。然后,我就留下这个游戏推广到一般的问题让有兴趣的同学思考。