有向图

在数学中，更具体地说，在图论中，有向图（或二维图）是由一组顶点组成的图，这些顶点由有向边连接，通常称为弧。

在形式上，一个有向图是一个有序的对G=（V，A），其中V是一个集合，其元素被称为顶点、节点或点；A是一组有序的顶点对，被称为弧、有向边（有时仅仅是边，相应的集合被称为E而不是A）、箭头或有向线。它与普通图或无向图不同，因为后者是以无序的顶点对来定义的，通常被称为边、链接或线。

上述定义不允许有向图有多个具有相同源节点和目标节点的箭头，但有些作者考虑了一个更广泛的定义，允许有向图有这样的多个弧（即他们允许弧集是一个多集）。有时这些实体被称为有向多图（或多图）。

另一方面，上述定义允许有向图有循环（即直接连接节点与自身的弧），但有些作者考虑采用较窄的定义，不允许有向图有循环。无循环的有向图可称为简单有向图，而有循环的有向图可称为循环图（见有向图的类型一节）。

有向图的类型子类对称有向图是指所有的边都出现了两次，每个方向都有一个（也就是说，对于每个属于二维图的箭头，相应的反向箭头也属于它）。(这样的边有时被称为双定向，这样的图有时也被称为双定向，但这与双定向图的含义相冲突。)

简单有向图是指没有循环（直接将顶点连接到自己的箭头）和没有具有相同源节点和目标节点的多个箭头的有向图。如前所述，在有多个箭头的情况下，该实体通常被称为有向多图。

有些作者把带有循环的数字图描述为循环图。完整的有向图是简单的有向图，其中每一对顶点由一对对称的有向弧连接（它等同于无向完整图，其边由一对反向弧代替）。因此，一个完整的数字图是对称的。

半完整的多部分数字图是简单的数字图，其中顶点集被划分为不同的集合，对于不同集合中的每一对顶点x和y，x和y之间有一个弧。

半完整的数字图是简单的数字图，其中每一对顶点之间有一个弧。

每个半完全数位图都是一个半完全的多分位数位图，以一种微妙的方式，每个顶点构成分区的一个集合。

准跨度数位图是简单数位图，对于每个不同顶点的三重x，y，z，有从x到y和从y到z的弧，x和z之间有一条弧，注意x和z之间可以只有一条弧，或者两个方向相反的弧。

一个半完整的数位图是一个准跨度数位图。准遍历图有一些扩展，叫做k-准遍历图。有向图是没有对向边的有向图（即（x，y）和（y，x）中最多有一条可能是图的箭头）。

由此可见，当且仅当一个有向图没有2-循环时，它就是一个有向图。

锦标赛是通过为无定向完整图的每条边选择一个方向而得到的定向图。请注意，锦标赛是一个半完全图。如果一个有向图没有有向循环，那么它就是无循环的。

这种图的通常名称是有向无环图（DAG）。多树是指从同一起始顶点到同一终止顶点没有两条不同的有向路径的DAG。有向树或多树是通过对树（连接的、无环的无向图）的边进行定向形成的DAG。

有根树是定向树，其中底层无向树的所有边要么远离根，要么指向根（它们分别被称为树冠或外树，以及内树。具有补充属性的图加权有向图（也称为有向网络）是（简单的）有向图，其箭头被分配了权重，类似于加权图（也称为无向网络或加权网络）。

流网络是加权有向图，其中有两个节点被区分为源和汇。有根有向图（也称为流图）是有根图，其中一个顶点被区分为根。控制流图是有根图，在计算机科学中作为一种代表。