有向生成树

有向生成树（directed spanning tree），工学-控制科学与工程-网络系统控制分析与设计，有向图的一种特殊情形，其中一种情形为有向生成树。有向生成树需要满足以下3个条件：①仅含有一个没有父顶点的顶点，称之为全局可达顶点；②其他所有顶点有且仅有一个父顶点；③从全局可达顶点出发到图中所有其他顶点都存在有向路径。如果有向图的生成子图是一个有向树，那么该子图称为图的有向生成树。如果有向图是强连通图，那么有向图存在有向生成树，但有向图存在有向生成树却不一定是强连通图。因此，一个有向图含有有向生成树比它是强连通的条件更弱一些。