Лабораторная работа №6

ВНЕШНЯЯ УСТОЙЧИВОСТЬ И ПОКРЫТИЯ В ГРАФАХ

Цель работы — исследование внешней устойчивости ориентированных и неориентированных графов, приобретение практических навыков исследования структур технических систем.

Основные понятия и определения

Подмножество вершин S графа G = ( V , U ) называется доминирующим (внешне устойчивым), если каждая вершина из V — S смежна с некоторой вершиной из S . Другими словами, каждая вершина графа находится на расстоянии не более единицы от доминирующего множества. Доминирующее множество называется минимальным, нет другого доминирующего множества, содержащегося в нем. Минимальных доминирующих множеств в графе может быть несколько, и они не обязательно содержат одинаковое количество вершин. Минимальное доминирующее множество, имеющее наименьшую мощность называется наименьшим.

Подмножество вершин графа, являющееся одновременно независимым и доминирующим, называется ядром графа.

Понятие доминирующего множества переносится и на случай ориентированных графов. Подмножество S вершин орграфа называется доминирующим, если для любой вершины  существует такая вершина , что  где А - множество дуг орграфа Подмножество вершин S, являющееся одновременно и независимым, и доминирующим называется ядром орграфа. Например, орграф на рис. 8, а имеет два ядра

Орграф, изображенный на рис. 8, б, не имеет ядра.

Pис. 8. Ориентированные графы

Вершина и ребро графа покрывают друг друга, если они инцидентны. Ребро ( v_i, v_j ) покрывает вершины v_i, и v_j, а каждая из этих вершин покрывает это ребро. Подмножество  называйся покрытием (вершинным покрытием, опорой) графа G, если каждое ребро из U инцидентно хотя бы одной вершине из S. Покрытие графа G называется минимальным,если оно не содержит покрытия с меньшим числом вершин, и наименьшим, если число вершин в нем — наименьшее среди всех покрытий графа G. Число вершин в наименьшем покрытии графа G называется числом покрытия (числом вершинного покрытия) графа G и обозначается через .

Реберным покрытием графа G называется такое подмножество ребер , которое скрывает все вершины графа. При этом каждая вершина в G инцидентна по крайней мере одному ребру из W. Реберное покрытие графа называется минимальным, если в нем не содержится покрытий с меньшим числом ребер, и наименьшим, если число ребер в нем — наименьшее среди всех покрытий. Число ребер в наименьшим реберном покрытии графа G называется числом реберного покрытия и обозначается через .

Лабораторное задание

1. Выполните генерацию матрицы смежности M( G) неориентированного помеченного графа G порядка . Метки графа выберите из подмножества натуральных чисел {1,2,…, n}.

2. Выберите множество внешне устойчивых вершин S₁ графа G. Определите является ли множество S₁ ядром графа.

3. Вычислите числа вершинного  и реберного  покрытия графа G.

4. Осуществите генерацию матрицы смежности М ориентированного помеченного графа Н порядка . Метки графа выберите из подмножества натуральных чисел {1,2,…, n}.

5. Вычислите доминирующее множество вершин S₂ графа Н. Определите является ли множество S₂ ядром орграфа.

Содержание отчета

1. Матричные и графические представления графов G, H.

2. Схема алгоритмов вычисления множества внешне устойчивых вершин графа G, чисел вершинного  и реберного  покрытия графа G, доминирующего множества вершин графа Н.

3. Протоколы вычислений S1, S2, ,  в системе MathCAD.

Контрольные вопросы

1. Существует ли граф G порядка , в котором наименьшее доминирующее множество вершин не является независимым?

2. Чему равно число  вершинного графа, если оно максимально для всех графов порядка n?