Английская Википедия:Arborescence (graph theory)

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Short description

In graph theory, an arborescence is a directed graph having a distinguished vertex Шаблон:Mvar (called the root) such that, for any other vertex Шаблон:Mvar, there is exactly one directed path from Шаблон:Mvar to Шаблон:Mvar.[1] An arborescence is thus the directed-graph form of a rooted tree, understood here as an undirected graph.[2][3] An arborescence is also a directed rooted tree in which all edges point away from the root; a number of other equivalent characterizations exist.[4][5]

Every arborescence is a directed acyclic graph (DAG), but not every DAG is an arborescence.

Definition

The term arborescence comes from French.[6] Some authors object to it on grounds that it is cumbersome to spell.[7] There is a large number of synonyms for arborescence in graph theory, including directed rooted tree,[3][7] out-arborescence,[8] out-tree,[9] and even branching being used to denote the same concept.[9] Rooted tree itself has been defined by some authors as a directed graph.[10][11][12]

Further definitions

Furthermore, some authors define an arborescence to be a spanning directed tree of a given digraph.[12][13] The same can be said about some of its synonyms, especially branching.[13] Other authors use branching to denote a forest of arborescences, with the latter notion defined in broader sense given at beginning of this article,[14][15] but a variation with both notions of the spanning flavor is also encountered.[12]

It's also possible to define a useful notion by reversing all the edges of an arborescence, i.e. making them all point in the direction of the root rather than away from it. Such digraphs are also designated by a variety of terms, such as in-tree[16] or anti-arborescence.[17] W. T. Tutte distinguishes between the two cases by using the phrases arborescence diverging from [some root] and arborescence converging to [some root].[18]

The number of rooted trees (or arborescences) with n nodes is given by the sequence:

0, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, ... Шаблон:OEIS.

See also

References

Шаблон:Reflist

External links

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite web
  2. ↑ Шаблон:Cite journal
  3. ↑ 3,0 3,1 Шаблон:Cite book
  4. ↑ Шаблон:Cite book
  5. ↑ Шаблон:Cite book
  6. ↑ Шаблон:Cite book
  7. ↑ 7,0 7,1 Шаблон:Cite book
  8. ↑ Шаблон:Cite book
  9. ↑ 9,0 9,1 Шаблон:Cite book
  10. ↑ Шаблон:Cite book
  11. ↑ Шаблон:Cite book
  12. ↑ 12,0 12,1 12,2 Шаблон:Cite book
  13. ↑ 13,0 13,1 Шаблон:Cite book
  14. ↑ Шаблон:Cite book
  15. ↑ Шаблон:Cite book
  16. ↑ Шаблон:Cite book
  17. ↑ Шаблон:Cite book
  18. ↑ Шаблон:Citation
Источник — http://wikihandbk.com/ruwiki/index.php?title=Английская_Википедия:Arborescence_(graph_theory)&oldid=13224707