Информационные модели на графах

Наглядным средством представления состава и струк­туры системы является граф. Граф состоит из вершин, связанных линиями. Линия со стрел­кой называется дугой; линия ненаправленная (без стрелки) называется ребром. Линия, выходящая из неко­торой вершины и входящая в нее же, называется петлей. Вершины могут изображаться овалами, прямоугольниками и т. д.

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

Сети

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

Например, граф, отражающий отношение «переписы­ваются» между объектами класса «дети», может выгля­деть, как показано на рис. 2.28.

Рис. 2.28

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

Путь по вершинам и ребрам графа, включающий лю­бое ребро графа не более одного раза, называется цепью.

Пример цепи: Юра — Аня — Витя — Коля.

Цепь, начальная и конечная вершины которой совпа­дают, называется циклом.

Пример цикла: Аня — Коля — Витя — Аня.

Иначе выглядит граф, отражающий отношение «пи­шет письма» между теми же объектами класса «дети». Линии со стрелками (дуги) придают ему совершенно иной смысл (рис. 2.29).

Рис. 2.29

Граф называется ориентированным, если его верши­ны соединены дугами.

 Приведите примеры цепи и цикла в графе на рис. 2.29.

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

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

Рис. 2.30

 Назовите пути и циклы в графе на рис. 2.30.

Граф с циклом называется сетью.

На рис. 2.31 в виде графа представлена информацион­ная модель сказки про Царевну-лягушку.

Рис. 2.31

Вершины этого графа — персонажи и предметы из сказки, дуги — связи между ними. В отличие от предыду­щих примеров, здесь все связи различны. Поэтому они подписываются рядом с соответствующими дугами.

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