Arborescence

Материал из WEGA
Перейти к навигации Перейти к поиску

Arborescenceориентированное дерево.

This is a digraph [math]\displaystyle{ \,G }[/math] with a specified vertex [math]\displaystyle{ \,a }[/math] called a root such that each point [math]\displaystyle{ x\neq a }[/math] has indegree 1 and there is a unique [math]\displaystyle{ \,(a,x) }[/math]-path for each point [math]\displaystyle{ \,x }[/math]. Arborescence can be obtained by specifying a vertex [math]\displaystyle{ \,a }[/math] of a tree and then orienting each edge [math]\displaystyle{ \,e }[/math] such that the unique path connecting [math]\displaystyle{ \,a }[/math] to [math]\displaystyle{ \,e }[/math] ends at the tail of [math]\displaystyle{ \,e }[/math]. An inverse arborescence is a digraph obtained from an arborescence by inverting its edges.