描述单行道系统就不能用无向图,因为它不能指明各条路的方向。所谓有 向图实际上是在无向图的基础上进一步指定各条边的方向。在有向图中,顶点v 的出度是指由顶点v出发的有向边的条数,记做d(v);而入度则是指向顶点v 的有向边的条数,记做d(v)。此外也有顶点度的概念,它是该顶点的出度与入 度的和:d(v)=d+(v)+d(v)。 在有向图中,许多概念都可以通过无向图的相关概念加“有向”二字得到, 如有向边、有向途径、有向迹、有向路、有向圈,等等。有向图和无向图可以 相互转化:将一个无向图的每条边都规定方向后,即得到有向图,其称为原无向 图的一个定向图;将一个有向图的各条有向边的方向去掉,即得到一个无向图 其称为原有向图的基础图 有向图中也有一些概念不能由无向图通过简单地附加“有向”一词而得到 如,连通,有向图D说是连通的是指其基础图是连通的。如果D中任意两个顶点 都是可达的,则说有向图D是双向连通的(或叫强连通)。这里,顶点u可达顶 点v是指存在一条以u为起点、v为终点的有向路。这里的起点、终点不能互为 替换。有向图3-3就是连通的,但不是双向连通的,因为从任何顶点出发,都没 有到达顶点3的有向途径。不是双向连通的有向图可以分解成几个双向连通分 支。图3-3共有5个双向连通分支,分别用不同的颜色标出。 加权图与网络 般的加权图是指对图的每条边e赋予一个实数值W(e)。如架设连接各城 镇的交通路网,需考虑各段线路的修建费用;在运输网络中要考虑网络各段线路 的容量,等等。 图3-1-4一个交通路网 网络是一个这样的加权有向图,其指明了收点集和发点集,在图3-5中分别 用粉色和黄色标出。其余的顶点称为内点(绿色)。描述单行道系统就不能用无向图，因为它不能指明各条路的方向。所谓有 向图实际上是在无向图的基础上进一步指定各条边的方向。在有向图中，顶点 v 的出度是指由顶点 v 出发的有向边的条数，记做 d＋(v)；而入度则是指向顶点 v 的有向边的条数, 记做 d- (v)。此外也有顶点度的概念，它是该顶点的出度与入 度的和: d(v)=d＋(v)+d- (v)。 在有向图中，许多概念都可以通过无向图的相关概念加“有向”二字得到， 如 有向边、有向途径、有向迹、有向路、有向圈，等等。有向图和无向图可以 相互转化：将一个无向图的每条边都规定方向后，即得到有向图，其称为原无向 图的一个定向图；将一个有向图的各条有向边的方向去掉，即得到一个无向图， 其称为原有向图的基础图。 有向图中也有一些概念不能由无向图通过简单地附加“有向”一词而得到。 如，连通，有向图 D 说是连通的是指其基础图是连通的。如果 D 中任意两个顶点 都是可达的，则说有向图 D 是双向连通的（或叫强连通）。这里，顶点 u 可达顶 点 v 是指存在一条以 u 为起点、v 为终点的有向路。这里的起点、终点不能互为 替换。有向图 3-3 就是连通的，但不是双向连通的，因为从任何顶点出发，都没 有到达顶点 3 的有向途径。不是双向连通的有向图可以分解成几个双向连通分 支。图 3-3 共有 5 个双向连通分支，分别用不同的颜色标出。 z 加权图与网络 一般的加权图是指对图的每条边 e 赋予一个实数值 W(e)。如架设连接各城 镇的交通路网，需考虑各段线路的修建费用；在运输网络中要考虑网络各段线路 的容量，等等。 图 3-1－4 一个交通路网 网络是一个这样的加权有向图，其指明了收点集和发点集，在图 3-5 中分别 用粉色和黄色标出。其余的顶点称为内点（绿色）。 6 6 2 3 7 2 3 1 3 6 8 3