數學建模思想融入圖論課程教學的研究與實踐

摘要：結合圖論課程的教學實踐，介紹如何將數學建模思想方法融入到圖論課程教學中，從而激發學生的學習興趣，培養學生的創新能力和應該意識，提高圖論課程的教學效果.

關鍵詞：數學建模；圖論；實踐

中圖分類號：G642.0 文獻標志碼：A 文章編號：1674-9324（2013）45-0233-03

一、引言

圖論是組合數學的一個重要分支。它以圖為研究對象，這種圖由若干給定的點及連接兩點的邊所構成，通常用來描述某些事物之間的某種特定關系，以點代表事物，以連接兩點的邊表示兩個事物間具有這種關系。圖論的應用非常廣泛，在實際的生活生產中，有很多問題可以用圖論的知識和方法來解決，其應用性已涉及物理學、化學、信息論、控制論、網絡理論、博弈、運輸網絡、社會科學以及管理科學等諸多領域。目前高校很多課程都涉及到圖論知識，例如離散數學、數據結構、算法分析與設計、運籌學、組合數學、拓撲學、網絡優化等。甚至有些專業將圖論作為一門必修或選修課程來開設。

由于圖論課程具有概念多、公式復雜和定理難證明、難理解等特點，在一定程度上造成教學難，證明抽象度高，學生難以理解，學生不能真正理解圖論思想，更談不上靈活運用圖論知識來解決各種實際問題。從而會使學生感到圖論的學習非常枯燥。大學數學課程教學改革的趨勢，越來越注重數學的應用性，而數學建模過程就是利用已經掌握的數學知識來解決實際問題的過程。在當前實現數學作為一種應用能力的過程中，使用數學解決實際問題的能力培養是非常重要和必需的。因此，在大學數學類課程的教學中融入數學建模思想是目前數學課程教學改革的一個大的趨勢。由于圖論的概念和定理大多是從實際問題中抽象出來的，因此圖論中的諸多模型和算法是數學建模強有力的理論依據。所以在圖論課程教學中注重介紹這些概念和理論的實際背景，引導學生利用數學建模思想方法學習圖論的相關概念和定理，探究圖論的發展規律，從而將更好地幫助學生理解和掌握這些概念和理論。

二、數學建模思想方法

數學模型就是用數學語言，通過抽象、簡化，建立起來的描述客觀事物的特征及其內在聯系的數學結構。這個結構可以是公式、方程、表格、圖形等。把現實模型抽象、簡化為某種數學結構（即數學模型）之后，我們就可以用相關的數學知識來求出這個模型的解，驗證模型的合理性，并用該數學模型所提供的解答來解釋現實問題，這個過程便稱為數學建模。其目的是將復雜的客觀事物或聯系簡單化并用數學手段對其進行分析和處理。建立數學模型解決現實問題要經過模型準備、模型假設、模型構成、模型求解和模型分析這五個步驟。模型準備就是了解問題的實際背景，明確建模目的，搜集必要的各種信息，盡量弄清對象的特征，形成一個比較明晰的“問題”。模型假設是根據對象的特征和建模目的，抓住問題的本質，做出必要的、合理的簡化假設。模型構成是根據所作的假設，用數學的語言、符號描述對象的內在規律，建立包含常量、變量等的數學模型。模型求解是采用解方程、畫圖形、優化方法、數值計算、統計分析等各種數學方法，特別是數學軟件和計算機技術求解。模型分析就是對求解結果進行數學上的分析，并解釋為對現實問題的解答。由此可見，思想數學建模就是將數學的理論知識應用于解決實際問題，培養數學建模思想就是鍛煉應用數學的能力。

在圖論的教學中引入數學建模思想，將生活中的實際問題引入課堂，利用圖論知識分析實際問題，讓學生感受到圖論貼近生活。教學中可以引導學生自己尋找與圖論相關的實際問題，利用圖論知識建立實際問題的數學模型，并進行報告和討論，讓學生發表自己的見解和看法，在此過程中有助于學生對所學知識的融會貫通和掌握，大大提高學生學習圖論的興趣。

三、數學建模思想方法融入圖論教學的實踐

目前，各門數學課程教學改革所面臨的一個課題是如何增強應用數學知識解決實際問題的意識。在這樣的背景下，加之圖論知識的應用廣泛性，從而，將數學建模的思想方法融入到圖論課程教學中的研究和實踐已顯得刻不容緩。因此，結合圖論教學內容有機地增加數學建模教學內容，使廣大的學生能學習和體會到數學建模的基本思想方法，在日常的學習中培養學生應用圖論知識的意識，激發了學生學習圖論的積極性。

（一）在圖論定理公式中滲入建模的案例

在圖論某些定理證明的教學過程中可以適當地融入數學建模的思想與方法，把定理的結論看作一個特定的模型，需要去建立它。于是，當把定理的條件看作是模型的假設時，可根據預先設置的問題，情景引導學生發現定理的結論，從而定理證明的方法也隨之顯現。

案例1：設為任意無向圖，V={v1，v2，…，vn}，|E|=m，證明所有頂點的度數和=2m，并且奇點個數為偶數。

解析：證明該結論之前，首先任意選取若干個學生讓其隨機互相握手，并記下每個人的握手次數和每兩人之間握手的次數，由此可得每個人握手次數總和是每兩人之間握手次數的2倍以及握過奇數次手的人數一定是偶數。互動之后介紹該定理稱之為握手定理，從互動過程中可以建立定理結論的模型，并且證明的思路也是顯而易見的。

（二）在應用性例題中滲入數學建模的方法

案例2：一家公司生產有c1，c2，c3，c4，c5，c6，c7七種化學制劑，其中制劑（c1，c2），（c1，c4），（c2，c3），（c2，c5），（c2，c7），（c3，c4），（c3，c5），（c3，c6），（c4，c5），（c4，c7），（c5，c6），（c6，c7）之間是互不相容的，如果放在一起能發生化學反應，引起危險。因此，作為一種預防措施，該公司必須把倉庫分成互相隔離的若干區，以便把不相容的制品儲藏在不同的區，問至少要劃分多少小區，怎樣存放才能保證安全。

解析：首先建立模型，用圖來表示實例中這些制劑和他們之間關系，用頂點v1，v2，v3，v4，v5，v6，v7，表示c1，c2，c3，c4，c5，c6，c7表示七種化學制品，把不能放在一起的兩種制品對應的頂點用一條邊連接起來，如圖1。

模型求解：由圖可得極小覆蓋的邏輯表達式為：

（v1+v2v4）（v2+v1v3v5v7）（v3+v2v4v5v6）（v4+v1v3v5v7）（v5+v23v4v6）（v6+v3v5v7）（v7+v2v4v6）

利用邏輯代數法則簡化上述邏輯表達式為：

v1v3v5v7+v2v3v4v5v6+v2v4v5v6+v2v3v4v6

從而可得全部極小覆蓋為：

（v1，v3，v5，v7），（v2，v3，v4，v5，v7），（v2，v4，v5，v6），（v2，v3，v4，v6）

由于極大獨立集與極小覆蓋集之間互補的關系，所以上圖的所有極大獨立集為（v2，v4，v6），（v1，v6），（v1，v3，v7），（v1，v5，v7）.取圖G的一個極大獨立集V1=（v2，v4，v6），將其著第一種顏色。在VG-V1中，所有極大獨立集為，（v1，v3，v7），（v1，v5，v7），取V2=（v1，v3，v7）將其著第二種顏色。在VG-V1-V2中僅有點v5，將其著第三種顏色，故χ（G）=3.

于是得到該化學制品的存放方案：至少需要把倉庫劃分為3個區，可以將c2，c4，c6三種制品，c1，c3，c7三種制品和制品c5分別存放在一個區。

（三）設計相關數學建模問題，提高學生應用圖論知識解決實際問題的能力

由于教學課時的限制，將數學建模的思想方法融入圖論課程教學時，不能專門地讓學生學習建模，只能通過一些簡單的模型給學生介紹數學建模的思想及方法。圖論是現代數學的一個重要分支，在自然科學、社會科學、機械工程中有重要的意義，其求解思想滲透到自然學科的各個領域。因此，可以通過設計一些與圖論課程相關的課外建模活動，選擇符合學生實際并貼近生活的一些圖論問題，啟迪學生的論文查閱意識和能力，指導學生閱讀相關論文，最后以解題報告或小論文的形式提交他們的結果。促進學生應用圖論知識解決實際問題的能力。

四、結語

將數學建模思想方法融入圖論課程的教學中，使圖論課程教學與數學建模有機結合起來，激發學生學習圖論的興趣，培養學生勇于探索的精神，提高學生的動手能力，實踐表明這些方法能較好地提高圖論課程的教學效果。

參考文獻：

[1]Bondy J A，Murty U S R.Graph theory with applications[M].North-Holland：Elsevier，1976.

[2]翟明清.淺析圖論教學[J].大學數學，2011，27（5）：23-26.

[3]定向峰.將數學建模的思想和方法融入圖論課程教學中的一點嘗試[J].重慶教育學院學報，2006，19（6）：28-31.

[4]張清華，陳六新，李永紅.圖論教育教學改革與實踐[J].電腦知識與技術，2012，8（34）：8235-8237.

[5]姜啟源，謝金星，葉俊.數學模型[M].第4版.北京：高等教育出版社，2011.

基金項目：2011年新世紀廣西高等教育教改工程立項項目（2011JGB321）

作者簡介：喬友付（1978-），男，安徽霍邱人，碩士，副教授，主要研究方向：圖論及其應用。