第3章 圖的定向理論

3.1 網絡活性與圖的可定向性

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

為實現托盤物資的流暢轉運和高效存取，貨架軌道結構設計應保證整個貨架軌道交通網絡的活性，通過設計存儲巷道軌道、主軌道、提升機通道和軌道節點的交通規則，限定貨架軌道結構，確保其不會發生路徑死鎖。若一個貨架交通網絡通過設定一定的交通規則，總能保證貨架內運行的四向穿梭車能從某一個位置到達另一個位置，而不發生路徑沖突和死鎖，則稱該貨架交通網絡為活網絡，否則稱為死網絡。

在圖論中，圖由點和邊組成。將存儲貨位、存儲巷道軌道、主軌道、垂直提升機、貨架端口等抽象為圖的點和邊，則四向穿梭式自動化密集倉儲系統的貨架可抽象為圖進行研究。進一步地，可用圖論的方法分析貨架和交通網的結構和性質。活貨架網絡對應的圖為活圖，死貨架網絡對應的圖為死圖。

1.基礎知識

圖是一個三元組，記作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的關聯函數。若?G（e）=（u，v），e∈E（G），（u，v）∈V（G）×V（G），則簡寫成e=uv；稱u為有向邊e的起點，v為有向邊e的終點。

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

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

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

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

顯然，由強連通圖的定義可知，強連通圖是活圖，強連通圖對應的貨架交通網絡是活網絡。

設G是任意圖，x為G的任一頂點，與頂點x關聯的邊數稱為x的度數。設D是任意有向圖，x為D的任一頂點，射入x的邊數稱為x的入度，記作d+（x）；射出x的邊數稱為x的出度，記作d-（x）。圖D中節點的最小入度和最小出度分別記作δ+（x）和δ-（x），最大入度和最大出度分別記作Δ+（x）和Δ-（x）。

2.圖的定向相關定理

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

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

反證法：設圖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連結e的端點u1v1，不妨設P是從u1到v1的有向跡，則將邊e定向為從v1到u1，即邊e成為定向后的有向邊v1u1。這樣定向了兩條邊的圖仍然是強連通的，其中沒有定向的邊認為是雙向的。重復前面的過程，則最終G的每條邊會得到一個定向，使定向后的圖D（G）是強連通的。

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

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

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

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

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

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

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

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

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