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

паросочетаний графа G. Число ребер в наибольшем паросочетании
называется числом паросочетания и обозначается через α1 (G).
     Независимые множества ребер графа G находятся во взаимно
однозначном соответствии с независимым множеством
                             Лабораторное задание
 1. Выполните генерацию модифицированной матрицы смежности M(G)
неориентированного помеченного графа G. Порядок графа п определяется
преподавателем.
 2. Определите наибольшее независимое множество вершин и вершинное
число внутренней устойчивости α 0 (G) графов G и ¬ G.
 3. Определите наибольшее независимое множество ребер и число
паросочетаний α1 (G) графов G и ¬ G.
                              Содержание отчета
 1. Матричное и графическое представление графа G ( ¬ G).
 2. Схемы алгоритмов вычисления чисел внутренней устойчивости α 0 (G)
и паросочетаний α1 (G) графов G и ¬ G.
 3. Протоколы     вычислений       чисел   внутренней    устойчивости   и
паросочетаний графов G и ¬ G.
                             Контрольные вопросы
 1. Верно ли утверждение, что любое паросочетание графов содержится в
наибольшем паросочетании?
 2. Если G - дерево, содержащее n вершин, то выполняется ли для него
соотношение α 0 (G ≥ n 2 ?
 3. Каким    образом    можно      определить     наибольшее   независимое
множество вершин в графе Петерсена?




                                      17