Question

7.2.词汇和定义

现在我们已经看了一些图的示例，我们将更正式地定义图及其组件。我们已经从对树的讨论中知道了一些术语。

顶点 顶点（也称为“节点”）是图的基本部分。它可以有一个名称，我们将称为“键”。一个顶点也可能有额外的信息。我们将这个附加信息称为“有效载荷”。

边 边（也称为“弧”）是图的另一个基本部分。边连接两个顶点，以表明它们之间存在关系。边可以是单向的或双向的。如果图中的边都是单向的，我们称该图是有向图。上面显示的课程先决条件显然是一个图，因为你必须在其他课程之前学习一些课程。

权重 边可以被加权以示出从一个顶点到另一个顶点的成本。例如，在将一个城市连接到另一个城市的道路的图表中，边上的权重可以表示两个城市之间的距离。

利用这些定义，我们可以正式定义图。图可以由 G 表示，其中 $G =(V,E)$G=(V,E)。对于图 G，V 是一组顶点，E 是一组边。每个边是一个元组 $(v,w)$(v,w)，其中 $w,v \in V$w,v∈V。我们可以添加第三个组件到边元组来表示权重。子图 s 是边 e 和顶点 v 的集合，使得 $e \subset E$e⊂E 和 $v \subset V$v⊂V 。

Figure 2 展示了简单加权有向图的另一示例。正式地，我们可以将该图表示为六个顶点的集合：

$V = \left\{ V0,V1,V2,V3,V4,V5 \right\}$V={V0,V1,V2,V3,V4,V5}

和 9 条边的集合

$\begin{aligned} E = \left\{ \begin{array} {l}(v0,v1,5), (v1,v2,4), (v2,v3,9), (v3,v4,7), (v4,v0,1), \\ (v0,v5,2),(v5,v4,8),(v3,v5,3),(v5,v2,1) \end{array} \right\} \end{aligned}$​E={​(v0,v1,5),(v1,v2,4),(v2,v3,9),(v3,v4,7),(v4,v0,1),​(v0,v5,2),(v5,v4,8),(v3,v5,3),(v5,v2,1)​​}​​

Figure 2

figure 2 中的示例图有助于说明两个其他关键图形术语：

路径 图中的路径是由边连接的顶点序列。形式上，我们将定义一个路径为 $w_1, w_2, ..., w_n$w​1​​,w​2​​,...,w​n​​，使得$(wi, wi+1) \in E$(wi,wi+1)∈E, 当 $1 \leq i \leq n-1$1≤i≤n−1。未加权路径长度是路径中的边的数目，具体是 $n-1$n−1 。加权路径长度是路径中所有边的权重的总和。例如在 Figure 2中，从 V3 到 V1 的路径是顶点序列 $(V3,V4,V0,V1)$(V3,V4,V0,V1)。边是 $\{(v3,v4,7),(v4,v0,1),(v0,v1,5)\}${(v3,v4,7),(v4,v0,1),(v0,v1,5)}。

循环 有向图中的循环是在同一顶点开始和结束的路径。例如，在 Figure 2中，路径$(V5,V2,V3,V5)$(V5,V2,V3,V5)是一个循环。没有循环的图形称为非循环图形。没有循环的有向图称为有向无环图或 DAG 。我们将看到，如果问题可以表示为 DAG，我们可以解决几个重要的问题。