Arborescence

Материал из WEGA
Версия от 18:18, 15 февраля 2011; Glk (обсуждение | вклад) (Новая страница: «'''Arborescence''' --- ориентированное дерево. This is a digraph <math>G</math> with a specified vertex <math>a</math> called a ''root'' such…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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.