Аноним

Arborescence: различия между версиями

Материал из WEGA
нет описания правки
(Новая страница: «'''Arborescence''' --- ориентированное дерево. This is a digraph <math>G</math> with a specified vertex <math>a</math> called a ''root'' such…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Arborescence''' --- ориентированное дерево.   
'''Arborescence''' — ''[[ориентированное дерево]].''  


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