Лабораторная работа №6
ВНЕШНЯЯ УСТОЙЧИВОСТЬ И ПОКРЫТИЯ В ГРАФАХ Цель работы — исследование внешней устойчивости ориентированных и неориентированных графов, приобретение практических навыков исследования структур технических систем. Основные понятия и определения Подмножество вершин S графа G = ( V , U ) называется доминирующим (внешне устойчивым), если каждая вершина из V — S смежна с некоторой вершиной из S . Другими словами, каждая вершина графа находится на расстоянии не более единицы от доминирующего множества. Доминирующее множество называется минимальным, нет другого доминирующего множества, содержащегося в нем. Минимальных доминирующих множеств в графе может быть несколько, и они не обязательно содержат одинаковое количество вершин. Минимальное доминирующее множество, имеющее наименьшую мощность называется наименьшим. Подмножество вершин графа, являющееся одновременно независимым и доминирующим, называется ядром графа. Понятие доминирующего множества переносится и на случай ориентированных графов. Подмножество S вершин орграфа называется доминирующим, если для любой вершины существует такая вершина , что где А - множество дуг орграфа Подмножество вершин S, являющееся одновременно и независимым, и доминирующим называется ядром орграфа. Например, орграф на рис. 8, а имеет два ядра Орграф, изображенный на рис. 8, б, не имеет ядра. Pис. 8. Ориентированные графы Вершина и ребро графа покрывают друг друга, если они инцидентны. Ребро ( vi, vj ) покрывает вершины vi, и vj, а каждая из этих вершин покрывает это ребро. Подмножество называйся покрытием (вершинным покрытием, опорой) графа G, если каждое ребро из U инцидентно хотя бы одной вершине из S. Покрытие графа G называется минимальным,если оно не содержит покрытия с меньшим числом вершин, и наименьшим, если число вершин в нем — наименьшее среди всех покрытий графа G. Число вершин в наименьшем покрытии графа G называется числом покрытия (числом вершинного покрытия) графа G и обозначается через . Реберным покрытием графа G называется такое подмножество ребер , которое скрывает все вершины графа. При этом каждая вершина в G инцидентна по крайней мере одному ребру из W. Реберное покрытие графа называется минимальным, если в нем не содержится покрытий с меньшим числом ребер, и наименьшим, если число ребер в нем — наименьшее среди всех покрытий. Число ребер в наименьшим реберном покрытии графа G называется числом реберного покрытия и обозначается через . Лабораторное задание 1. Выполните генерацию матрицы смежности M( G) неориентированного помеченного графа G порядка . Метки графа выберите из подмножества натуральных чисел {1,2,…, n}. 2. Выберите множество внешне устойчивых вершин S1 графа G. Определите является ли множество S1 ядром графа. 3. Вычислите числа вершинного и реберного покрытия графа G. 4. Осуществите генерацию матрицы смежности М ориентированного помеченного графа Н порядка . Метки графа выберите из подмножества натуральных чисел {1,2,…, n}. 5. Вычислите доминирующее множество вершин S2 графа Н. Определите является ли множество S2 ядром орграфа. Содержание отчета 1. Матричные и графические представления графов G, H. 2. Схема алгоритмов вычисления множества внешне устойчивых вершин графа G, чисел вершинного и реберного покрытия графа G, доминирующего множества вершин графа Н. 3. Протоколы вычислений S1, S2, , в системе MathCAD. Контрольные вопросы 1. Существует ли граф G порядка , в котором наименьшее доминирующее множество вершин не является независимым? 2. Чему равно число вершинного графа, если оно максимально для всех графов порядка n?
Популярное: Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (211)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |