В представленном выше примере после
В представленном выше примере после введения всех транзитивных связей матрица следования S примет вид, представленный на рисунке 7.6)рисунке 7.6 (введённые транзитивные связи выделены курсивом).
Рис. 7.6. Матрица следования с транзитивными связями
С помощью введения транзитивных связей в нетреугольной матрице следования устанавливается наличие контуров в графе G. О наличии контуров свидетельствуют появившиеся ненулевые диагональные элементы, указывающие на связь вида a
Например, пусть задан граф G на рис. 7.7.
Рис. 7.7. Граф алгоритма и матрица следования
После первого шага преобразования S принимает вид, показанный на рис. 7.8.
Рис. 7.8. Первый шаг обнаружения контура
После второго шага преобразования S принимает вид, показанный на рис. 7.9.
Рис. 7.9. Обнаружение контура
Т.к. на главной диагонали матрицы появились единицы, то граф G содержит циклы (контуры). Из рисунка графа виден цикл 2
Определение 6. Работы a и b будем называть взаимно независимыми, если в матрице следования S выполняется условие (a, b) = (b, a) = 0.
Определение 7. Работы {ai}, i = 1, ... , s, образуют полное множество взаимно независимых работ (ПМВНР), если для любой работы j
Например, для графа G, представленного на рис. 7.1, после введения транзитивных связей, что учтено в матрице следования на рис. 7.6, можно установить следующие ПМВНР: {1,2}, {2,3,4}, {3,4,5}, {2,3,6}, {3,5,6,7}, {8}.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий