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.

Текущая версия от 16:30, 23 октября 2018

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.