Arborescence: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Arborescence''' --- ориентированное дерево. This is a digraph <math>G</math> with a specified vertex <math>a</math> called a ''root'' such…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||
Текущая версия от 11:36, 5 декабря 2011
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.