柳 欣

(山西大學(xué)商務(wù)學(xué)院信息學(xué)院，山西 太原 030031)

0 引言

計(jì)算思維是人類尋求問題求解的途徑。計(jì)算思維能力主要包括：符號表示、邏輯思維、形式化證明、建立模型、模型計(jì)算、利用計(jì)算機(jī)技術(shù)等[1-3]。

圖論是離散數(shù)學(xué)的重要組成部分，也是數(shù)據(jù)結(jié)構(gòu)和算法分析的重要內(nèi)容之一。通常來說，我們會把圖視為一種由“頂點(diǎn)”組成的抽象網(wǎng)絡(luò)，網(wǎng)絡(luò)中的各頂點(diǎn)可以通過“邊”實(shí)現(xiàn)彼此的連接，表示兩頂點(diǎn)有關(guān)聯(lián)。由此得到最基礎(chǔ)的2個(gè)概念，頂點(diǎn)(vertex)和邊(edge)。頂點(diǎn)用來表示某個(gè)對象或是事物。邊用來表示事物與事物之間的邏輯關(guān)系[4]。圖論算法是我們經(jīng)常用來求解實(shí)際問題的一種方法，在數(shù)學(xué)建模的求解過程中也經(jīng)常應(yīng)用。為了使得圖論算法思路更加清晰，將計(jì)算思維引入圖論算法中，具體如圖1所示。

圖1 融入計(jì)算思維的圖論問題求解模式

1 問題提出

著色問題是圖論的重要組成部分，給定無向圖G=(V,E)，用n種顏色為無向圖中的每個(gè)頂點(diǎn)V著色，要求為每1個(gè)頂點(diǎn)畫1種顏色，并且使相鄰兩個(gè)頂點(diǎn)之間有兩種不同顏色，這個(gè)問題叫做圖的著色問題[5]。下面分別列舉了兩個(gè)著色問題。

1.1 問題1

給圖2著色，要求相鄰城市間著上不同的顏色。

圖2 著色圖

1.2 問題2

期末考試安排問題。

某學(xué)期信息學(xué)院期末考試課程如下：

軟件工程、高級語言程序設(shè)計(jì)、微機(jī)原理與接口技術(shù)、離散數(shù)學(xué)、現(xiàn)代通信技術(shù)。

已知：

1) 軟件工程專業(yè)的學(xué)生開設(shè)軟件工程、微機(jī)原理與接口技術(shù)、離散數(shù)學(xué)課程。

2) 網(wǎng)絡(luò)工程專業(yè)學(xué)生開設(shè)離散數(shù)學(xué)、微機(jī)原理與接口技術(shù)、現(xiàn)代通信技術(shù)課程。

3) 計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生開設(shè)離散數(shù)學(xué)和高級語言程序設(shè)計(jì)課程。

4) 物聯(lián)網(wǎng)專業(yè)學(xué)生開設(shè)高級語言程序設(shè)計(jì)和現(xiàn)代通信技術(shù)課程。

問：期末考試最少安排多少場可以完成。

2 問題求解

以著色問題為例說明基于計(jì)算思維的圖論問題求解過程。

2.1 建立模型

1) 如果兩個(gè)城市相鄰，就在兩個(gè)城市之間畫一條邊。結(jié)構(gòu)如圖3所示。

圖3 問題1結(jié)構(gòu)圖

2) 如果兩門課程對應(yīng)的學(xué)生專業(yè)相同，就在兩門課程之間畫一條邊。結(jié)構(gòu)如圖4所示。

圖4 問題2結(jié)構(gòu)圖

問題1建模：把每個(gè)城市抽象化為1個(gè)點(diǎn)，張家界、懷化、常德、婁底、益陽依次用v1-v5表示。

問題2建模：把每門考試課程抽象化為1個(gè)點(diǎn)，軟件工程、離散數(shù)學(xué)、微機(jī)原理與接口技術(shù)、高級語言程序設(shè)計(jì)、現(xiàn)代通信技術(shù)依次用v1-v5表示。

上述兩個(gè)問題得到的模型如圖5所示。

圖5 模型示意圖

2.2 模型計(jì)算

根據(jù)實(shí)際問題建立的數(shù)學(xué)模型，屬于離散數(shù)學(xué)圖論中的著色問題，對問題的求解等價(jià)于對圖中v1-v5進(jìn)行著色，要求相鄰接點(diǎn)著不同的顏色。

步驟1：從結(jié)點(diǎn)s1出發(fā)，v1著顏色1生成結(jié)點(diǎn)s2，產(chǎn)生的著色序列為(1,0,0,0,0)，是有效的。

步驟2：從結(jié)點(diǎn)s2出發(fā)，v2著顏色1生成結(jié)點(diǎn)s3，產(chǎn)生的著色序列為(1,1,0,0,0)，是無效的。s3為無效結(jié)點(diǎn)。

步驟3：從結(jié)點(diǎn)s4出發(fā)，v2著顏色2生成結(jié)點(diǎn)s4，產(chǎn)生的著色序列為(1,2,0,0,0)，是有效的。

步驟4：v3分別著顏色1和2，生成結(jié)點(diǎn)s5和s6，產(chǎn)生的著色序列分別為(1,2,1,0,0)和(1,2,2,0,0)，都是無效的。所以，結(jié)點(diǎn)s5和s6為無效結(jié)點(diǎn)。

步驟5：v3著顏色3，生成結(jié)點(diǎn)s7，產(chǎn)生的著色序列為(1,2,3,0,0)，是有效的。重復(fù)上述步驟，最后得到有效著色(1,2,3,3,1)。

著色流程如圖6所示。

圖6 著色流程圖

這樣，得到v1～v5這5個(gè)頂點(diǎn)著色次序依次為：1、2、3、3、1。

2.3 編程實(shí)現(xiàn)及結(jié)果分析

具體算法如下：

設(shè)數(shù)組col [m]為頂點(diǎn)的著色號，利用回溯法求解著色問題，算法如下：

void GraphCol (int m, int c[ ][ ], int j)

{

for (i=1; i<=m; i++ )

col [i]=0;

a=1;

while (a>=1)

{col [a]=col[a]+1;

while (col [a]<=j)

if Ok(a) break;

else col[a]=col [a]+1;

if (col [a]<=j && a= =m)

{for (i=1; i<=m; i++)

cout<

return;

}

else if (col [a]<=n && a

a=a+1;

else {

col [a]=0;a=a-1; }

}

}

引入圖的鄰接矩陣：

得到的實(shí)驗(yàn)結(jié)果如下。

在采用2種顏色為5個(gè)頂點(diǎn)進(jìn)行著色如圖7所示。

圖7 2種顏色著色結(jié)果圖

在采用3種顏色為5個(gè)頂點(diǎn)進(jìn)行著色如圖8所示。

實(shí)驗(yàn)結(jié)果分析：在采用2種顏色為5個(gè)頂點(diǎn)著色時(shí)顯示顏色不夠用，說明在顏色數(shù)小于等于2時(shí)，不能為5個(gè)頂點(diǎn)著色。繼續(xù)增加至3種顏色，實(shí)驗(yàn)結(jié)果為v1～v5這5個(gè)頂點(diǎn)著色次序?yàn)?、2、3、3、1，與理論推導(dǎo)結(jié)果一致。

圖8 3種顏色著色結(jié)果圖

3 結(jié)語

實(shí)踐證明，融入計(jì)算思維的圖論問題求解模式，將計(jì)算思維的符號表示、建立模型、模型計(jì)算和系統(tǒng)實(shí)現(xiàn)與圖論問題求解過程巧妙地結(jié)合在一起，使得問題求解思路更加清晰，具有一定的應(yīng)用價(jià)值。