閆超君

(安徽水利水電職業(yè)技術(shù)學(xué)院，安徽合肥231603)

工程實(shí)踐中，常用雙代號(hào)網(wǎng)絡(luò)圖表達(dá)工作之間的相互關(guān)系和整個(gè)工程任務(wù)的全貌，通過(guò)分析計(jì)算，找出對(duì)全局有決定性影響的關(guān)鍵線路和各項(xiàng)關(guān)鍵工作，據(jù)此對(duì)任務(wù)作出切實(shí)可行的全面規(guī)劃和安排。確定雙代號(hào)網(wǎng)絡(luò)圖關(guān)鍵線路的方法有很多，諸如:直接法、總時(shí)差最小法、節(jié)點(diǎn)參數(shù)法、時(shí)標(biāo)網(wǎng)絡(luò)圖法、標(biāo)號(hào)法、破圈法。其中破圈法運(yùn)用時(shí)不需大量計(jì)算，是一種比較簡(jiǎn)便直觀的方法，但由于在運(yùn)用破圈法時(shí)，有一些誤區(qū)存在。為此，在實(shí)際工作中很少有人運(yùn)用，使得破圈法應(yīng)用不是很廣泛。

1 對(duì)破圈法的初步認(rèn)識(shí)

在雙代號(hào)網(wǎng)絡(luò)圖中有許多節(jié)點(diǎn)和箭線，這些節(jié)點(diǎn)和箭線形成了許多封閉的“圈”，這些“圈”是指在兩個(gè)節(jié)點(diǎn)之間由兩條線路連通該二個(gè)節(jié)點(diǎn)所形成的最小圈。破圈法是將網(wǎng)絡(luò)中各個(gè)封閉圈的二條線路按各自所含工作的持續(xù)時(shí)間來(lái)進(jìn)行比較，破掉持續(xù)時(shí)間短的線路，逐個(gè)“破圈”，直至圓圈不可破時(shí)為止，最后剩下的線路即為網(wǎng)絡(luò)圖的關(guān)鍵線路如圖1。

從節(jié)點(diǎn)①開(kāi)始，節(jié)點(diǎn)①、②、③形成了第一個(gè)圈，從節(jié)點(diǎn)①到節(jié)點(diǎn)③有二條線路，一條是①→③，一條是①→②→③。①→③需要時(shí)間是6，①→②→③需要時(shí)間是5，因6﹥5所以切斷①→②→③。

從節(jié)點(diǎn)②開(kāi)始，節(jié)點(diǎn)②、③、④形成了第二個(gè)圈，從節(jié)點(diǎn)②到節(jié)點(diǎn)④有二條線路，一條是②→③→④，一條是②→④。②→③→④需要時(shí)間是6，②→④需要時(shí)間是4，因6﹥4所以切斷②→④。

從節(jié)點(diǎn)③開(kāi)始，節(jié)點(diǎn)③、④、⑤形成了第三個(gè)圈，從節(jié)點(diǎn)③到節(jié)點(diǎn)⑤有二條線路，一條是③→④→⑤，一條是③→⑤。③→④→⑤需要時(shí)間是4，③→⑤需要時(shí)間是1，因4﹥1所以切斷③→⑤。

從節(jié)點(diǎn)④開(kāi)始，節(jié)點(diǎn)④、⑤、⑥形成了第四個(gè)圈，從節(jié)點(diǎn)④到節(jié)點(diǎn)⑥有二條線路，一條是④→⑤→⑥，一條是⑤→⑥。④→⑤→⑥需要時(shí)間是3，④→⑥需要時(shí)間是2，因3﹥2所以切斷④→⑥。剩下的即為關(guān)鍵線路，見(jiàn)圖2所示中的雙箭線。

2 誤區(qū)分析

上述示例看似正確，但有不少誤區(qū)存在。比如按上述方法確定圖3所示的雙代號(hào)網(wǎng)絡(luò)圖，關(guān)鍵線路就確定不出來(lái)，甚至判斷出錯(cuò)誤的關(guān)鍵線路。

按上述所述破圈法，從節(jié)點(diǎn)①開(kāi)始，節(jié)點(diǎn)①、②、③形成了第一個(gè)圈，從節(jié)點(diǎn)①到節(jié)點(diǎn)③有二條線路，一條是①→③，一條是①→②→③。①→③需要時(shí)間是2，①→②→③需要時(shí)間是3，因3﹥2所以切斷①→③。

從節(jié)點(diǎn)①開(kāi)始，節(jié)點(diǎn)①、③、④、⑤形成了第二個(gè)圈，從節(jié)點(diǎn)①到節(jié)點(diǎn)⑤有二條線路，一條是①→③→⑤，一條是①→④→⑤。①→③→⑤需要時(shí)間是4，①→④→⑤需要時(shí)間是7，因7﹥4所以切斷①→③→⑤。

同理可切斷⑦→⑧，④→⑧。關(guān)鍵線路如圖4雙箭線所示。但是，用此方法判斷出的關(guān)鍵線路是錯(cuò)誤的。正確的關(guān)鍵線路如圖5雙箭線所示。

出現(xiàn)破圈法判別的關(guān)鍵線路不正確的原因就是大家對(duì)破圈法的錯(cuò)誤理解，判斷中存在誤區(qū)，現(xiàn)分析一下存在的誤區(qū)。

誤區(qū)一:破圈時(shí)，去掉一整條線路。凡遇到節(jié)點(diǎn)有兩個(gè)及兩個(gè)以上的內(nèi)向箭線時(shí)，肯定有一個(gè)圈，比較時(shí)間長(zhǎng)短，把時(shí)間較短線路流進(jìn)的一個(gè)箭線去掉，如圖6所示只去掉②→③，誤區(qū)是把整條線路去掉如圖7所示，去掉了①→②箭線和①→③箭線。

誤區(qū)二:破掉的箭線，找下一個(gè)圈時(shí)還在用。破圈法找圈時(shí)，破掉的箭線不能再次用，誤區(qū)是去掉的箭線還繼續(xù)用。圖4中到⑤節(jié)點(diǎn)有兩個(gè)內(nèi)向箭線，一定有個(gè)最小的圈，此最小的圈不是由①→③→⑤和①→④→⑤兩條線組成的圈，因?yàn)棰佟垡哑频簦怯散佟凇邸莺廷佟堋輧蓷l線組成的圈。圖4中到⑦節(jié)點(diǎn)有兩個(gè)內(nèi)向箭線，一定有個(gè)最小的圈，此最小的圈不是由②→③→⑤→⑦和②→⑥→⑦兩條線組成的圈，因?yàn)棰邸菀哑频?，而是由①→②→⑥→⑦和①→④→⑤→⑦兩條線組成的圈。

誤區(qū)三:破圈法不能判別所有雙代號(hào)網(wǎng)絡(luò)圖的關(guān)鍵線路。由于不能正確地找到“圈”，就不能正確地破“圈”，以至于雙代號(hào)網(wǎng)絡(luò)圖利用破圈法確定關(guān)鍵線路，破到最后，連一條完整的線路都沒(méi)有，就不能確定出關(guān)鍵線路，于是認(rèn)為，破圈法不科學(xué)，不好用，不能判別所有雙代號(hào)網(wǎng)絡(luò)圖的關(guān)鍵線路。正是因?yàn)榇嗽?，很多教科?shū)上都不介紹破圈法。實(shí)際是所有的雙代號(hào)網(wǎng)絡(luò)圖都可以用破圈法判別出關(guān)鍵線路。

3 正確利用破圈法確定關(guān)鍵線路

通過(guò)對(duì)破圈法的再認(rèn)識(shí)，走出誤區(qū)，正確判別雙代號(hào)網(wǎng)絡(luò)圖的關(guān)鍵線路。對(duì)圖3所示網(wǎng)絡(luò)圖進(jìn)行破圈法判別關(guān)鍵線路。

從節(jié)點(diǎn)①開(kāi)始，到③有兩條內(nèi)向箭線，節(jié)點(diǎn)①、②、③形成一個(gè)圈，即從節(jié)點(diǎn)①到節(jié)點(diǎn)③有二條線路，一條是①→③，一條是①→②→③。①→③需要時(shí)間是2，①→②→③需要時(shí)間是3，因3﹥2所以切斷①→③。

到節(jié)點(diǎn)⑤有兩條內(nèi)向箭線，但①→③箭線已被斷開(kāi)，所以節(jié)點(diǎn)①、③、④、⑤不能形成一個(gè)圈，應(yīng)擴(kuò)大范圍找“圈”，節(jié)點(diǎn)①、②、③、④、⑤形成一個(gè)圈，即從節(jié)點(diǎn)①到節(jié)點(diǎn)⑤有二條線路，一條是①→②→③→⑤，一條是①→④→⑤。①→②→③→⑤需要時(shí)間是5，①→④→⑤需要時(shí)間是7，因7﹥5所以切斷③→⑤。

到節(jié)點(diǎn)⑦有兩條內(nèi)向箭線，由于③→⑤已破掉，所以節(jié)點(diǎn)②、③、⑤、⑥、⑦不能形成一個(gè)圈，應(yīng)擴(kuò)大范圍找“圈”，節(jié)點(diǎn)①、②、④、⑤、⑥、⑦形成一個(gè)圈，即從節(jié)點(diǎn)①到節(jié)點(diǎn)⑦有二條線路，一條是①→②→⑥→⑦，一條是①→④→⑤→⑦。①→②→⑥→⑦需要時(shí)間是8，①→④→⑤→⑦需要時(shí)間是10，因10﹥8，所以切斷⑥→⑦。

到節(jié)點(diǎn)⑧有三條內(nèi)向箭線，一定有兩個(gè)圈，節(jié)點(diǎn)④、⑤、⑦、⑧形成一個(gè)圈，即從節(jié)點(diǎn)④到節(jié)點(diǎn)⑧有二條線路，一條是④→⑤→⑦→⑧，一條是④→⑧。④→⑤→⑦→⑧需要時(shí)間是7，④→⑧需要時(shí)間是5，因7﹥5，所以切斷④→⑧。由于⑥→⑦已破掉，節(jié)點(diǎn)⑥、⑦、⑧不能形成一個(gè)圈，應(yīng)擴(kuò)大范圍找“圈”，節(jié)點(diǎn)①、②、⑥、⑧、④、⑤、⑦形成一個(gè)圈，即由①→②→⑥→⑧，和①→④→⑤→⑦→⑧這兩條線形成另一個(gè)圈，①→②→⑥→⑧需要時(shí)間是13，①→④→⑤→⑦→⑧需要時(shí)間是14，因14﹥13，所以切斷⑥→⑧，如圖8所示。

剩下的線路，能從起點(diǎn)走到終點(diǎn)的線路就是關(guān)鍵線路，①→②→⑥走不通，不是關(guān)鍵線路，①→④→⑤→⑦→⑧從起點(diǎn)走到了終點(diǎn)，故是關(guān)鍵線路，如圖8雙箭線所示。

從圖8可以看出，關(guān)鍵線路與標(biāo)號(hào)法確定的關(guān)鍵線路(圖5)一致。

4 結(jié)束語(yǔ)

通過(guò)對(duì)破圈法的誤區(qū)分析，運(yùn)用破圈法時(shí)注意三原則:破最小的圈、破過(guò)的線)不可以再用、只破流進(jìn)箭線的一個(gè)箭線。走出誤區(qū)，就能快速地運(yùn)用破圈法判別雙代號(hào)網(wǎng)絡(luò)圖的關(guān)鍵線路，而且所有的雙代號(hào)網(wǎng)絡(luò)圖都可以用破圈法確定關(guān)鍵線路。

破圈法不需計(jì)算時(shí)間參數(shù)，通過(guò)破圈就可以確定出關(guān)鍵線路，簡(jiǎn)單直觀，是一種非常實(shí)用的確定雙代號(hào)網(wǎng)絡(luò)圖關(guān)鍵線路的方法。

［1] 閆超君.建設(shè)工程進(jìn)度控制［M] .合肥:合肥工業(yè)大學(xué)出版社，2009.

［2] 龐素珍.用圖論理論正確掌握破圈法［J] .河北北方學(xué)院學(xué)報(bào)，2007(5):80－82.

［3] 董躍華，李云浩.用破圈法實(shí)現(xiàn)普利姆算法［J] .江西理工大學(xué)學(xué)報(bào)，2008(4):20－21.

［4] 郭月明.運(yùn)籌學(xué)［M] .廣州:華南理工大學(xué)出版社，2001.

［5] 李濟(jì)民.用圖論指導(dǎo)破圈法的學(xué)習(xí)［J] .經(jīng)濟(jì)與管理，1998(1):42－43.

［6] 周 迎.破圈法解動(dòng)態(tài)規(guī)劃中的最短路問(wèn)題［J] .西昌農(nóng)業(yè)高等?？茖W(xué)校學(xué)報(bào)，2003(3):68－69.