Канонический вид ИЛМ

Правила представления ИЛМ в каноническом виде кратко изложены в п. 4.3.1.7. Там же приведен пример использования неформального способа упорядочения ИнО по уровням иерархии. Хотя в рассматриваемом примере количество ИнО в ИЛМ мало, длина цепочек, составляющих последовательность ИнО, связанных отношениями типа “Один-ко-многим”, невелика и можно расположить ИнО по уровням иерархии, не прибегая к формальным способам, в учебных целях рассмотрим формальный способ.

Формальный подход основан на использовании матрицы смежности – квадратной матрицы, количество строк (и столбцов) которой равно количеству ИнО. Значения элементов матрицы Xij = 1 ( i – номер строки, j – номер столбца) определяются по формулам:

Xij = 1, если ИОi : Иоj = 1 : М,

Xij = 0, если ИОi : Иоj ¹ 1 : М.

Подсчитываются суммы элементов по столбцам. Равенство суммы нулю означает, что ИнО столбца выносится на текущий иерархический уровень. Для получения следующего уровня
иерархии удаляются строки и столбцы матрицы, соответствующие выделенным на текущий иерархический уровень ИнО. Этот процесс продолжается до тех пор, пока в итоговой строке получатся только нулевые суммы.

Другими словами, значение “1” в матрице смежности записывается в позиции на пересечении “строка-столбец” в том случае, если между ИнО, записанным в названии строки, и ИнО, имя которого указано в названии столбца, имеется связь “Один-ко-многим”. Если сумма по столбцу равна нулю, то этот столбец и строка с таким же именем вычеркиваются, а оставшиеся столбцы и строки образуют новую матрицу смежности. Вычеркнутые ИнО выносятся на нулевой уровень иерархии.

Ниже приведена исходная матрица смежности для рассматриваемого примера.

 

	ТТН	Отгрузка	ЦН	Сдача	Изделие	Цех	Склад
ТТН
Отгрузка
ЦН
Сдача
Изделие
Цех
Склад
Сумма по столбцу

В исходной матрице смежности нулевые суммы образовались в столбцах “ТТН”, “Цех” и “Склад”. Следовательно, в этой матрице вычеркиваются соответствующие им столбцы и строки, и на нулевой уровень иерархии выносятся ИнО с этими названиями. Теперь получим вторую матрицу смежности, образованную вычеркиванием строк и столбцов исходной матрицы.

Во второй матрице смежности нулевые суммы образовались в столбцах “ЦН” и “Изделие”. Следовательно, эти столбцы в ней вычеркиваются, а ИнО “ЦН” и “Изделие” выносятся на первый уровень.

 

 

	Отгрузка	ЦН	Сдача	Изделие
Отгрузка
ЦН
Сдача
Изделие
Сумма по столбцу

Вычеркиванием строк и столбцов второй матрицы получим третью матрицу смежности.

	Отгрузка	Сдача
Отгрузка
Сдача
Сумма по столбцу	0

Таким образом, на второй (и последний) уровень иерархии выносятся ИнО “Отгрузка” и “Сдача”. На рис. 4.14 представлена ИЛМ рассматриваемого примера в каноническом виде.

Рис. 4.14. ИЛМ ПО “Движение готовой продукции на складах”