Arborescence

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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