Введение в информационные системы. Брюхомицкий Ю.А. - 57 стр.

UptoLike

Составители:

Рубрика:

Отношения типа «один ко многим» носят иерархический характер и

отображаются древовидными структурами. Отношения типа «многие ко мно-

гим» носят более универсальный характер и отображаются структурами гра-

фов. Например, выпускники вуза поступают на работу в различные организа-

ции. В то же время каждая организация принимает специалистов из различных

вузов. Результирующая схема

отображает связь многих вузов со многими орга-

низациями и представляет собой пример отношения «многие ко многим» (рис.

5.1).

Рис. 5.1. Пример отношения «многие ко многим»

Граф общего вида состоит из множества вершин (узлов) V и множества

ребер Е, связывающих пары вершин, и обозначается G = (V, E). Если в

понятия

«вершина» и «ребро» вкладывать определенную смысловую нагрузку, то с по-

мощью графов можно получить способ представления данных. Например, вер-

шинам графа можно сопоставить определенные объекты, а ребрам – отношения

между объектами.

Граф, в котором порядок рассмотрения вершин не играет роли, называ-

ется неориентированным графом.

Если ребра графа связывают неравноправные вершины,

рассматривае-

мые в определенном порядке, то ребрам приписывают определенные направле-

ния. Такие ребра называются дугами, а содержащий их граф называется ориен-

тированным или орграфом, рис. 5.2, а.

Если пара вершин соединяется двумя и более числом дуг, то такие дуги

называют параллельными. При этом две дуги, одинаково направленные по от-

ношению к

данной вершине, называют строго параллельными, а различно на-

правленные – нестрого параллельными. Нестрого параллельные дуги могут

быть заменены ребром. Если в графе произвести все подобные замены, придем

к смешанному графу, который содержит как ребра, так и дуги, рис. 5.2, б.

ВУЗ 1 ВУЗ 2 ВУЗ 3

Предприятие 1 Предприятие 2 Предприятие 3 Предприятие 4