離散數(shù)學(xué)中圖論部分教學(xué)的研究

李建平

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

關(guān)鍵詞 趣味教學(xué) 數(shù)模思想 大創(chuàng)項目

中圖分類號：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 引言

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

1圖論教學(xué)方法探討

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

1.1 引入圖論背景，創(chuàng)設(shè)學(xué)習(xí)情境，實行趣味教學(xué)

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

1.2 引入數(shù)模思想，結(jié)合具體事例，撰寫課程論文

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

1.3 開展大創(chuàng)項目，培養(yǎng)創(chuàng)新意識，實施實踐教學(xué)

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

2結(jié)語

對我們學(xué)院信息與計算專業(yè)的學(xué)生來說，離散數(shù)學(xué)中的圖論部分是重要而又不易掌握的知識點。隨著計算機與科技的發(fā)展，離散數(shù)學(xué)中的圖論知識越來越重要，越來越多的應(yīng)用領(lǐng)域。離散數(shù)學(xué)中圖論部分的學(xué)習(xí)，不僅可以奠定學(xué)生的良好數(shù)學(xué)素養(yǎng)，更可以提高他們的算法分析與實現(xiàn)能力，為后續(xù)的數(shù)據(jù)結(jié)構(gòu)、算法分析以及數(shù)據(jù)庫原理等課程打下堅實的基礎(chǔ)。因此，我們需要更加積極探索如何更好地上好離散數(shù)學(xué)中的圖論部分。

參考文獻

[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] 屈婉玲，耿素云，張立昂.離散數(shù)學(xué)[M].高等教育出版社，2008.

[4] 孫玲琍，李治.關(guān)于《離散數(shù)學(xué)》圖論教學(xué)的思考[J].計算機科學(xué)，2010.37：117-118.

[5] 翟明清.淺析圖論教學(xué)[J].大學(xué)數(shù)學(xué)，2011.27：203-206.

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