基于計(jì)算思維的圖論問(wèn)題研究

柳 欣

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

0 引言

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

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

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

1 問(wèn)題提出

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

1.1 問(wèn)題1

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

圖2 著色圖

1.2 問(wèn)題2

期末考試安排問(wèn)題。

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

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

已知：

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

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

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

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

問(wèn)：期末考試最少安排多少場(chǎng)可以完成。

2 問(wèn)題求解

以著色問(wèn)題為例說(shuō)明基于計(jì)算思維的圖論問(wèn)題求解過(guò)程。

2.1 建立模型

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

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

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

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

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

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

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

圖5 模型示意圖

2.2 模型計(jì)算

根據(jù)實(shí)際問(wèn)題建立的數(shù)學(xué)模型，屬于離散數(shù)學(xué)圖論中的著色問(wèn)題，對(duì)問(wèn)題的求解等價(jià)于對(duì)圖中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)，是無(wú)效的。s3為無(wú)效結(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)，都是無(wú)效的。所以，結(jié)點(diǎn)s5和s6為無(wú)效結(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)的著色號(hào)，利用回溯法求解著色問(wè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í)顯示顏色不夠用，說(shuō)明在顏色數(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é)語(yǔ)

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