Корневые и бескорневые деревья
Дерево называется корневым или заякоренным (rooted), если имеется особая вершина называемая корнем. У этой вершины нет предка, но она является обшим предком для всего дерева, а все вершины дерева в свою очередь являются потомками. Деревья a), b) и c) на рисунке являются корневыми.
Дерево в котором отражены лишь отношения между таксонами, но не указан один общий предок называется бескорневым или незаякоренным (unrooted). Пример такого дерева приведен на рисунке d) (в 6.2.).
Число дихотомических корневых деревьев для n висячих вершин можно определить по формуле:
(2n -3) !
Nr = ----------------
2n-2 (n-2) !
Число дихотомических бескорневых деревьев для n висячих вершин можно определить по формуле:
(2n -5) !
Nu = ----------------
2 n-3 (n-3) !
Число дихотомических бескорневых деревьев для n висячих вершин равно числу корневых деревьев для n-1 вершин. Число возможных деревьев увеличивается очень быстро, так при n=10 возможны уже 207025 бескорневых дерева и 34459425 корневых. Это делает невозможным построение филогенетического дерева путем простого перебора уже при сравнительно небольших значениях n.
Смотрите также:
