3.2 可定向圖的一種定向方法

給定圖G，給G的邊定向，使定向后的圖D（G）是強連通圖。

首先，將圖G的n個頂點分別給出標號v1，v2，…，vn。顯然，圖G是連通圖且不含割邊，否則其不存在強連通定向。

任選一個頂點標號v1，選一條邊以標號v1的頂點為端點，給這條邊的另一端頂點標號v2。以此類推，對k個已標號的頂點，其標號為v1，v2，…，vk，如果存在一條邊以vk為端點而另一端是未標號的頂點，則給這個頂點標號vk+1。如果不存在這樣的頂點，即與vk關聯的邊的另一端都已標號，這時在已標號的頂點中找一個標號最大的頂點vj，使它與一個未標號的頂點鄰接，給這個與vj鄰接的未標號的頂點標號vk+1。當所有頂點得到標號時，對于在標號過程中用到的邊，定向為從標號大的頂點到標號小的頂點，從而實現對圖G的定向。

可以證明，用上述方法定向所得的圖是強連通的。

對同一個圖，可以有多個定向方式。以圖3-2a中的圖為例，該圖有6個頂點，分別采用不同的順序對其進行定向。首先選擇位于圖中左上部的頂點，標記為v1。與v1相鄰的頂點有兩個，若選擇v1下方的頂點并標記為v2，然后依次選擇頂點進行標記，則最后可得到如圖3-2b所示的定向結果；若選擇v1右側的頂點并標記為v2，然后依次選擇頂點進行標記，則最后可得到如圖3-2c所示的定向結果。顯然，兩種不同的定向順序得到了不同的定向結果。

圖3-2 不同定向方式得到的定向結果

對四向穿梭式自動化密集倉儲系統而言，只要貨架交通網絡是活網絡，即可保證托盤物資在貨架內部流暢轉運。但是，對于某一活貨架交通網絡，在不同的定向結果下，將托盤物資從一個位置轉運到另一個位置的路徑長度存在差別，從而導致物資轉運和存取效率存在差別。因此，在對既有貨架網絡進行定向時，還應結合其他因素綜合設計，以獲得較高的托盤物資轉運和存取效率。