有向图 - The mini wiki

作为图论中最基本的概念之一，连通图基于连通的概念。在一个无向图G中，若从顶点

v

i

{\displaystyle v_{i}}

到顶点

v

j

{\displaystyle v_{j}}

有路径相连，则称

v

i

{\displaystyle v_{i}}

和

v

j

{\displaystyle v_{j}}

是连通的。如果G是有向图，那么连接

v

i

{\displaystyle v_{i}}

和

v

j

{\displaystyle v_{j}}

的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。图的连通性是图的基本性质。连通度是指为了让图分解成孤立的子图所要删除的顶点数的最小值。连通度是刻画网络的一个重要指标。

在数学中，更确切地说，在图论中，一个顶点或节点是构成图的基本单位：一个无向图包括一个顶点的集合和一个边的集合，而一个有向图包括一个顶点的集合和一个弧的集合。在一个图的示意图中，一个顶点通常表示为一个带标号的圆形，而一条边表示为连接两个顶点的一条直线或一个箭头。

在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该顶点，则这个图是一个有向无环图。

在数学中，更确切地说，在图论中，一个顶点或节点是构成图的基本单位：一个无向图包括一个顶点的集合和一个边的集合，而一个有向图包括一个顶点的集合和一个弧的集合。在一个图的示意图中，一个顶点通常表示为一个带标号的圆形，而一条边表示为连接两个顶点的一条直线或一个箭头。

在图论中，去掉其中所有边能使一张网络流图不再连通图的边集称为图的割，一张图上最小的割称为最小割。与最小割相关的问题称最小割问题，其变体包括带边权、有向图、包含源点与汇点，以及将原网络分为多于两个子图等问题。其中，带边权的最小割问题允许有负权边，可通过对所有边权取相反数简单地转化为最大流问题求解。

在程序设计中，数据流程编程是一种编程范型，它将程序建模为数据在运算之间流动的有向图，从而实现了数据流程原理和架构。数据流程编程语言，共享了纯函数式语言的某些特征，比如单赋值，并且开发它们的动因，通常是为了向更适合数值处理的语言，增加函数式编程概念。

在有向图的数学理论中，如果一个图的每一个顶点都可从该图其他任意一点到达，则称该图是强连通的。在任意有向图中能够实现强连通的部分我们称其为强连通分量。判断一个图是否为强连通以及找到一个图强连通分量只需要线性时间。