借助圖論方法，指導(dǎo)數(shù)學(xué)建模

唐紀(jì)芳

[摘 要] 圖論方法是數(shù)學(xué)建模的重要方法，通過利用圖式，很多數(shù)學(xué)難題都能得以快速巧妙地解決。根據(jù)多年的教學(xué)實(shí)踐經(jīng)驗(yàn)，淺談了幾點(diǎn)借助圖論方法，指導(dǎo)學(xué)生數(shù)學(xué)建模的策略，旨在提高學(xué)生解決問題的能力，升華其數(shù)學(xué)素養(yǎng)。

[關(guān) 鍵 詞] 高職；數(shù)學(xué)建模；圖論

[中圖分類號(hào)] G712 [文獻(xiàn)標(biāo)志碼] A [文章編號(hào)] 2096-0603（2018）08-0170-01

圖論是離散數(shù)學(xué)的一個(gè)重要分支，工程技術(shù)、自然科學(xué)、經(jīng)濟(jì)管理等領(lǐng)域的諸多問題通過借用圖論方法建立數(shù)學(xué)模型，都能得以迎刃而解。下面筆者針對(duì)圖論的幾種重要算法及其應(yīng)用展開了簡單的論述。

一、最短軌道問題，變換標(biāo)號(hào)

最短軌道問題指的是在給出的一個(gè)網(wǎng)絡(luò)中，找出任意兩點(diǎn)之間的最短路線及其長度。運(yùn)用圖論方法求解最短路問題時(shí)，首先需要從路線的起點(diǎn)開始，逐步尋找到達(dá)各點(diǎn)的最短路線，并且需要在每一步都對(duì)頂點(diǎn)記錄一個(gè)數(shù)，即做出該點(diǎn)的標(biāo)號(hào)，隨后不斷變換標(biāo)號(hào)，把一個(gè)不是最短距離標(biāo)號(hào)的頂點(diǎn)變成是最短距離標(biāo)號(hào)的頂點(diǎn)，最后得到最短的一條線路。應(yīng)用該算法可以高效地解決交通路網(wǎng)的布置、景觀路線的安排、運(yùn)輸路線的設(shè)計(jì)等實(shí)際問題。教師在進(jìn)行教學(xué)時(shí)，可以引導(dǎo)學(xué)生將實(shí)際問題轉(zhuǎn)化為圖論中的最短軌道問題，抽象出數(shù)學(xué)模型。

比如，筆者在對(duì)項(xiàng)目管理專業(yè)的高職學(xué)生進(jìn)行教學(xué)時(shí)，設(shè)計(jì)了如下的問題讓學(xué)生進(jìn)行作答：某建設(shè)單位A有一批鋼筋需要從城市v1運(yùn)送到施工單位所在城市v6，已知六座城市v1、v2、v3、v4、v5、v6之間的路網(wǎng)形式如下圖所示，請(qǐng)問選擇哪一條運(yùn)輸路線才能使成本最低呢？學(xué)生在解決這一問題時(shí)，建立了數(shù)學(xué)模型：W（P（v1，v6））=min{W（P），P取自所有v1到v6的軌道集合}，然后通過數(shù)次的迭代與標(biāo)號(hào)變換，找到了最短路線：v1→v3→v2→v4→v5→v6，且最短距離為12。

二、探究Euler回路，節(jié)點(diǎn)配對(duì)

隨著科學(xué)技術(shù)的發(fā)展，電路結(jié)構(gòu)變得越來越復(fù)雜，圖論方法在電路結(jié)構(gòu)設(shè)計(jì)與計(jì)算中扮演著十分重要的角色。Euler回路是由數(shù)學(xué)家歐拉在解決“七橋問題”時(shí)創(chuàng)設(shè)的，對(duì)于電氣等專業(yè)的高職學(xué)生，通過應(yīng)用Euler回路對(duì)復(fù)雜電路進(jìn)行分析，對(duì)支路的聯(lián)結(jié)點(diǎn)進(jìn)行配對(duì)，有助于得到最簡回路電流方程組，簡化電路的求解。

比如，筆者在引導(dǎo)相關(guān)專業(yè)的學(xué)生學(xué)習(xí)Euler回路時(shí)，帶大家探究了如下的電路問題：如下圖2所示，電路中有A、B、C、D、E五個(gè)節(jié)點(diǎn)，8條支路，13個(gè)回路……求解該電路。在探究這一問題時(shí)，筆者引導(dǎo)學(xué)生將歐拉回路的思想滲透到電路的分析與計(jì)算中來，選擇網(wǎng)孔作為一組獨(dú)立回路，4個(gè)網(wǎng)孔分別如下圖3所示，最后得到了7個(gè)電路方程，成功求解了該電路問題。

三、求最小生成樹，有效避圈

高職數(shù)學(xué)內(nèi)容一般比較抽象，學(xué)生在解決一些涉及離散型變量的數(shù)學(xué)問題時(shí)，常常會(huì)覺得比較吃力、困難。圖論方法具有直觀形象的優(yōu)點(diǎn)，比如說最小生成樹原理，通過用點(diǎn)與邊組成圖形表示現(xiàn)實(shí)世界中的各種關(guān)系，能夠使關(guān)系變得簡單明了，易于解決?？肆_斯克爾算法也叫做“避圈法”，利用該方法能夠有效建構(gòu)選線問題等題型的數(shù)學(xué)模型。因此在教學(xué)時(shí)，教師可以引導(dǎo)學(xué)生善于從題目中抽象出最小生成樹模型，提高他們解決專業(yè)相關(guān)問題的能力。

圖論在實(shí)際的生產(chǎn)生活中有著非常廣泛的應(yīng)用，其內(nèi)容與高職專業(yè)密切相關(guān)，教師應(yīng)注重結(jié)合專業(yè)合理組合圖論的教學(xué)內(nèi)容，使高職數(shù)學(xué)的教學(xué)更加專業(yè)化、高效化。

參考文獻(xiàn)：

[1]喬友付.數(shù)學(xué)建模在《圖論》教學(xué)中的作用[J].教育教學(xué)論壇，2013（37）：65-66.

[2]卜月華，王維凡，呂新忠.圖論及其應(yīng)用[M].東南大學(xué)出版社，2015.