Иерархические системы и деревья

Виды графов

Граф, в котором все связи изображены дугами, называется ориентированным графом.

На рис. 3. изображен ориентированный граф, содержащий информацию о мужском составе некоторой семьи.

Рис.3

Здесь дуги обозначают связь «быть отцом», т. е. Лев является отцом для Андрея и Петра, Андрей — отец Алексея, а Петр — отец Михаила и Дмитрия. У каждого человека может быть только один отец, но несколько детей. Поэтому в каждую вершину графа может входить только одна стрелка (дуга), а выходить — несколько. Такой граф представляет собой генеалогическое дерево.

Деревом называют граф, в котором нет петель, т. е. связанных по замкнутой линии вершин.

Граф на рис. 1 нельзя назвать деревом. В нем очевидны петли: Дачи — Подгорная — Бобры — Елово — Дачи и пр. Если бы, например, между Елово и Бобрами, Елово и Озёрной не было дорог, то такой граф был бы деревом.

У дерева на рис. 3 вершина «Лев» является корнем. От корня идут ветви, по которым можно добраться до любой другой вершины дерева только по одному пути. Конечные вершины каждой ветви называются листьями.

Название «дерево» выбрано не случайно, потому что очевидно некоторое внешнее сходство с деревом-растением. Правда, дерево-граф выглядит перевернутым, но это связано с нашей привычкой писать сверху вниз, а не наоборот. А строить дерево удобно, начиная с корня.

Система, информационная модель которой представляется в виде дерева, называется иерархической системой.

Как правило, иерархическую структуру имеют общественные системы, между частями которых установлены отношения подчиненности (например: директор — начальник цеха — начальник участка — бригадир — рабочий); системы, между частями которых существуют отношения вхождения одних в другие (например: федерация, республика, область, город, район). На рис. 4 вы видите «географическое дерево». Его корнем является вершина «Планета Земля», листьями — города.

Рис. 4

Вершины дерева на рис. 4 четко разделены на пять уровней. Дерево на рис. 4 имеет три уровня.

Для дерева выполняется правило: вершины верхнего уровня связаны с вершинами нижнего уровня как «один ко многим». Один континент содержит множество стран, одна страна — множество регионов, а не наоборот.

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

Дата добавления: 2017-02-01