图论中的有向图

本节我们将学习有向图，但在此之前，我们需要先学习什么是图。只有这样，我们才能轻松理解有向图。

Graph

图是由非空边集和顶点集组成的。图也可以表示为点和线的图形表示。图中的两条线通过点连接。图的顶点用点表示，图的边用线表示。

两个顶点通过一条边连接。在图中，最少使用一条边来连接两个顶点。图可以表示为 G = (V, E)，其中顶点集由 V 表示，边集由 E 表示。在本节中，我们将学习有向图、有向图的例子等等。

有向图

如果有一个图的边带有方向，那么这种图就称为有向图。有向图还有一个名字，即有向图。有向图的每一条边都有一个特定的起点，也称为源点，以及一个特定的终点，也称为目标点。在绘制有向图时，我们将所有这些边画成箭头，这些箭头只沿一个方向排列（从源点到目标点）。现在，我们将通过下面的例子来理解有向图：

示例：此示例包含一个有向图，我们需要找出该图的边和顶点。

解答：在上图中，我们有 4 个顶点和 5 条边。该图的顶点集和边集如下所示：

V = {1, 2, 3, 4}

E = {(1 → 2), (3 → 2), (1 → 3), (4 → 3), (3 → 4)}

G = {1, 2, 3, 4}, {(1 → 2), (3 → 2), (1 → 3), (4 → 3), (3 → 4)}

一些重要定义

在学习有向图时，我们需要了解一些重要的定义，以便轻松理解有向图。这些定义描述如下：

1. 自环：自环可以描述为一条连接顶点到自身的边。
2. 平行边：如果有两条边，并且这两条边都连接到相同的有序顶点对，则称为平行边。
3. 入度：可以通过计算指向该顶点的总边数来计算顶点的入度。
4. 出度：可以通过计算从该顶点出发的总边数来计算顶点的出度。
5. 简单有向路径：如果在一个有向图中存在一条不包含重复顶点的路径，那么这种路径就称为简单有向路径。
6. 有向路径：如果在一个有向图中存在一条路径（顶点序列），该路径不包含重复的边，并且图的边从每个顶点指向路径中的下一个顶点，那么这种路径就称为有向路径。
7. 简单有向环：如果在一个有向图中存在一条路径，该路径不包含除起点和终点之外的重复顶点，那么这种路径就称为简单有向环。
8. 有向环：如果在一个有向图中存在一条路径（顶点序列），其中序列的起点和终点相同，那么我们可以称之为有向环。
9. 路径或环的长度：我们可以通过计算图中边的数量来计算任何环或路径的长度。
10. 有向无环图：如果一个有向图不包含任何有向环，那么我们称之为有向无环图。
11. 可达性：如果在一个有向图中存在从顶点 x 到顶点 y 的路径，那么这种顶点就称为可达顶点，这意味着在可达性情况下，我们可以从顶点 x 到达顶点 y。
12. DAG（有向无环图）：如果一个有向图中没有有向环，那么这种图就称为 DAG。
13. 强连通有向图：如果在一个有向图（有向图）中，从每个顶点到图中的所有其他顶点都存在一条有向路径，那么这种图就称为强连通有向图。
14. 不强连通：如果一个有向图包含一组强连通分量，那么这种图就称为不强连通有向图。为此，分量必须是极大的强连通子图。
15. 强连通顶点：如果存在两个顶点 x 和 y，它们是相互可达的，那么它们就称为强连通顶点。相互可达的顶点意味着必须存在一条有向路径，我们可以通过它从顶点 x 到达 y，并且存在一条有向路径，我们可以通过它从顶点 y 到达 x。

有向图的特点

在有向图领域有各种各样的特点，有助于区分有向图和无向图。下面显示了一些特点：

1. 有向边：在有向图中，每条边都有一个方向。这种类型的图用于显示顶点之间的一对一关系。
2. 环：有向图可能包含环。这意味着它可以包含起点和终点相同的路径。对于环，最少必须有一条边。通过环，可以轻松理解图中的反馈回路或其他模式。
3. 入度与出度：在有向图中，图中每个顶点的度量必须有两个不同的度量，即入度和出度。可以通过计算指向顶点的总边数来得到入度，可以通过计算从顶点出发的总边数来得到出度。
4. 路径和可达性：在有向图中，路径包含沿着边方向的顶点和边序列。通过路径，我们可以分析顶点之间的可达性。

有向图的应用

有向图在各个领域都有各种各样的应用，如下所示：

1. 社交网络：可以使用有向图轻松建模社交媒体。在这里，有向图的顶点用于表示社交媒体上的每个人，图的边用于表示他们之间的关系，如关注或好友关系。
2. 交通网络：可以使用有向图轻松建模交通系统。使用有向图的交通系统可以是机场、道路或地铁系统。在这里，有向图的顶点用于表示地点，图的边用于表示它们之间的连接。
3. 计算机网络：可以使用有向图轻松建模计算机网络。计算机网络可以是互联网。在这里，有向图的顶点用于表示路由器或计算机等设备，图的边用于表示它们之间的连接。
4. 项目管理：可以使用有向图轻松建模项目管理。在这里，有向图的顶点用于表示任务，图的边用于表示它们之间的依赖关系。

有向图的优点

有向图有很多优点，其中一些如下所示：

1. 复杂关系：通过有向图，我们可以轻松地对复杂关系进行建模。它在需要方向性的情况下很有用，例如交通系统或社交网络。
2. 分析：通过有向图，可以轻松地分析系统中的信息或信息流。这种分析有助于理解和优化系统的行为。
3. 依赖关系：通过有向图，可以轻松地显示模型之间的依赖关系。例如，在推荐系统或项目管理中可以使用。

有向图的缺点

有向图有很多优点，其中一些如下所示：

1. 更复杂：在有向图中，每条边都有方向。因此，有向图比无向图更复杂。
2. 更多处理能力：当我们尝试分析有向图时，它通常比无向图需要更多的处理能力，因为有向图在边上包含关联的方向。
3. 不直观：与无向图相比，有向图的使用不那么普遍。因此，对于一个人来说，理解和使用它们不太直观。

有向图的例子

有向图有很多例子，其中一些如下所示：

示例 1

此示例包含一个有向图，我们需要找出该图的边和顶点。

解答：在上图中，我们有 7 个顶点和 11 条边。该图的顶点集和边集如下所示：

V = {A, B, C, D, E, F, G}

E = {(E → C), (C → B), (B → D), (E → D), (D → B), (B → A), (A → B), (G → D), (G → F), (A → F), (F → A)}

G = {{A, B, C, D, E, F, G}, {(E → C), (C → B), (B → D), (E → D), (D → B), (B → A), (A → B), (G → D), (G → F), (A → F), (F → A)}}

示例 2

此示例包含一个有向图，我们需要找出该图的边和顶点。

解答：在上图中，我们有 4 个顶点和 5 条边。该图的顶点集和边集如下所示：

V = {1, 2, 3, 4}

E = {(1 → 2), (2 → 3), (3 → 1), (3 → 4), (2 → 4)}

G = {1, 2, 3, 4}, {(1 → 2), (2 → 3), (3 → 1), (3 → 4), (2 → 4)}

示例 3

此示例包含一个图，我们需要找出该图的边和顶点。

解答：上图中的边不包含箭头。所以，这个图不可能是个有向图，因为有向图的每条边都必须有箭头。所以，在这个图中，我们可以双向通行。但可以找出该图的边集和顶点集。

示例 4

此示例包含一个图，我们需要找出该图的边和顶点。

解答：在上图中，我们有 4 个顶点和 8 条边。该图还包含自环。该图的顶点集和边集如下所示：

V = {a, b, c, d}

E = {(a → b), (a → a), (b → b), (b → a), (c → d), (c → c), (d → d), (c → a)}

G = {a, b, c, d}, {(a → b), (a → a), (b → b), (b → a), (c → d), (c → c), (d → d), (c → a)}