monk

Представление информации в форме графа

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

Две вершины, соединенные ребром (дугой) называются смежными.

Вершины и рёбра графа могут характеризоваться некоторыми числовыми величинами. Например, может быть известна длина ребра или “стоимость прохождения” по нему. Такие характеристики называют весом, а граф называется взвешенным.

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

Пример. На рис. 1 представлены различные типы конфигураций локальных вычислительных сетей (ЛВС), являющиеся информационными моделями структур ЛВС, представленными в виде графов:

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

Рис. 1 Различные типы конфигураций локальных вычислительных сетей

Древовидная Полносвязная

Наиболее наглядно граф задаётся рисунком. Однако не все детали рисунка одинаково важны. В частности, несущественны геометрические свойства рёбер (длина, кривизна и так далее), форма вершин (точка, кружок, квадрат, овал и пр.) и взаимное расположение вершин на плоскости. Так, на рис. 2 представлены два изображения одного и того же графа.

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

Рис. 2 Различные изображения одного и того же графа

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

В форме графа удобно отображать взаимосвязи понятий, относящихся к одной области деятельности или познания.

Пример. Рассмотрите граф понятий темы “Четырёхугольники” из курса геометрии (рис. 3). Не правда ли, хорошая “шпаргалка”?

Рис. 3 Граф понятий темы “Четырёхугольники”

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

Пример. Сетевые графики строительства хорошо демонстрируют, какие работы могут выполняться одновременно, а какие требуют обязательного завершения предыдущих этапов. Анализируя такие графы, можно рассчитать время, необходимое для завершения всей работы, спланировать, сколько, когда и на какие работы направить специалистов и технику, определить наиболее “узкие” участки и уделить им особое внимание.

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

Пример. Графы, представленные на рис. 4 могут быть описаны, например, следующими способами.

Символическая запись:

а(l,2) в(1.4) c(2,4) d(3,5) е(4,5) f(3,4)

Табличная запись:

1

2

3

4

5

1

a

b

2

a

c

8

f

d

4

b

c

f

e

6

d

e

Рис. 2.9.5 Графы, имеющие одинаковые описания в виде таблицы и символической записи

Представление данных в форме дерева

Особым видом графа является дерево. Данная форма модели применяется тогда, когда элементы моделируемого объекта находятся в состоянии какого-либо подчинения и соподчинения, когда есть отношение иерархичности.

Пример. Модель управления предприятием (школой, театральным коллективом и т. д.) очень удобно представлять в виде дерева.

Пример. Вам хорошо известно понятие “родословное дерево” и вы можете изобразить в такой форме ваши родственные отношения.

Пример. Каталог файлов на диске, также как и библиотечный каталог — примеры информационных моделей в форме дерева.

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

Изображать построенное дерево отношений можно в любом направлении — это уже дело эстетического вкуса разработчика модели.

В научной и учебной деятельности с помощью деревьев часто представляют классификацию изучаемых объектов.

Классифицирование — распределение объектов по классам в зависимости от их общих признаков, фиксирующее закономерные связи между классами объектов в единой системе данной отрасли знания.

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

Классификация позволяет ориентироваться в многообразии объектов и является источником знания о них. Очень важен выбор основания классификации — то есть признака. на основании которого объекты разбиваются на классы. Выбор разных оснований приводит к разным классификациям.

Пример. На рис. 5 вы видите классификацию, предложенную Григорием Великим, которая призвана была показать, что человек имеет что-то общее со всеми видами существующих в мире вещей, и поэтому его справедливо называют “вселенной в миниатюре”. Обратите внимание, что объекты здесь разбиваются всегда на два класса. Такая классификация носит название дихотомической.

Рис. 5. Классификация “того, что есть” Григория Великого

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

Рис. 6 Классификация принтеров

Пример. Важным видом исторических классификаций является построение родословных или генеалогических деревьев. Они бывают самого разного вида: с указанием только прямых потомков (рис. 7); с включением жён (мужей) и их родственников и др.

Рис. 2.9.8. Родословное дерево великих и удельных князей Владимирских и Московских. XIII-XIV века (фрагмент)

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

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

Выводы:

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

Эти точки называют вершинами графа.

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

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

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

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

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

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

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

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

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

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

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

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

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

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