離散數學中圖論部分教學的研究

李建平

摘 要 在我們學院的信息與計算專業中，數據結構、算法分析以及數據庫原理等課程都要涉及到離散數學中圖論的知識，因此，離散數學中關于圖論部分的教學尤為重要。根據圖論的概念、公式以及定理比較多的特點，為了避免教學的枯燥難懂，本文從以下三個方面進行了探討：結合知識背景、引入數模思想、開展大創項目。

關鍵詞 趣味教學 數模思想 大創項目

中圖分類號：G424 文獻標識碼：A DOI：10.16400/j.cnki.kjdkx.2018.01.061

Research on the teaching of graph theory in Discrete Mathematics

——Based on information and computing major

LI Jianping

（Faculty of Applied Mathematics， Guangdong University of Technology， Guangzhou， Guangdong 510090）

Abstract In the information and computing major of our college， the knowledge of graph theory in Discrete Mathematics is applied in some courses such as data structure， algorithm analysis and database principles etc. So， It is very important for the teaching of graph theory in Discrete Mathematics. According to the characteristics of graph theory and avoiding the dull teaching， this paper discusses from the following three aspects： combining background of graph theory， introducing the thought of mathematics modeling and developing the innovative projects for Students.

Keywords interest teaching； the thought of mathematics modeling； the innovative projects

0 引言

離散數學中的圖論是數學的一個重要分支，是研究自然科學、工程技術、社會科學等問題的一個重要的現代數學工具，在數據結構、算法分析和數據庫原理等課程學習中都占據了很重要的地位。它是通過點和線組成的拓撲圖形，較為方便的模擬自然界和人類社會的各種系統并建立相應的數學模型，根據圖的性質進行分析，提供研究各種系統的理論。圖是數據結構和算法學中最強大的框架之一，所有類型的結構或系統幾乎都可以用圖來表現。圖論知識被廣泛應用到各種領域，如萬維網、社交網絡、交通網絡、通信網絡、圖像處理中的屬性圖、化學分子結構以及生態系統中的食物鏈等都可以用圖來描述他們之間的復雜關系。隨著計算機的發展，圖論得到了迅猛發展，更進一步向各個學科滲透。圖論知識與線性規劃、動態規劃等優化理論和方法相互滲透。圖論中有著豐富的算法如求單源最短路徑的迪杰斯特拉算法，SPFA算法，求負權回路的BELLMAN算法，多源最短路徑的FLOYD算法，拓撲排序算法，最小生成樹的PRIM和KRUSKAL算法等等。圖論算法提供了對很多問題都有效的一種簡單而系統的建模方式，很多問題都可以轉化為圖論問題，然后用圖論的基本算法加以解決；這門課程的學習，不僅可以培養學生的抽象思維能力、邏輯推理能力、創新能力、分析問題和解決問題的能力，也為學生的后續課程打下了堅實的基礎。

1圖論教學方法探討

我們學院信息計算專業要求學生具有良好的數學素養，掌握信息科學和計算科學的基本理論和方法，旨在培養能在信息與計算機領域從事理論和應用研究以及軟件開發設計工作的高素質應用型人才。開設的多門計算機方面的課程，如數據庫原理、數據結構、算法設計與分析等都要涉及到圖論知識，因此離散數學中的圖論部分的教學顯得尤為重要。但是圖論的概念、公式和定理比較多，定理的證明通常相對較難，在一定程度上造成教學枯燥難懂。通過對圖論部分的教學的不斷探索和學生的交流，本文對本部分知識的教學進行了以下的探討。

1.1 引入圖論背景，創設學習情境，實行趣味教學

圖論中概念、定理比較多，初學者不易掌握。在進行圖論課概念的教學時，要善于結合生活實際，把概念具體化，使學生覺得這些抽象的概念就在自己的身邊，伸手即可摸到。例如：在講歐拉圖時，可以先從2007年河南新鄉回龍景區新增景點——“七座橋”的100萬元的現金大獎的問題，引申回到經典的哥尼斯堡七橋問題，以及愛爾蘭數學家哈密頓（Halmiton）提出的“周游世界”的游戲，最后回到大家熟悉的一筆畫問題，從而引出歐拉圖的概念及其應用。在講解匹配章節時，引入教師課表安排問題，快遞員送貨等問題。在講解連通度時，介紹投遞員問題以及網絡的安全性問題；講染色問題時，可提出化學品的貯置問題，考試日程安排以及教室與課程安排問題等。從圖論的背景以及現實生活中的實際問題等有趣味的例子引入到枯燥的概念與定理中，讓學生感到學有所用，主動去思考，主動去尋求答案，從而真正參與到教學活動中，這樣可以充分地調動學生的求知欲和學習樂趣，從而使學生對所學的知識將更加深刻，收獲將更多，因此教學質量與教學效果將得到提升。

1.2 引入數模思想，結合具體事例，撰寫課程論文

數學建模是一種數學的思考方法，是運用數學的語言和方法，通過抽象，簡化建立能近似刻畫并解決實際問題的一種強有力的數學手段。它將一個實際的問題簡化為一個可以用數據和很簡短的語言能表示出來的問題，然后通過數學工具解決這個問題的過程。在實際問題中，物體或人可以用圖的頂點來表示，它們之間的相互聯系可以用頂點之間的連線表示，通過這樣的轉化，一些實際問題就可以變成簡單的圖論問題。因此在圖論的教學過程中，通過一些簡單的模型介紹數學建模的思想及方法，將數學建模的思維和方法融入圖論教學中，通過具體的實例，讓學生建立簡單的數學模型。例如，在介紹最小樹的Prim算法與Kruskal算法時，可以引入實例圖書館的學習資源如何優化配置，農村交通建設，最優布線問題等。在介紹匈牙利算法以及Kuhn-Munkers算法時，可以引入學校的教師課表如何安排，大學生就業問題以及大齡男女婚配問題等實例。在講圖論部分的算法分析時布置大作業，讓學生分組討論，對某一具體實例進行分析，建立簡單的數學模型，找出相應的算法，完成課程論文。通過這些實例的建模與練習，學生進一步掌握了圖論部分的經典算法，初步了解算法和數模思想，增加了學生的動手能力和學習興趣，為后面課程的學習奠定了堅實的基礎。

1.3 開展大創項目，培養創新意識，實施實踐教學

為了提高大學生的創新實踐能力，學校開展了大學生創新創業項目。 適應新時代的發展，將離散數學中的圖論知識與大創項目相結合，開展圖論方面的大學生創新創業項目申請，建立創新團隊，這樣可以培養學生的創新意識，將實踐教學模式應用到圖論部分的教學。課堂上，將傳統教學模式與探討式教學相結合，加強老師與學生之間、學生與學生之間相互探討，對學生的疑惑進行答疑，發揮學生的學習主觀能動性，培養學生分析問題和解決問題的能力。課堂外，主要實施實踐教學，借鑒“翻轉課堂”的教學模式，讓學生通過圖書館、網上資源對新知識自主學習。教會學生查閱相關文獻，帶領學生了解學科發展動態，培養學生的論文查閱意識和能力，并帶領學生撰寫小論文，為課程論文和畢業論文奠定基礎，培養學生的創新意識和科研意識，為部分學生繼續深造奠定研究基礎。在學生大創項目完成過程中，遇到實際問題，鼓勵他們運用圖論知識建立基本的數學模型，編寫相應的程序來解決問題。將大創項目與圖論知識結合，將探討式教學與實踐教學運用到課堂中，既鞏固了圖論的理論知識，加深了對圖論知識的理解，也培養了學生的創新意識，鍛煉了學生的編程能力和實踐能力，為畢業設計和就業做好鋪墊。

2結語

對我們學院信息與計算專業的學生來說，離散數學中的圖論部分是重要而又不易掌握的知識點。隨著計算機與科技的發展，離散數學中的圖論知識越來越重要，越來越多的應用領域。離散數學中圖論部分的學習，不僅可以奠定學生的良好數學素養，更可以提高他們的算法分析與實現能力，為后續的數據結構、算法分析以及數據庫原理等課程打下堅實的基礎。因此，我們需要更加積極探索如何更好地上好離散數學中的圖論部分。

參考文獻

[1] J.A. Bondy， U.S.R. Murty， Graph Theory[M].Springer，2008.

[2] Chartrand G，Oellermann 0 R.Applied and algorithmic graph theory[M].New York：McGraw—Hill，1993.

[3] 屈婉玲，耿素云，張立昂.離散數學[M].高等教育出版社，2008.

[4] 孫玲琍，李治.關于《離散數學》圖論教學的思考[J].計算機科學，2010.37：117-118.

[5] 翟明清.淺析圖論教學[J].大學數學，2011.27：203-206.

[6] 孫培，劉凱，曾俊杰，楊本朝.在圖論課程中融入數學建模思想的教學改革初探[J].大學數學，2015.8：118-119.