- •Часть 1
- •Часть 1
- •Введение
- •1. Основные понятия теории графов
- •Задачи теории графов
- •1.2. Основные определения
- •1.3. Степени вершин графа
- •1.4. Изоморфизм графов
- •2. Представление графов в эвм и операции над ними
- •2.1. Матричные способы задания графов
- •2.2. Список ребер (луг) и структура смежности графа
- •2.3. Части графов
- •2.4. Основные операции над графами
- •3. Маршруты в графах
- •3.1. Понятие маршрута
- •Маршруты в неориентированных графах
- •Маршруты в ориентированных графах
- •3.2. Связность в графах.
- •В примере 3 граф имеет две сильно связных компоненты.
- •3.3. Связность и матрица смежности графа
- •3.4. Матрица взаимодостижимости
- •4. Деревья
- •4.1. Свободные деревья
- •4.2. Ориентированные, упорядоченные и бинарные деревья
- •Эквивалентное определение ориентированного дерева
- •5. Эйлеровы и гамильтоновы графы.
- •5.1. Эйлеровы графы.
- •5. 2. Алгоритм построения эйлерова цикла в эйлеровом графе
- •5.3. Гамильтоновы графы
- •5.4. Оценки числа эйлеровых и гамильтоновых графов
- •6. Фундаментальные циклы и разрезы
- •6.1. Фундаментальные циклы
- •6.2. Разрезы
- •7. Связь теории графов с бинарными отношениями и векторными пространствами
- •7.1. Отношения на множествах и графы
- •7.2. Векторные пространства, связанные с графами
- •8. Планарность и раскраска графов
- •8.1. Планарные графы
- •8.2. Раскраска графов
- •8.3. Алгоритм последовательной раскраски
- •9. Покрытия и независимость
- •9.1. Покрывающие множества вершин и ребер
- •9.2. Независимые множества вершин и ребер
- •9.3. Доминирующие множества
- •10. Кратчайшие маршруты в графах
- •10.1. Расстояния в графах
- •10.2. Алгоритм Форда-Беллмана
- •11. Задача коммивояжера
- •11.1. Постановка задачи
- •11.2. Обходы вершин графа по глубине и ширине
- •11.3. Решение задачи коммивояжера
- •12. Потоки в сетях
- •12.1. Основные определения
- •12.2. Теорема Форда и Фалкерсона
- •12.3. Алгоритм построения максимального потока
- •13. Сетевое планирование и управление
- •13.1. Элементы сетевого графика
- •13.2. Временные параметры сетевого графика
- •13.3. Распределение ограниченных ресурсов
- •14. Анализ технических систем (на примере электрической цепи)
- •14.1 Закон Кирхгофа
- •14.2. Основные уравнения
- •15. Сигнальные графы
- •15.1. Общие представления о сигнальных графах
- •15.2. Преобразования сигнальных графов
- •15.3. Формула Мэзона
- •16. Переключательные сети (схемы)
- •17. Математические машины и цепи маркова
- •Библиографический список
- •Оглавление
- •Часть 1
- •394026 Воронеж, Московский просп., 14
9.3. Доминирующие множества
Задача о наименьшем покрытии (ЗНП) является примером общей экстремальной задачи, к которой прямо или косвенно сводятся практические задачи. Эта задача может быть сформулирована в терминах доминирующего множества.
Определение. Для графа G(V,E) множество вершин SV называется доминирующим множеством, если для любой вершины vV либо vS, либо существуют вершина sS и ребро (S,V).
Доминирующее множество называется минимальным, если его подмножество не является доминирующим. Доминирующее множество называется наименьшим, если число элементов в нем минимально.
Пример: Задача о пяти ферзях. Расставить их на шахматной доске так, чтобы они били всю доску. Это задача об отыскании наименьших доминирующих множеств.
Доминирование тесно связано с вершинной независимостью.
Теорема. Независимое множество вершин является максимальным тогда и только тогда, когда оно является доминирующим.
Независимое доминирующее множество вершин называется ядром графа.
Рассмотрим задачу. Пусть каждый вершине сопоставлена некоторая цепь. Требуется выбрать доминирующее множество с наименьшей суммарной ценой. Эта задача называется задачей о наименьшем покрытии (ЗНП). К этой задаче сводятся, например:
Задача о выборе переводчиков. Организации нужно нанять переводчиков с определенного множества языков. Каждый из имеющихся переводчиков владеет некоторыми иностранными языками и требует определенную зарплату. Требуется определить, каких переводчиков следует нанять, чтобы сумма расходов на зарплату была минимальной.
Задача о перевозки. Поставщику необходимо доставить товары своим потребителям. Имеется множество различных маршрутов, каждый их которых позволяет обслуживать определенное подмножество потребителей и требует определенных расходов. Требуется определить, какие маршруты следует использовать, чтобы все потребители были обслужены, а сумма транспортных расходов была наименьшей.
ЗНП могут быть сформулированы различными способами.
Пусть имеется конечное множество {V1,…, Vp} и семейство подмножеств этого множества {E1,…, Ep}. Каждому подмножеству Eiприписать вес. Найти покрытие E` (E`E) наименьшего веса. Из этой формулировки происходит название «задача о наименьшем покрытии».
ЗНП можно сформулировать как задачу линейного программирования min при ограничениях (i=1,…,p), где ci0 xi= tij=
Дана булева матрица Т размера р на р. Каждому столбцу приписан вес cj. Найти такое множество столбцов минимальной стоимости, чтобы любая строка содержала единицу хотя бы в одном из выбранных столбцов.
ЗНП относиться к числу трудоемких задач, и для ее решения применяются переборные алгоритмы с теми или иными улучшениями. Связь ЗНП с другими задачами можно представить в следующем виде.
ЗНП
Наименьшее
доминирующее ЗНП с единичными весами
множество вершин
Наибольшее независимое
множество вершин
Наименьшее
доминирующее Наибольшее независимое множество ребер множество ребер
Рис. 32
На этой схеме стрелки от задач А к задачи В означает, что решение задачи А влечет за собой решение задачи В.