Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kodomo.cmm.msu.ru/FBB/year_04/doc/term3/Help11.html
Дата изменения: Mon Nov 14 20:15:14 2005
Дата индексирования: Sat Dec 22 07:17:19 2007
Кодировка: Windows-1251
Task 11 (Help)

Подсказки к заданию 11.

Способ описания топологии бескорневого дерева (упр. I.3).

Любая ветвь делит листья (внешние вершины) дерева на 2 группы: листья первой группы находятся по одну сторону данной ветви, а второй — по другую стороной ветви. Например, в дереве 
         +----- F
         |
   +-----+   +-- A
   |     |   |
   |     +---+
   |         |
   |         +-- B
   |  +--- C
   |  |
   +--+    +--- D
      |    |
      +----+
           |
           +--- E
по одну сторону красной ветви лежат листья A и B, а по другую — C, D, E и F. Будем записывать это так: 
    {A,B} | {C,D,E,F}
Тем самым ветвь описывается как разбиение множества листьев на два непересекающихся подмножества.

Описав подобным образом все внутренние ветви дерева, Вы получите описание топологии бескорневого дерева. Порядок перечисления вершин по одну сторону ветви не имеет значения.

Очевидно также, что внешние ветви (те, что соединяют листья с ближайшими узлами) будут одинаковы в деревьях любой топологии, имеющих данный набор листьев: ветвь {A} | {Х1,Х2,...} будет присутствовать во всех деревьях, где есть лист А. Поэтому описывают только внутренние ветви.

Чаще, впрочем, ветви бескорневого дерева описывают следующим образом: вместо, например, {A,C} | {B,D,E,F} пишут: 

  A B C D E F
  . * . * * *
Такая форма записи позволяет описать все ветви дерева в виде одной таблички.
 

Способы изображения деревьев

Кладограммы отображают только общую топологию дерева, эволюционные расстояния игнорируются (могут остаться в виде подписей).

Филограммы имеют длины ребер, пропорциональные эволюционным расстояниям.

Для простоты отображения дерева (например, в текстовом формате) часто используют прямоугольные кладо- или филограммы.
При этом ребра изломлены под прямым углом. Внимание: место излома — это не узел!

При отображении дерева в текстовом формате традиционно принято:

Пример: 
   +------------- Seq1
   |
   |
  -1
   |  +------- Seq2
   |  |
   +--2
      |
      +----------- Seq3
Впрочем, нередко узлы вместо чисел помечаются тоже знаком "+". Вместо знака "|" для "рисования" вертикальных частей ребер иногда используется знак "!".