АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

ОПРЕДЕЛЕНИЕ. Неориентированный связный граф, не имеющий петель, называется деревом, если он не содержит циклических ребер.

Прочитайте:
  1. I. Доход от прироста стоимости при реализации ценных бумаг (инвестор самостоятельно несет ответственность за определение и выплату налогов в бюджет Республики Казахстан)
  2. I. ОПРЕДЕЛЕНИЕ ОСНОВНЫХ ТЕРМИНОВ
  3. I. Определение СКФ по клиренсу креатинина
  4. II. Договорные отношения могущие влиять на определение управомоченного лица
  5. А. Определение группы крови стандартными изогемагглютинирующими сыворотками.
  6. Аборты. Определение, классифиация, диагностика и профилактика.
  7. Ангины: 1) определение, этиология и патогенез 2) классификация 3) патологическая анатомия и дифференциальная диагностика различных форм 4) местные осложнения 5) общие осложнения
  8. Антигены. Определение. Свойства. Виды.
  9. Асептика, антисептика. Определение понятий. Способы проведения.
  10. Б. Определение группы крови с помощью цоликлонов (моноклональных антител)

Неориентированный связный граф, не имеющий петель, называется деревом, если он не содержит циклических ребер.

 

Если граф D - это дерево и v - некоторая вершина в D, то D может быть представлен в виде корневого дерева с корнем v.

Изобразим вершину v, расположив её в первом ярусе. Вершины, соседние с v, поместим в первый ярус и соединим дугами с корнем. Вершины, соседние с вершинами первого яруса, отличные от корня, поместим во второй ярус и соединим с соседними с ними вершинами первого яруса.

Продолжаем описанный процесс до тех пор, пока все вершины D не окажутся распределенными по ярусам. Процесс распределения вершин D по ярусам заканчивается через конечное число шагов, так как D имеет конечное число вершин.

 

Та из двух соседних вершин корневого дерева, которая располагается в ярусе с меньшим номером, называется предком. Вторая из этих вершин называется потомком.

 

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

 

Корневое представление всякого дерева D обладает следующими свойствами:

1) в D имеются висячие вершины;

2) каждая внутренняя вершина корневого дерева является соседней с единственной вершиной предшествующего яруса.

Деревья имеют много различных приложений. Одно из них - представление структур арифметических выражений с помощью корневых деревьев. Это позволяет алгоритмизировать процесс вычисления значений произвольных выражений.

 

Например, арифметическое выражение (a + b) ´ (c - d)/(a - c) представляется в виде дерева, изображенного на рис. 5.15:

/

´ -

+ - a c

 

 

Дата добавления: 2015-09-27 | Просмотры: 494 | Нарушение авторских прав

При использовании материала ссылка на сайт medlec.org обязательна! (0.003 сек.)