第3章 圖的定向理論

3.1 網(wǎng)絡(luò)活性與圖的可定向性

四向穿梭式自動化密集倉儲系統(tǒng)的貨架由存儲貨位、存儲巷道軌道、主軌道、垂直提升機、貨架端口等組成，四向穿梭車在貨架內(nèi)運行，將托盤集裝物資從一個位置運送到另一個位置。因此，四向穿梭式自動化密集倉儲系統(tǒng)的貨架貨位布局設(shè)計應(yīng)滿足托盤集裝物資在貨架內(nèi)的轉(zhuǎn)運需求。在此基礎(chǔ)上設(shè)計貨架軌道，并進一步滿足物資高效存取需求。

為實現(xiàn)托盤物資的流暢轉(zhuǎn)運和高效存取，貨架軌道結(jié)構(gòu)設(shè)計應(yīng)保證整個貨架軌道交通網(wǎng)絡(luò)的活性，通過設(shè)計存儲巷道軌道、主軌道、提升機通道和軌道節(jié)點的交通規(guī)則，限定貨架軌道結(jié)構(gòu)，確保其不會發(fā)生路徑死鎖。若一個貨架交通網(wǎng)絡(luò)通過設(shè)定一定的交通規(guī)則，總能保證貨架內(nèi)運行的四向穿梭車能從某一個位置到達(dá)另一個位置，而不發(fā)生路徑?jīng)_突和死鎖，則稱該貨架交通網(wǎng)絡(luò)為活網(wǎng)絡(luò)，否則稱為死網(wǎng)絡(luò)。

在圖論中，圖由點和邊組成。將存儲貨位、存儲巷道軌道、主軌道、垂直提升機、貨架端口等抽象為圖的點和邊，則四向穿梭式自動化密集倉儲系統(tǒng)的貨架可抽象為圖進行研究。進一步地，可用圖論的方法分析貨架和交通網(wǎng)的結(jié)構(gòu)和性質(zhì)?；钬浖芫W(wǎng)絡(luò)對應(yīng)的圖為活圖，死貨架網(wǎng)絡(luò)對應(yīng)的圖為死圖。

1.基礎(chǔ)知識

圖是一個三元組，記作G={V（G），E（G），?G}。其中，V（G）={v1，v2，…，vn}，V（G）≠?，它是圖G的頂點集合；E（G）={e1，e2，…，em}是圖G的邊集合，其中ei={vj，vk}或ei=vj→vk，（若ei={vj，vk}，則稱ei為以vj和vk為端點的無向邊；若ei=vj→vk，則稱ei為以vj和vk為端點的有向邊）；?G為圖G的關(guān)聯(lián)函數(shù)。若?G（e）=（u，v），e∈E（G），（u，v）∈V（G）×V（G），則簡寫成e=uv；稱u為有向邊e的起點，v為有向邊e的終點。

設(shè)u1，…，un是圖G的頂點，e1，…，en是圖G的邊，G的有限頂點和邊交替序列u0e1u1e2…un-1enun形成一條u1-un鏈，u1和un稱為鏈的端點，其余頂點稱為鏈的內(nèi)部點。當(dāng)u1≠un時，稱該鏈為開的，否則為閉的。為簡化描述，將u1-un鏈用頂點序列u1u2…un-1un表示。

若圖G則中的邊皆為有向邊，則圖G為有向圖；若圖G中的邊皆為無向邊，則圖G為無向圖。設(shè)W是有向圖G中的u1-un鏈，指定W的方向是從u1到un，若W中所有邊的方向與此方向一致，則稱W為G中從u1到un的有向跡。兩端點相同的跡（閉跡）稱為圈，有向閉跡稱為有向圈。

若G是有向圖，如果對u，v∈V（G），存在從u到v的有向跡P（u，v），則稱u可達(dá)v；當(dāng)?u，v∈V（G），u可達(dá)v或v可達(dá)u時，稱G是單連通有向圖；當(dāng)?u，v∈V（G），不但u可達(dá)v，而且v可達(dá)u時，稱G是強連通有向圖；若把G的每邊箭頭均取消，所得到無向圖稱為有向圖G的底圖，底圖連通的有向圖稱為弱連通有向圖；任意一個無向圖G，將G的邊指定一個方向得到一個有向圖D，稱D為G的一個定向圖。

一個有向圖D是強連通的，是指D中任意兩個頂點之間都存在從一個頂點到另一個頂點的有向跡，即對任意兩個頂點u和v，在D中既存在從u到v的有向跡，也存在從v到u的有向跡。當(dāng)有向圖不是強連通時，則它可劃分為多個強連通分支，每個強連通分支是有向圖的極大強連通子圖。

顯然，由強連通圖的定義可知，強連通圖是活圖，強連通圖對應(yīng)的貨架交通網(wǎng)絡(luò)是活網(wǎng)絡(luò)。

設(shè)G是任意圖，x為G的任一頂點，與頂點x關(guān)聯(lián)的邊數(shù)稱為x的度數(shù)。設(shè)D是任意有向圖，x為D的任一頂點，射入x的邊數(shù)稱為x的入度，記作d+（x）；射出x的邊數(shù)稱為x的出度，記作d-（x）。圖D中節(jié)點的最小入度和最小出度分別記作δ+（x）和δ-（x），最大入度和最大出度分別記作Δ+（x）和Δ-（x）。

2.圖的定向相關(guān)定理

羅賓斯定理：一個圖G有強連通定向，當(dāng)且僅當(dāng)G是連通的并且不含割邊。

證明：充分條件。若圖G有強連通定向，則G沒有割邊。

反證法：設(shè)圖G有強連通定向且G有割邊uv，若uv是圖G的割邊且定向為從v到u，則定向后的圖D（G）中沒有從u到v的有向跡；若定向為從u到v，則圖D（G）中沒有從v到u的有向跡，與D（G）是強連通相矛盾。

必要條件。若G不含割邊，G一定存在一個定向，使定向后的圖D（G）是強連通的。一個無向圖可以看成一個有向圖，只要用一對方向相反的邊代替無向邊即可。這樣，首先將無向邊看成是雙向的。由于G連通，則這樣定向的圖是強連通的。對G的任一邊uv，由于uv不是割邊，則G中存在從v到u的跡不含邊uv。將從v到u的跡看成有向的，并將邊uv定向為從u到v的有向邊。這樣得到的圖是強連通的。注意：這里沒定向的邊看成是雙向的。同樣地，在G中再取一條沒有定向的邊e，由于它不是割邊，又邊uv定向后的圖仍是強連通的，于是圖G-e中存在一條有向跡P連結(jié)e的端點u1v1，不妨設(shè)P是從u1到v1的有向跡，則將邊e定向為從v1到u1，即邊e成為定向后的有向邊v1u1。這樣定向了兩條邊的圖仍然是強連通的，其中沒有定向的邊認(rèn)為是雙向的。重復(fù)前面的過程，則最終G的每條邊會得到一個定向，使定向后的圖D（G）是強連通的。

推論：一個圖G有強連通定向，當(dāng)且僅當(dāng)G的任何一條邊總是屬于某一個圈。該推論與羅賓斯定理等價，互為充分必要條件。

證明：充分條件。若圖G有強連通定向，則G的任何一條邊總是屬于某一個圈。

反證法：假設(shè)在強連通圖G=（V，E）中，vA∈V，vB∈V，vAvB∈E，邊vAvB不屬于任何圈。對圖G進行定向，若邊vAvB為圖G的有向邊（即定向為vA→vB），則圖G內(nèi)所有能到達(dá)點vA的點及其連通邊形成一個強連通子圖G1，所有vB能夠到達(dá)的點及其連通邊形成一個強連通子圖G2，如圖3-1所示。顯然，圖G2上的點不能到達(dá)圖G1，與圖G內(nèi)的點互相連通矛盾。

圖3-1 主軌道網(wǎng)存在割邊，不能強連通定向

若對圖G進行定向后，邊vBvA為圖G的有向邊（即定向為vB→vA），可以類似方法證明。

必要條件。如果圖G內(nèi)任何一條邊總是屬于某一個圈，則該圖不存在割邊，由羅賓斯定理可證。

綜上，圖G有強連通定向，當(dāng)且僅當(dāng)G的任何一條邊總是屬于某一個圈。

圖的定向定理：設(shè)G是強連通的混合圖，對于圖G的每條不是割邊的邊e，總可給邊e一個定向使得到的混合圖仍是強連通的。

證明：此定理的證明與羅賓斯定理的證明方法類似。