Методы и алгоритмы принятия решений в управлении учебным процессом в условиях неопределенности. Найханова Л.В - 91 стр.

3.3.2 Методы оптимизации графа межпредметных связей
        Характерной особенностью графа междисциплинарных связей является наличие
большого количества дуг, связывающих вершины графа. Впоследствии это может вызвать
затруднения в распределении дисциплин по семестрам. Для уменьшения размерности графа
межпредметных связей используются следующие методы: выявления и устранения
контуров; исключения несущественных или эквивалентных путей; исключения связей,
перекрещивающих слои графа.

3.3.2.1 Выявление и удаление контуров
        Введем несколько определений [59]:
        Определение 3.4. Маршрут (путь) – это такая последовательность конечного или
бесконечного числа ребер (l1, l2, l3,…,ln), что каждые два соседних ребра li-1 и li инцидентны
одной вершине (смежные).
        Определение 3.5. Вершина V0, инцидентная ребру l1, называется началом маршрута, а
вершина Vn , инцидентная ребру ln называется концом маршрута.
        Определение 3.6. Если V0 = Vn, где V0 – начало маршрута, а Vn – конец маршрута, то
маршрут называют циклическим или контуром.
        Возможны два случая образования контуров:
        1. Наличие перекрестных связей между дисциплинами. Например, в результате
нарушения логики взаимосвязей между дисциплинами для начала изучения одного курса
требуется знание другого, и наоборот (рисунок 3.18а).
        2. Необходимость параллельного изучения курсов с попеременной передачей
информации из одного курса в другой (рисунок 3.18б).
        В процессе анализа графа межпредметных связей G(D,U) необходимо выявить
контуры, которые должны быть предоставлены ЛПР для их разрыва. В первом случае ЛПР
должен пересмотреть содержание курсов и ликвидировать противоречивые требования
путем перераспределения учебного материала или объединения дисциплин, входящих в
цикл. При возникновении второй ситуации необходимо провести детальный анализ и
выявить возможность параллельного изучения дисциплин или же обосновать необходимость
разрыва в изучении того или иного курса.
        Алгоритм выявления контуров основан на методе поиска в глубину:
     1. Формируется множество вершин контура R = {r}, где r – вершина, входящая в
           контур.
     2. Добавить во множество R вершину {k | (i,k) ≠ 0 и k ∉ R}.
     3. Если вершина k∈R, то обнаружен цикл и далее п.4, иначе п. 5.
     4. Двигаясь в обратном порядке, обнаружить вершины, входящие в цикл, и обнулить
           связь [j,k], где j – последняя вершина, смежная k.
     5. Если есть смежные вершины вершине K, то повторить п. 2, иначе обнулить
           элемент матрицы [j,k], где j – последняя вершина, смежная k.
     6. Повторять для всех вершин с п.1.

                    2
                                                            1                    2
           1                  3
                                                             б) Параллельные связи
          а) Перекрестные ссылки
                     Рисунок 3.18 - Возможные случаи образования контуров




                                             91