Граф— совокупность точек, соединённых между собой линиями. Эти точки называют вершинами графа

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

Граф называется взвешенным, если вершины или рёбра (дуги) характеризуются некоторой дополнительной информацией — весом вершины или ребра (дуги).

Граф однозначно задан, если заданы множество его вершин, множество рёбер (дуг) и указано, какие вершины какими рёбрами соединены.

Формализация при построении графа включает в себя следующие этапы:

• выявление всех элементов объекта;

• определение характеристик элементов (названий, номеров, весов и т. п.);

• установление наличия и вида связей (односторонняя или двухсторонняя) между элементами;

• определение характеристик связей — весов рёбер и дуг;

• выбор формы изображения вершин и рёбер, ввод условных обозначений в случае необходимости;

• представление выделенных элементов и связей в графическом виде.

Для компьютерного моделирования более удобным является символическое и/или табличное задание графа.

Символическое задание графа — перечисление всех его рёбер с указанием вершин, которые они соединяют, либо перечисление всех вершин с указанием исходящих из них рёбер.

Дерево — особый вид графа, применяемый при моделировании объекта, элементы которого находятся в отношении иерархии (подчинения и соподчинения).

Корнем дерева называется вершина, соответствующая основному (центральному, главному, родовому) элементу моделируемого объекта. Листьями дерева называют вершины графа, у которых нет «подчинённых» вершин.

Формализация при построении дерева сводится к выявлению основного элемента рассматриваемого объекта (вершина нулевого уровня — корень дерева), элементов, которые находятся в непосредственном подчинении у основного элемента (вершины 1-го уровня), элементов, находящихся в непосредственном подчинении у вершин 1-го уровня (вершины 2-го уровня) и т. д.

Классификация — система соподчинённых понятий (классов объектов, явлений) в какой-либо отрасли знания, составленная на основе учёта общих признаков объектов и закономерных связей между ними. Представляется чаще всего в виде иерархического графа (дерева) или таблицы.

Реляционная (табличная), сетевая (графовая) и иерархическая (древовидная) модели являются основными для представления данных в базах данных.

Программные комплексы, которые позволяют создавать, обновлять, сохранять базы данных и обслуживать запросы пользователей к ним, называются соответственно реляционной, сетевой, иерархической системой управления базами данных (СУБД).

Большинство существующих автоматизированных баз данных являются базами данных реляционного типа.

Контрольные вопросы и задания

1. Что называется графом? Ориентированным графом?

2. Что называется вершинами графа? Рёбрами?

3. Какие рёбра и какие вершины графа называются смежными?

4. Какой граф называется деревом?

5. Какие системы объектов целесообразно и возможно представлять с помощью табличных моделей?

Дата добавления: 2014-01-11