Связи между классами объектов

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

Каждая связь обладает определенными характеристиками. Одна их характеристик – опциональность связи (минимальное кардинальное число). Это бизнес-правило, указывающее должна ли связь существовать для каждого объекта класса объектов (обязательная связь) или это не требуется (необязательная связь). Еще одна важная характеристика связи – мощность (максимальное кардинальное число). Это бизнес правило, указывающее сколько таких связей существует – одна и только одна, или много. Если обнаружена связь, которая имеет мощность «ноль», эта связь необязательная.

Кроме того, каждая сторона связи имеет имя. Это описание правил бизнеса. Например: «соответствует», «относится к». Имена часто составляют пары: «основан на» – «является основой для»; «приобретается у» – «поставляется»; «отвечает за» – «находится под ответственностью». Имя имеет большое значение, оно показывает, насколько хорошо понята взаимосвязь информации.

Таблица 2.3

Правило чтения связи

Часть 1	Каждый (ая, ое)
Часть 2	Имя первого класса объектов
Часть 3	Опциональность связи (должна быть или может быть)
Часть 4	Имя связи
Часть 5	Мощность связи (одна или много)
Часть 6	Имя второго класса объектов

Увидев связь, необходимо убедиться в том, что она имеет смысл. Для этого её необходимо проговорить как обычное предложение в обе стороны (любая связь двусторонняя), используя правило произношения связи (табл. 2.3).

2.2.2. Элементы теории графов: понятия графа, пути, контуры, цепи и циклы, матрица инциденций; основы теории сетей

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

Графом G называется совокупность двух множеств V (точек) и E (линий), между элементами которых определено отношение инцидентности (связности или соседства), причем каждый элемент e  E, инцидентен ровно двум элементам v₁, v₂  V, необязательно различным, которые называются смежными. Элементы множества V называются вершинами графа G, элементы множества E – его ребрами. Граф связен, если любые его две вершины можно соединить цепью.

Если N – множество узлов, то любое подмножество N × N является обобщенным графом G. Если в парах подмножества N × N имеет значение порядок, то граф G является ориентированным.

На рис. 2.2 показаны разные типы графов. Обратите внимание на то, что граф не обязательно должен быть связным. Если задаться условием, что петли не допускаются, т.е. в каждой паре должны присутствовать разные узлы, то такой граф называется обыкновенным. Если на графе не допускаются не только петли, но и циклы (т.е. последовательность связей, в которой начальный и конечный узлы совпадают), то такой граф называется лесом.

Рис. 2.2. Некоторые виды графов: а) обыкновенный граф; 6) связный граф с петлей; в) обыкновенный ориентированный граф – дерево

Если G – обыкновенный граф, в котором имеется n узлов и n – 1 связей, и отсутствуют циклы, то такой граф является деревом. Иными словами, дерево – это связный лес. Обычно один из узлов дерева является его корнем. Остальные узлы образуют ветвящуюся структуру «наследников» корневого узла, в которой отсутствуют циклы. Узлы, не имеющие наследников, являются терминальными или «листьями» дерева, а остальные узлы называются промежуточными (нетерминальными).

В теории графов сетью называется взвешенный ориентированный граф, т.е. граф, в котором каждой связи сопоставлено определенное число. Обычно этими числами оценивается «стоимость» пути вдоль этой связи или длина связи, как на карте дорог. В каждом конкретном случае применения графа как формального средства описания проблемы эти числа могут трактоваться по-своему.

Если L – это множество взвешенных связей, a N, как и ранее, множество узлов, то сеть – это любое подмножество N × L × N, в котором имеет значение порядок в триадах.

Связи в сети практически всегда являются ориентированными, поскольку отношения, представленные взвешенными связями, не должны быть симметричными.

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

Опишем традиционную геометрическую интерпретацию графа.

Пусть G = [A, B] – некоторый граф и A = {a₁, a₂, …, a_p}, B = {b₁, b₂, …, b_q}.

Фиксируем на плоскости произвольным образом p точек и произвольным образом дадим им в качестве имен имена вершин данного графа; в итоге на плоскости возникнут точки, обозначенные как a₁, a₂, …, a_p. Затем для каждой пары точек a_i, a_j таких, что (a_i, a_j)  B, проведем отрезок прямой, соединяющий точки a_i, a_j. В результате таких действий возникнет некоторый рисунок, который и называется геометрической интерпретацией графа. Заметим, что одному и тому же графу соответствует много рисунков, которые могут быть его геометрическими интерпретациями.

Пусть теперь G₁ = [А₁, В₁], G₂ = [А₂, В₂] – два графа таких, что A₁  A₂ и B₁  B₂, тогда говорят, что G₁ является подграфом графа G₂.

Если в некотором графе G = [A, B] множество ребер B таково, что B = V(A), то граф называется полным. Заметим, что если в полном графе число вершин равно p, то число ребер равно p(p – 1)/2.

Мажоранта – некоторая вершина z  X (множество вершин), которая следует за всеми вершинами подмножества Y множества Х. Миноранта – некоторая вершина z  X (множество вершин), которая предшествует всем вершинам подмножества Y множества Х.

Для неориентированного графа степень вершины – число ребер, которые инцидентны вершине x. Для ориентированного графа степень вершины – множество дуг, исходящих (входящих) из (и) вершины – полустепень исхода (захода).

Цепь − незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны.

Цикл − замкнутая цепь (в неориентированном графе).

Контур − замкнутый путь (в ориентированном графе).

Простой путь (цепь) − путь (цепь, цикл, контур), в котором ни одна дуга/ребро не встречается дважды.

Простой цикл (контур) − цикл (контур), в котором все вершины попарно различны.

Гамильтонова цепь (путь, цикл, контур) − простая цепь (путь, цикл, контур), проходящая через все вершины.

Эйлерова цепь (путь, цикл, контур) − цепь (путь, цикл, контур), содержащая все ребра (дуги) графа по одному разу.

Длина маршрута (пути) − число ребер в маршруте (дуг в пути).