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 不同定向方式得到的定向结果

对四向穿梭式自动化密集仓储系统而言，只要货架交通网络是活网络，即可保证托盘物资在货架内部流畅转运。但是，对于某一活货架交通网络，在不同的定向结果下，将托盘物资从一个位置转运到另一个位置的路径长度存在差别，从而导致物资转运和存取效率存在差别。因此，在对既有货架网络进行定向时，还应结合其他因素综合设计，以获得较高的托盘物资转运和存取效率。