Методические указания к выполнению лабораторных работ по курсу "Дискретная математика" пенза 2004 (стр. 5 из 6)
Подмножество вершин графа, являющееся одновременно независимым и доминирующим, называется ядром графа.
Понятие доминирующего множества переносится и на случай ориентированных графов. Подмножество 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?Лабораторная работа № 7
ЦЕПИ И ЦИКЛЫ В ГРАФАХ
Цель работы — исследование цепей и циклов в ориентированных и неориентированных графах.
Основные понятия и определения
Чередующаяся последовательность вершин и ребер графа
называется маршрутом, соединяющим вершины vi и vi+1. Маршрут (vi, vi+1) является цепью, все его вершины кроме, возможно, крайних, различны. Маршрут (vi, vi+1) называется циклическим, если vi = vi+1. Циклическая цепь называется циклом, циклическая простая цепь — простым циклом. Число ребер в маршруте (vi, vi+1) определяет его длину. Простой цикл единичной длины называется единичным циклом. Длина всякого цикла в простом графе (без петель кратных ребер) и кратных ребер) минимум равна трем. Минимальная из длин циклов графа называется его обхватом.Любая цепь графа может рассматриваться как его подграф. В цепи Q графа G, заданной последовательностью вершин v1, v2,…,vn, можно выделить две вершины vi, vj. Часть цепи Q, начинающаяся в vi и заканчивающаяся в vj(vi, vi+1,…,vj-1, vj), сама является цепью графа G. Цепь (vi, vj) называется полуцепью цепи Q. На рис. 9 приведен граф G, в котором (1,2) и (1, 2, 3, 5) - простые цепи. Цепь (1, 3, 5, 4, 3, 2) не является простой цепью. Маршрут (1, 2, 3, 5, 4, 3, 2) — не цепь. Цепь (1, 2, 3, 1) — простой цикл. Обхват рассматриваемого графа равен трем.
Рис. 9. Граф с обхватом, равным трем
В ориентированных графах маршрут ориентированный и является последовательностью вида (1). Аналогом цепи с в ориентированном графе служит путь (ориентированная цепь). Вершина vj в ориентированном графе называется достижимой из вершины vi, если существует путь (vi, vj).
Произвольный ориентированный маршрут (vi, vj), не являющийся простой цепью, превращается в простую цепь после устранения ''лишних звеньев''. Поэтому верны утверждения:
1. При i, не равном j, всякий маршрут (vi, vj) содержит простую цепь.
2. Всякий цикл содержит простой цикл.
3. Если C, D - два несовпадающих простых цикла, имеющих общее ребро ui, то граф
также содержит простой цикл.Лабораторное задание
1. Выполните генерацию матрицы смежности M(G) неориентированного помеченного графа G порядка
. Метки графа выберите из подмножества натуральных чисел {1,2,…,n}. Отождествляя каждую вершину графа с одним из элементов на рис.6, постройте функциональную схему электронного узла. При этом входы элементов с номерами 1, 2 являются входами, а выходы элементов с номерами n, n - 1 — выходами всего учла.2. Вычислите остов минимального веса и базисные циклы Li, i = 1, 2,..., m в графе G. При отсутствии базисных циклов в графе по согласованию с преподавателем осуществите добавление ребра (ребер)
3. Определите через базисные циклы все остальные циклы Lj, j = m+1, m+2,… в графе G. В соответствии с найденными циклами графа укажите на функциональной схеме узла все замкнутые цепи (контуры).
4. Осуществите генерацию матрицы смежности M(H) помеченного орграфа H порядка
. Определите все вершины, достижимые из вершины v1. Выберите достижимую вершину vj, j = 2,3,…,n, определяющую самый длинный маршрут. Определите, является ли самый длинный маршрут простой ориентированной цепью. Если маршрут не является простой ориентированной цепью, то удалите ''лишние звенья''.Содержание отчета
1. Матричные и графические представления графов G, H, функциональная схема электронного узла.
2. Схема алгоритмов вычисления остова и базисных циклов графа G и достижимых из вершины v1 вершин графа H.
3. Протоколы вычислений характеристик графа G, Н средствами системы MathCAD.
Контрольные вопросы
1. Как найти остов графа?
2. Найдите остовные деревья в графе Петерсена.
3. Верно ли, что, диаметр связного графа G равен k (k>2), то в G существует остовное дерево, диаметр которого также равен k?
ЛИТЕРАТУРА
1. Акимов О.Е. Дискретная математика: логика, группы, графы. – М.: Лаборатория Базовых Знаний, 2001 – 352 с.