第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一个定向使得到的混合图仍是强连通的。

证明：此定理的证明与罗宾斯定理的证明方法类似。