美国蒙特克莱尔州立大学图论教学特点研究及启示

摘  要：图论是理工科专业学生开设的一门重要基础课程。该文研究美国蒙特克莱尔州立大学图论课程的教学方法，发现其在教学过程中融入大量应用实例，增强学生的学习主动性，完美达到理论联系实际的教学目标。分析其应用型教学特点，可以在国内图论课程的教学中，注重引入相关应用及研究理念，激发学生学习兴趣，明确图论课程的实际应用价值，对于图论课程的教学改革和课程建设具有一定的参考意义。

关键词：图论；蒙特克莱尔州立大学；教学研究；教学方法；课程建设

中图分类号：G649        文献标志码：A          文章编号：2096-000X（2024）03-0121-04

Abstract： Graph Theory is an important basic course for students majoring in science and engineering. This paper studies the teaching methods of Graph Theory in Montclair State University， and finds that a large number of application examples are integrated into the teaching process to enhance students' learning initiative and perfectly achieve the teaching goal of integrating theory with practice. Analyzing the application-oriented teaching characteristics， we can introduce relevant applications and research ideas into the domestic teaching of Graph Theory， so as to stimulate students' interest in learning and clarify the practical application value of Graph Theory， which has a certain reference significance for the teaching reform and curriculum construction of Graph Theory.

Keywords： Graph Theory; Montclair State University; teaching research; teaching methods; curriculum construction

图论是数学的一个分支，以图为研究对象。图论中的图是由一个点集以及这个点集中的某些点对的连线构成的图形，这种图形通常用于描述一些事物之间的特定关系，其中用点表示事物，用连接两点的线表示对应的两个事物之间有这样的关系。

图论起源于哥尼斯堡七桥这个经典的问题。18世纪，在哥尼斯堡的普莱格尔河上建有七座桥，连接河中间的两个岛和河岸。人们闲暇时经常在这上面散步，于是有人提出：能不能每座桥通过且只通过一次，最后回到原来的位置。这个简单而有趣的问题受到人们的关注，很多人尝试了各种走法，但并没有做到。后来，瑞士数学家欧拉解决了哥尼斯堡七桥问题，由此成为图论的创始人。

在图论的发展历史中，有一个著名的问题是四色猜想：一个平面或球面上的地图只需四种颜色就可以着色，使得两个相邻的国家着不同的颜色。这个问题于1852年提出，但是百余年后四色问题还没有解决。1976年，阿佩尔和哈肯给出了一个借助计算机的证明，按照某些性质，该方法将所有的地图分为1 936类，利用计算机运行了1 200个小时，验证了可以用四种颜色着色。因为采用的方法不能人工直接验证，这个证明不能被所有数学家接受。四色猜想推动了图的着色理论、平面图理论、代数拓扑图论等分支的发展。

图论在物理、化学、计算机科学、运筹学、信息论、社会科学和经济管理等众多领域都有非常广泛的应用。图论的研究也促进了拟阵理论、超图理论、极图理论、代数图论和拓扑图论等快速的发展。

一  蒙特克莱尔州立大学图论教学

蒙特克莱尔州立大学位于美国新泽西州，是一所公立研究型大学，蒙特克莱尔州立大学始建于1908年，是新泽西州第二大的学校，而且是该州成长最快的大学之一。作为美国USNEWS TOP 100公立大学之一的本科、研究生教育学府和学术研究机构，蒙特克莱尔州立大学的应用数学、计算机等多门学科在全美享有较高的知名度，在图论方向的研究国际知名，学校汇集和培养了一批图论及其应用领域的专家学者。作者曾于2019年在蒙特克莱尔州立大学访学交流，全程参与了该校图论课程的教学并有一些自己的感悟。本文研究蒙特克莱尔州立大学图论课程的教学特点，希望可以对国内图论课程的教学改革和课程建设提供一点启示和值得借鉴的地方。

蒙特克莱尔州立大学的图论教学，采用的教材是Rosen的《Discrete Mathematics and Its Applications》[1]中关于图论部分的内容，该教材十分经典，知识点完备，应用实例非常丰富。教学过程以课堂讲授为主，课件为辅，教学讲义可以从授课教师的个人主页上下载。授课过程中注重启发学生的自主性，循序渐进地学习，为加深学生对理论的深刻掌握，采用大量应用实例激发学生的求知欲，并穿插一些研究型理念，引导启发学生进一步独立思考。课后作业限期提交，完成提交后可以在授课教师的主页上查看相应的习题解答。要求学生在课前预习，课上按照自己的理解做好笔记，课后完成相应练习。任课教师每周都会约定答疑时间，学生可以在此时间段与教师交流学习中的一些问题。参与蒙特克莱尔州立大学图论的整个教学过程，发现其最重要的特点是注重理论联系实际，知识点结合应用，使学生既能扎实掌握理论，也能将理论应用到实践或研究中去。下面逐章简单介绍蒙特克莱尔州立大学图论课程的内容，重点介绍其应用实例，从而说明其授课过程注重理论联系应用的特点。

第一章介绍了图和有向图的相关定义，讲授了现实生活中图的各种重要应用。例如社会网络，图被广泛地用于模拟基于不同的人与人或群体之间各种关系的社会结构。这些社会结构及表示它们的图被称为社会网络。在这些图模型中，个体或组织由顶点表示；个体或组织之间的关系由边表示。社会网络的研究是一个非常活跃的多学科领域，人们已经用其研究了许多不同类型的人与人之间的关系。常见的社会网络有相识和友谊图，影响图、合作图、电话呼叫图、引用图、模块依赖关系图，优先图与并行处理、航线图、道路网、生态学中的生态位重叠图和蛋白质相互作用图等。这些都是图在实际生活中的一些应用。

第二章介绍了图论中的一些特殊类型的图类，如完全图、圈、轮、超立方、偶图和完全偶图等，随之介绍了这些图类在局域网中的应用。例如，一个办公场所中的各种计算机，如小型计算机和个人计算机，以及外围设备，如打印机和绘图仪，可以使用局域网连接。其中一些局域网络是基于星形拓扑结构的，即所有设备都连接到一个中央控制设备。这样的局域网可以用一个完全二部图来表示，消息通过中央控制设备从一个设备发送到另一个设备。有一些局域网是基于环形拓扑结构的，即每个设备正好连接到另外两个设备。具有环形拓扑的局域网使用圈来建立，消息在一个圈内从一个设备发送到另一个设备，直至到达消息的预期接收者为止。一些局域网使用上述两种拓扑的混合。消息可以围绕环发送，也可以通过中央设备发送。这种结构使网络更加可靠，具有这种结构的局域网可以用轮来建立。

第三章是图的表示及图同构。图同构出现在化学、电子电路设计以及生物信息学和计算机视觉等领域的应用中。化学家使用多重图，即分子图来模拟化合物。在这些图中，顶点代表原子，边代表这些原子之间的化学键。两种结构异构体，分子式相同但原子键合不同，具有非同构的分子图。当合成一种可能的新化合物时，要检查分子图数据库，看该化合物的分子图是否与已知的分子图相同。电子电路是用图形建模的，其中顶点表示元件，边表示元件之间的连接。现代集成电路，称为芯片，是小型化的电子电路，通常有数百万个晶体管及其之间的连接。由于现代芯片的复杂性，人们使用自动化工具设计。图形同构是验证由自动化工具生成的电路的特定布局是否与设计的原始示意图相对应的基础。图形同构也可以用来确定一个供应商的芯片是否包含来自不同供应商的知识产权。这可以通过在为这些芯片建模的图中寻找大型同构子图来实现。

第四章是树。介绍了树的定义及相关性质，然后讨论了几个可以用树研究的问题。搜索列表中的项目是计算机科学中最重要的任务之一。主要目标是实现一个搜索算法，在项目完全有序的情况下有效地找到项目。这可以通过使用二叉搜索树来实现，二叉搜索树是一个二叉树，其中顶点的每个子节点都被指定为右或左子节点，没有任何顶点有多个右子节点或左子节点。此外，还介绍了树的其他应用，诸如决策树、前缀码、游戏树等。

第五章是关于连通性的。在介绍了路的概念以后，在其应用部分，先介绍了相识图中的路径，在相识图中，两个人之间有一条路，即一条链，其中相邻的两个人互相认识。许多社会科学家推测，世界上几乎每一对人都是由一小串人联系在一起的，也许只有5个人或更少。这意味着在包含世界上所有人的熟人关系图中，几乎每一对顶点都通过一条长度不超过6的路径相连。约翰·瓜尔的话剧《六度分离》就是基于这个概念。在连通性的应用部分，介绍了电话呼叫图的连通分支。当存在从x开始到y结束的一系列电话呼叫时，两个顶点x和y位于电话呼叫图的同一分支中。分析AT&T网络中某一天的电话呼叫调用图，发现该图有53 767 087个顶点、超过1.7亿条边和超过370万个连接组件。这些分支大多很小，大约四分之三由两个顶点组成，这两个顶点表示一对只互相呼叫的电话号码。这个图有一个巨大的连通分支，有44 989 297个顶点，占总数的80%以上。

第六章是最短路问题，该问题本身就是一个实际应用问题。给出一个连接若干个城市的铁路网，在这个网络的两个指定城市间，找一条最短铁路线。以各城市为图的顶点，把两个城市之间的直达铁路作为图中对应的两个顶点之间的边构造图。对图的每一条边赋以一个实数表示直通铁路的长度，称为该边的权，得到一个赋权图。最短路问题就是在赋权图指定的两个顶点之间，寻找具有最小权的路，使用Dijkstra算法可以求解这一问题。同时，也介绍了最短路问题在其他问题中的应用，例如，可将其用在中国邮递员问题的求解中。

第七章是欧拉图和哈密尔顿图。欧拉图的应用是中国邮递员问题：一名邮递员从邮局出发，经过他所负责投递的街区内每条街道至少一次，最后返回邮局，如何为他设计最短的投递路线。如果能在图中找到一条欧拉环游，那么该环游正好经过每条街道一次。如果不存在欧拉环游，则某些街道必将经过多次。这个问题是中国管梅谷教授最先提出的，在国际上被称为中国邮递员问题。哈密尔顿路径和回路可以用来解决实际问题。许多应用程序要找一条路径或线路，可以访问城市中的每个道路交叉口、每个地方仅一次。发现图模型中的哈密尔顿路径或回路可以解决这类问题。例如著名的旅行推销员问题：一名推销员从驻地出发，计划去若干城市推销商品，要求经过每个城市恰好一次，最后返回驻地。如何为他设计最短的旅行路线？该问题归结为在赋权完全图中寻找总权重尽可能小的哈密尔顿回路。

第八章是对集。在其应用部分，介绍了人员分派问题。某公司准备分派n个工人去做n件工作，已知这些工人中的每个人都适合做一件或几件工作，问是否能分派所有的工人做一件他适合的工作？使用匈牙利方法可解决人员分派问题。此外，还可以考虑工人对各种工作的效率，目的是使工人的总效率达到最大，该问题称为最优分派问题，使用Kuhn-Munkres算法可以解决这一问题。

第九章是图的着色问题。图着色在涉及调度和分配的问题上有多种应用。例如安排期末考试，如何安排大学期末考试，以便没有学生同时参加两门考试？这个排考问题可以用一个图模型来解决，顶点代表课程，如果课程中有一个共同的学生，则在两个顶点之间连一条边。期末考试的每个时间段都用不同的颜色表示。考试时间表对应于相关图的着色。再例如频率分配，电视频道2到13被分配给北美的电视台，以便150英里（约等于241.40 km）内没有两个电视台可以在同一频道上运行。信道分配如何用图着色来建模？通过给每个站指定一个顶点来构造一个图。如果两个顶点位于彼此150英里以内，则它们通过边连接。频道的分配对应于图的着色，其中每种颜色表示不同的频道。