Урок 12
Табличные модели

Содержание урока

Табличные модели. Таблицы типа «объект—свойство»

Табличные модели. Таблицы типа «объект—объект»

Табличные модели. Вопросы и задания

Системы, модели, графы. Понятие системы

Системы, модели, графы. Виды графов

Системы, модели, графы. Вопросы и задания

Дополнительный материал. Основы системологии

Системы, модели, графы. Виды графов

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

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

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

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

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

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

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

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

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

Как правило, иерархическую структуру имеют общественные системы, между частями которых установлены отношения подчиненности (например:

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

На рисунке 2.12 вы видите «географическое дерево». Его корнем является вершина «Планета Земля», листьями — города.

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

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

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

Сети

А теперь рассмотрим систему, изображенную в виде графа на рис. 2.13.

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

Здесь имеются два уровня вершин, но правило «один ко многим» не выполняется. Один ученик может посещать множество факультативов; один факультатив посещает множество учеников. Такой принцип связи называют «многие ко многим». Граф с такой структурой носит название сеть.

Элементы сети не всегда делятся по уровням. В сети возможно произвольное соединение элементов: каждый элемент может быть соединен с любым другим. Граф на рис. 2.9 — пример дорожной сети.