理论教育 可定向图的定向方法

可定向图的定向方法

时间:2023-06-01 理论教育 版权反馈
【摘要】:,vk,如果存在一条边以vk为端点而另一端是未标号的顶点,则给这个顶点标号vk+1。以图3-2a中的图为例,该图有6个顶点,分别采用不同的顺序对其进行定向。显然,两种不同的定向顺序得到了不同的定向结果。图3-2 不同定向方式得到的定向结果对四向穿梭式自动化密集仓储系统而言,只要货架交通网络是活网络,即可保证托盘物资在货架内部流畅转运。

可定向图的定向方法

给定图G,给G的边定向,使定向后的图DG)是强连通图。

首先,将图Gn个顶点分别给出标号v1v2,…,vn。显然,图G是连通图且不含割边,否则其不存在强连通定向。

任选一个顶点标号v1,选一条边以标号v1的顶点为端点,给这条边的另一端顶点标号v2。以此类推,对k个已标号的顶点,其标号为v1v2,…,vk,如果存在一条边以vk为端点而另一端是未标号的顶点,则给这个顶点标号vk+1。如果不存在这样的顶点,即与vk关联的边的另一端都已标号,这时在已标号的顶点中找一个标号最大的顶点vj,使它与一个未标号的顶点邻接,给这个与vj邻接的未标号的顶点标号vk+1。当所有顶点得到标号时,对于在标号过程中用到的边,定向为从标号大的顶点到标号小的顶点,从而实现对图G的定向。

可以证明,用上述方法定向所得的图是强连通的。

对同一个图,可以有多个定向方式。以图3-2a中的图为例,该图有6个顶点,分别采用不同的顺序对其进行定向。首先选择位于图中左上部的顶点,标记为v1。与v1相邻的顶点有两个,若选择v1下方的顶点并标记为v2,然后依次选择顶点进行标记,则最后可得到如图3-2b所示的定向结果;若选择v1右侧的顶点并标记为v2,然后依次选择顶点进行标记,则最后可得到如图3-2c所示的定向结果。显然,两种不同的定向顺序得到了不同的定向结果。(www.daowen.com)

978-7-111-58625-8-Chapter03-2.jpg

图3-2 不同定向方式得到的定向结果

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

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈