Матрица инциденций для системы без циклов

Примечание. Единица в скобках может быть опущена, так как ее наличие определяется свойством транзитивности.

Таким образом, мы получили систему. Назовем ее условно «инвестиционной системой», так как каждому этапу проекта соответствует определенная доля инвестиций. Требуется разбить множество этапов на группы по степени проявления отношения R, т.е. по порядку следования. Для выделения уровней порядка применяется алгоритм ранжирования.

Шаг 1. Определим вектор-строку A ₀, равную сумме строк исходной матрицы. Напомним, что матрица является объединением своих строк-векторов, поэтому сложение строк осуществляется покомпонентно. Имеем A ₀ = (0 0 1 1 1 1 1 1 2 2 2 1 3 5). Нули в строке А ₀ соответствуют элементам, которым не предшествуют никакие другие элементы. В нашем случае это элементы x ₁, x ₂. Они образуют первый порядковый уровень: { x ₁, x ₂} – N ₀ (1-й порядковый уровень).

Шаг 2. Преобразуем строку А ₀ следующим образом:

а) нули заменим знаком «крест» ´; б) исключим из строки значения, соответствующие «нулевым» операциям, выделенным на шаге 1, т.е. в нашем случае операциям x ₁ и x _2. В итоге преобразования получим строку А ₁: А ₁ = (´ ´ 0 0 0 1 0 1 1 2 2 1 3 4) Новые нули в строке А ₁ соответствуют элементам x ₃, x ₄, x ₅, x _7, которые образуют 2-й порядковый уровень: { x ₃, x ₄, x ₅, x ₇} – N ₁ (2-й порядковый уровень).

Шаг 3. Действуя аналогично шагу 2, преобразуем строку А ₁ и получаем строку А ₂: А ₂ = (´ ´ ´ ´ ´ 0 ´ 0 1 1 1 1 2 4). Аналогично запишем { x ₆, x ₈} – N ₂ (3-й порядковый уровень).

Шаг 4. Повторяя шаг 2, получаем А ₃ = (´ ´ ´ ´ ´ ´ ´ ´ 0 1 1 1 1 4). { x ₉} – N ₃ (4-й порядковый уровень).

Шаг 5. А ₄ = (´ ´ ´ ´ ´ ´ ´ ´ ´ 0 0 0 0 4). { x ₁₀, x ₁₁, x ₁₂, x ₁₃} – N ₄ (5-й порядковый уровень).

Шаг 6. А ₅ = (´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ 0). { x ₁₄} – N ₅ (6-й порядковый уровень).

Таким образом, структура системы состоит из отдельных элементов и шести порядковых уровней, объединяющих группы элементов по степени проявления отношения R, т.е. по порядку следования.

Рассмотрим теперь систему с циклами, имеющую более сложную структуру. Отметим, что для использования алгоритма ранжирования, изложенного выше, необходимо появление новых нулей на каждом шаге. Если нули отсутствуют в первой или какой-то из последующих строк, то это является свидетельством, что система содержит циклы, т.е. циклические связи некоторых элементов между собой. Говорят, что два элемента x_i и x_j связаны циклом, если существует путь из x_i в x_j и обратно. Путь понимается здесь как связь элементов через отношение R между ними. Цикл может быть простым x_i → x_j → x_i, составным x_i → x_k → x_m →…→ x_n → x_i или автоциклом x_i → x_i → x_i. Простой цикл будем обозначать x_i ↔ x_j, составной x_i ← - → x_j, автоцикл x_i ↔ x_i.

Конкретизируем условия задачи. Пусть для определенности элементами множества Х являются дефекты продукции Х = { х ₁, х ₂,..., х ₈}. Зададим отношение R «Дефект x_i не менее значим, чем дефект x_j». Назовем полученную систему условно «диагностической системой». Задача состоит в разбиении множества Х на группы по степени проявления отношения R, т.е. по степени значимости. Матрица инциденций, полученная по результатам контроля продукции, представлена в табл. 7.

Таблица 7