Необщие ребра в филогенетических деревьях: различия между версиями

Пусть e – ребро в филогенетическом дереве T. Удаление ребра e разбивает T на два поддерева. Метки листьев также разбиваются на два подмножества, соответствующих поддеревьям. Ребро e называется ребром, порождающим разбиение множества меток листьев. Пусть даны два филогенетических дерева T и T' с одним и тем же количеством листьев и одним и тем же множеством меток листьев. Ребро e дерева T является общим, если существует некоторое ребро e' в дереве T', такое, что ребра e и e' порождают одно и то же разбиение множества меток листьев в соответствующих деревьях. В противном случае ребро e является необщим. Отметим, что деревья T и T' имеют одно и то же число ребер, стало быть, число необщих ребер в T (относительно T') равно числу необщих ребер в T' (относительно T). Это число называется расстоянием в необщих ребрах между деревьями T и T0. Определим две задачи: