Анализ графов на ЭВМ. Методические указания. Макарычев П.П - 23 стр.

 2. Выберите множество внешне устойчивых вершин S1 графа G.
Определите является ли множество S1 ядром графа.
 3. Вычислите числа вершинного β 0 и реберного β1 покрытия графа G.
 4. Осуществите генерацию матрицы смежности М ориентированного
помеченного графа Н порядка            n ≥ 6 . Метки графа выберите из
подмножества натуральных чисел {1,2,…,n}.
 5. Вычислите доминирующее множество вершин S2 графа Н. Определите
является ли множество S2 ядром орграфа.
                             Содержание отчета
 1. Матричные и графические представления графов G, H.
 2. Схема алгоритмов вычисления множества внешне устойчивых вершин
графа G, чисел вершинного β 0 и реберного β1 покрытия графа G,
доминирующего множества вершин графа Н.
 3. Протоколы вычислений S1, S2, β 0 , β1 в системе MathCAD.
                            Контрольные вопросы
 1. Существует ли граф G порядка n = 6 , в котором наименьшее
доминирующее множество вершин не является независимым?
 2. Чему равно число β (G ) вершинного графа, если оно максимально для
всех графов порядка n?
                          Лабораторная работа № 7
                       ЦЕПИ И ЦИКЛЫ В ГРАФАХ
      Цель работы — исследование цепей и циклов в ориентированных и
неориентированных графах.
                      Основные понятия и определения
      Чередующаяся       последовательность      вершин      и   ребер    графа
v1 , u1 , v2 , u2 ,..., ui , vi +1 называется маршрутом, соединяющим вершины vi и
vi+1. Маршрут (vi, vi+1) является цепью, все его вершины кроме, возможно,




                                       23