美國蒙特克萊爾州立大學圖論教學特點研究及啟示

張國珍 王大進

摘? 要：圖論是理工科專業學生開設的一門重要基礎課程。該文研究美國蒙特克萊爾州立大學圖論課程的教學方法，發現其在教學過程中融入大量應用實例，增強學生的學習主動性，完美達到理論聯系實際的教學目標。分析其應用型教學特點，可以在國內圖論課程的教學中，注重引入相關應用及研究理念，激發學生學習興趣，明確圖論課程的實際應用價值，對于圖論課程的教學改革和課程建設具有一定的參考意義。

關鍵詞：圖論；蒙特克萊爾州立大學；教學研究；教學方法；課程建設

中圖分類號：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英里以內，則它們通過邊連接。頻道的分配對應于圖的著色，其中每種顏色表示不同的頻道。

第十章是平面圖。在其應用部分講到，圖的平面性在電子電路設計中起著重要的作用。可以用一個圖來模擬電路，用頂點來表示電路的組成部分，用邊來表示電路之間的連接。如果表示電路的圖形是平面的，可以在沒有交叉連接的單板上打印電路。當這個圖形不是平面圖時，則必須使用更昂貴的設計。例如，可以將表示電路的圖中的頂點劃分為平面子圖，然后用多層構造電路。可以在連接交叉時使用絕緣導線構建電路。在這種情況下，用最少可能的交叉點繪制圖形是很重要的。

二? 圖論教學的一些啟示

在美國蒙特克萊爾州立大學的圖論教學中，類似的應用例子還很多，此處就不再一一列舉了，教學中理論聯系實際隨處可見。研究其教學特點，可以為圖論教學改革提供一些思路。當然，多年來，國內圖論的教學改革也取得了大量的成果，讀者可以參考文獻[2-11]。教學改革的核心是要改變原有的單純的接受式學習方法，建立充分發揮調動學生主動性的學習方式。從多年教學中發現，要想調動學生的學習主動性，不能一味地單純講授知識點，這樣容易導致學生只是被動地接收，加入大量應用實例，對于激發學生的學習主動性至關重要。

國內的圖論教學，基本采用的是邦迪《圖論》[12]的中文翻譯版，但因為該教材涉及到的應用內容較少，所以授課時注重的是理論講解，應用部分涉及不多。例如在介紹了圖的概念之后，大多不會講解其應用。這樣的講授過程，使得學生不能體會到圖在現實生活中的重要性，從而對概念的掌握也就沒有那么深刻。而蒙特克萊爾州立大學在講授完圖的概念后，以大量的社會網絡應用為例，體現了圖的實際重要性。我們可以借鑒國外的教學方法，加入應用的部分，激發學生對圖論的興趣，使其在課程初始就能體會到圖論的應用價值。

在圖的常見類型部分，國內講授完圖類后，一般很少介紹其應用部分。受美國蒙特克萊爾州立大學這種應用型教學的啟發，我們可以把圖類和研究課題結合起來，讓學生初步形成一些研究型的理念。作者本人是研究互連網絡容錯性的，超立方是最常用的互連網絡拓撲之一，且超立方就是一個偶圖，符合此處介紹的圖類。我們可以引入超立方的相關知識，同時介紹其在并行計算互連網絡中的應用。并行處理是使用由許多獨立的處理器組成的計算機，每個處理器擁有自己的內存，有助于克服單處理器計算機的局限性。當使用并行處理時，這些處理器需要相互連接。我們可以用適當的圖形表示多處理器計算機中處理器的互連網絡。超立方是并行處理器最常用的互連網絡之一，對于這樣一個網絡，處理器的數量是2m，每個處理器都有到其他m個處理器的雙向連接。許多計算機是用超立方網絡構建的，許多并行算法是用超立方網絡設計的。通過應用的講解，激發學生對超立方的研究興趣，并就一些簡單的研究問題讓學生開展相應的工作。

在圖的連通性部分，國內教材大多數只是涉及到連通度、邊連通度的概念及其在理論上的一些結論。對連通性應用部分講解甚少。但實際上，連通性在互連網絡的可靠性及容錯性的度量中有非常重要的應用。結合美國蒙特克萊爾州立大學這種應用型教學的模式，我們可以結合網絡的性能，在此章節補充連通性的各種概念的發展與應用。多處理器系統的互連網絡拓撲可以用圖來表示。此時，圖的頂點表示系統中的元件，圖的邊表示元件之間的物理連線。為系統設計或選擇網絡拓撲時，基本的考慮是系統的可靠性與容錯性。連通度和邊連通度是度量網絡的可靠性與容錯性的兩個經典參數。作為傳統連通性的推廣，學者們相繼提出了條件連通性、超連通性、好鄰連通性、廣義連通性和結構連通性等概念。這些連通性參數可以更加精確及更加符合實際地度量網絡的可靠性與容錯性。通過補充這些內容，可以讓學生深刻了解連通度的發展過程，各個連通性參數之間的聯系與區別，以及在度量網絡可靠性與容錯性時不同的應用背景。同時可以尋找一些知名的流行網絡，在這些網絡上指導學生計算所講到的各類連通性參數。通過這樣的教學及練習，使學生能夠熟練掌握連通性的各種概念，并對其應用產生濃厚的興趣，也可以為學生將來從事相關的科學研究打下良好的基礎。

通過研究美國蒙特克萊爾州立大學圖論教學的過程，在今后的教學中，我們可以借鑒其注重應用講解的特點，在各個知識點的學習中選取恰當的應用實例來佐證圖論的實用價值，從而激發學生的學習興趣，提高其學習主動性，理論聯系實際，更好地掌握圖論課程的精髓。

參考文獻：

[1] ROSEN K H. Discrete Mathematics and Its Applications[M]. New York：McGraw-Hill， 2019.

[2] 王樹禾.圖論[M].北京：科學出版社，2009.

[3] 徐俊明.《圖論及其應用》課程建設探索[J].教育與現代化，1997（2）：41-46.

[4] 王寶麗，胡運紅，張鳳琴.人工智能技術融入散數學課程的教學探索[J].高等理科教育，2019（5）：70-75.

[5] 史永堂，雷輝，李佳傲.數學基礎課程圖論的課程思政探索與實踐[J].大學數學，2021，37（4）：34-41.

[6] 鄧凱，朱立軍.圖論及其應用課程混合式教學改革探索[J].大學教育，2021（4）：21-24.

[7] 孫艷蕊.圖論教學中學生創新思維培養的探索與實踐[J].高師理科學刊，2018，38（8）：82-85.

[8] 廖云華，劉建剛，謝小良.圖的鄰接矩陣的教學設計[J].現代商貿工業，2021，42（6）：145-146.

[9] 丁學利.圖論教學中求最小生成樹的方法研究[J].阜陽職業技術學院學報，2020，31（4）：39-42.

[10] 孫曉玲，杜建偉.關于圖論課堂教學的探討與研究[J].教育教學論壇，2020（31）：301-302.

[11] 劉春妍，方海，文趙宇.《圖論》課程思政教育教學設計探索與實踐[J].黑河學院學報，2022，13（3）：110-112.

[12] BONDY J A， MURTY U S R. Graph theory[M].New York：Springer，2008.