Данные, используемые в любой информационной модели, всегда определенным образом упорядочены, структурированы. Иначе можно сказать так: данные, на которых базируется информационная модель, представляют собой систему со всеми характерными признаками — элементным составом, структурой, назначением. Такие структурированные системы данных часто называют структурами данных. Исследуя некоторую реальную систему (объект моделирования), системный аналитик строит ее теоретическую модель. При этом в первую очередь он должен описать структуру данных.
Рассмотрим несколько часто используемых видов описания структур данных: графы, иерархические структуры (деревья) и таблицы.
Графы. Информация о некотором реальном объекте может быть представлена по-разному. В разговорной речи мы используем словесное (вербальное) представление информации.
Вот, например, словесное описание некоторой местности: «Наш район состоит из пяти поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино». По такому описанию довольно трудно представить себе эту местность, нелегко и запомнить описание. А представьте себе, что поселков не 5, а 25! Всё гораздо понятнее становится из схемы на рис. 1 (на ней поселки обозначены первыми буквами своих названий).
|
|
Рисунок 1. Неориентированный граф (сеть)
Это не карта местности. Здесь не выдержаны направления по сторонам света, не соблюден масштаб. На этой схеме отражен лишь факт существования пяти поселков и дорожной связи между ними. Такая схема называется графом.
Граф отображает элементный состав системы и структуру связей.
Составными частями графа являются вершины и ребра. Здесь вершины изображены кружками, обозначающими элементы системы, а ребра изображены линиями, показывающими связи (отношения) между элементами. Глядя на этот граф, легко понять структуру дорожной системы в данной местности.
Построенный граф позволяет, например, ответить на вопрос: через какие поселки надо проехать, чтобы добраться из Репкино в Мышкино. Видно, что есть два возможных пути; обозначим их так:
1)Р —К —Б —М;
2)Р —К —Д —Б —М.
Очевидно, первый путь более выгодный, потому что он короче. Однако если по какой-то причине дорога между К и Б окажется непроезжей (начнутся ремонтные работы или дорогу занесет снегом), то единственным остается второй путь. Граф на рисунке 1 еще называют сетью.
Для сети характерна возможность множества различных путей перемещения по ребрам между некоторыми парами вершин.
|
|
Для сетей также характерно наличие замкнутых путей, которые называются циклами. На рис. 1 имеется цикл: К - Д - Б - К.
Граф, изображенный на рис. 1, является неориентированным графом. На нем каждое ребро обозначает наличие дорожной связи между двумя пунктами. Но дорожная связь действует одинаково в обе стороны: если по дороге можно проехать от Б к М, то по ней же можно проехать и от М к Б. Такую связь еще называют симметричной.
А теперь рассмотрим другой пример графа — на рисунке 2.
Этот пример относится к медицине. Известно, что существуют четыре группы крови человека. Оказывается, что при переливании крови от одного человека к другому не все группы совместимы. Граф на рис. 2 показывает возможные варианты переливания крови.
Рисунок 2. Ориентированный граф
Группы крови обозначены вершинами графа с соответствующими номерами, а стрелки указывают на возможность переливания одной группы крови человеку с другой группой крови.
Связи между вершинами данного графа несимметричны и поэтому изображаются направленными линиями со стрелками. Такие линии принято называть дугами (в отличие от ребер неориентированных графов). Граф с такими свойствами называется ориентированным. Линия, выходящая и входящая в одну и ту же вершину, называется петлей. На рис. 2 присутствуют четыре такие петли.