Методы решения систем с разреженными матрицами. Теория графов. Глушакова Т.Н - 34 стр.

                                     34


            6         1       10          11      8

     G                                                    5
            9         2        4          7       3

73. Для графа G из задачи 72
    1) перечислить все смежные вершины и указать их степень;
    2) найти смежное множество для вершин 4, 5; расстояние между вершина-
       ми 10, 3 и 9, 5; эксцентриситет вершины 11; диаметр графа G; клику;
    3) указать несколько путей, соединяющих вершины 6,7; периферийные и
       псевдопериферийные вершины, циклы, частичный граф и подграф, раз-
       делители.
74. Построить структуру уровней смежности для графа G из задачи 72.
75. Реализовать следующие алгоритмы для графа G из задачи 72:
    1) алгоритм Катхилл-Макки;
    2) алгоритм уменьшения профиля разреженной матрицы;
    3) алгоритм отыскания ППВ;
    4) алгоритм отыскания вершины с большим значением эксцентриситета;
    5) алгоритм определения множества достижимости для Q={3,5,1};
    6) алгоритм минимальной степени;
    7) алгоритм оценки объема заполнения в методе минимальной степени;
    8) алгоритм метода вложенных сечений;
    9) алгоритм метода параллельных сечений:
      а) упрощенный вариант,
      б) стандартный вариант.
    Для 1), 2), 6), 8), 9) нарисовать портреты получившихся переупорядоченных
    матриц.
76. Для графа G из задачи 72 найти Reach(1,Q), Reach(7,Q), Reach(8,Q), где
    Q={2,6,9}.
77. Построить графы исключения Gk для графа G из задачи 72.
78. Пользуясь теоремой Джорджа-Лю, определить, принадлежит ли ребро (5,7)
    графу заполнения GF графа G из задачи 72.
79. Построить для графа G из задачи 72 его фактор-дерево, указать монотонное
    упорядочение фактор-дерева и компоненты связности.
80. Нарисовать портрет переупорядоченной матрицы с блочной структурой,
    отвечающей фактор-дереву из задачи 79.