有向图相关知识简介

一、有向图相关概念

1、特性

在有向图中，边是单向的，即每条边所连接的两个顶点都是一个有序对，它们的邻接性是单向的。

有向图是由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点

2、有向边

一条有向边由第一个顶点指出并指向第二个顶点。

3、出度

有向图中，一个顶点的出度为由该顶点指出的边的总数；

4、入度

有向图中，一个顶点的入度为指向该顶点的边的总数。

5、头尾

一条有向边的第一个顶点称为它的头，第二个顶点则被称为它的尾。

有向边可画为由头指向尾的一个箭头。

例如用 v → w 来表示有向图中一条由 v 指向 w 的边。

6、顶点关系

一般情况下，一幅有向图中的两个顶点的关系可能有 4 种：

（1）没有边相连；

（2）存在从 v 到 w 的边 v → w；

（3）存在从 w 到 v 的边 w → v；

（4）既存在 v → w 也存在 w → v，即双向的连接。

7、有向路径

有向图中， 有向路径由一系列顶点组成，对于其中的每个顶点都存在一条有向边，并从它指向序列中的下一个顶点。

当存在从 v 到 w 的有向路径时，称顶点 w 能够由顶点 v 达到。

在有向图中由 v 能够到达 w 并不意味着由 w 也能到达 v。

8、有向环

有向环为一条至少含有一条边且起点和终点相同的有向路径。

9、简单有向环

简单有向环是一条（除了起点和终点必须相同之外）不含有重复的顶点和边的环。

10、长度

路径或者环的长度即为其中所包含的边数。

11、强连通与强连通分量

如果两个顶点 v 和 w 是互相可达的，则称它们为强连通的。也就是说，既存在一条从 v到 w 的有向路径，也存在一条从 w 到 v 的有向路径。

如果一幅有向图中的任意两个顶点都是强连通的，则称这幅有向图也是强连通的。

当且仅当两个顶点都在一个普通的有向环中，这两个顶点是强连通的

有向图中的强连通性也是一种顶点之间等价关系，有着以下性质。
（1）自反性：任意顶点 v 和自己都是强连通的。
（2）对称性：如果 v 和 w 是强连通的，那么 w 和 v 也是强连通的。
（3）传递性：如果 v 和 w 是强连通的且 w 和 x 也是强连通的，那么 v 和 x 也是强连通的。

作为一种等价关系，强连通性将所有顶点分为了一些等价类，每个等价类都是由相互均为强连通的顶点的最大子集组成的。这些子集被称为强连通分量

二、有向图可以解决的问题

1、单点可达性

给定一幅有向图和一个起点 s，回答“是否存在一条从 s 到达给定顶点 v 的有向路径？ ”等类似问题。

2、多点可达性

给定一幅有向图和顶点的集合，回答“是否存在一条从集合中的任意顶点到达给定顶点 v 的有向路径？”等类似问题。

3、单点有向路径

给定一幅有向图和一个起点 s，回答“从 s 到给定目的顶点 v 是否存在一条有向路径？如果有，找出这条路径。”等类似问题。

4、单点最短有向路径

给定一幅有向图和一个起点 s，回答“从 s 到给定目的顶点 v 是否存在一条有向路径？如果有，找出其中最短的那条（所含边数最少）。”等类似问题。

5、优先级限制下的调度问题

给定一组需要完成的任务，以及一组关于任务完成的先后次序的优先级限制。在满足限制条件的前提下应该如何安排并完成所有任务？

6、拓扑排序

给定一幅有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素（或者说明无法做到这一点）

7、有向环检测

给定的有向图中包含有向环吗？如果有，按照路径的方向从某个顶点并返回自己来找到环上的所有顶点。

有向无环图（ DAG）就是一幅不含有向环的有向图。

当且仅当一幅有向图是无环图时它才能进行拓扑排序。

原文地址：https://blog.csdn.net/well_fly/article/details/143062880

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！