11.3.3. Задача о наименьшем покрытии
Рассмотрим следующую задачу. Пусть каждой вершине сопоставлена некоторая цена. Требуется выбрать доминирующее множество с наименьшей суммарной ценой. Эта задача называется задачей о наименьшем покрытии (сокращенно ЗНП).
ЗНП является весьма общей задачей, к которой сводятся многие другие задачи.
Пример
Задача о выборе переводчиков. Организации нужно нанять переводчиков для перевода с определенного множества языков. Каждый из имеющихся перевод чиков владеет некоторыми иностранными языками и требует определенную зарплату. Требуется определить, каких переводчиков следует нанять, чтобы сумма расходов на зарплату была минимальной.
Задача о развозке. Поставщику нужно доставить товары своим потребителям. Имеется множество возможных маршрутов, каждый из которых позволяет об служить определенное подмножество потребителей и требует определенных расходов. Требуется определить, какие маршруты следует использовать, что бы все потребители были обслужены, а сумма транспортных расходов была минимальной.
- Иркутский государственный технический университет
- 1. Определения графов
- 7.4.5. Массив дуг
- 8.4.2. Трансверсаль
- 8.5.4. Алгоритм нахождения максимального потока
- 8.6.3. Выделение компонент сильной связности
- 8.7.1. Длина дуг
- 8.7.2. Алгоритм Флойда
- 8.7.3. Алгоритм Дейкстры
- Глава 9 Деревья
- 9.1. Свободные деревья
- 9.1.1. Определения
- 9.1 .2. Основные свойства деревьев
- 9.2. Ориентированные, упорядоченные и бинарные деревья
- 9.2.1. Ориентированные деревья
- 9.2.2. Эквивалентное определение ордерева
- 9.2.3. Упорядоченные деревья
- 9.2.4. Бинарные деревья
- 9.3. Представление деревьев в эвм
- 9.3.1. Представление свободных, ориентированных и упорядоченных деревьев
- 9.3.2. Представление бинарных деревьев
- 9.3.3. Обходы бинарных деревьев
- 9.3.4. Алгоритм симметричного обхода бинарного дерева
- 9.4. Деревья сортировки
- 9.4.1. Ассоциативная память
- 9.4.2. Способы реализации ассоциативной памяти
- 9.4.3. Алгоритм бинарного (двоичного) поиска
- 9.4.4. Алгоритм поиска в дереве сортировки
- 9.4.5. Алгоритм вставки в дерево сортировки
- 9.4.6. Алгоритм удаления из дерева сортировки
- 9.4.7. Вспомогательные алгоритмы для дерева сортировки
- 9.4.8. Сравнение представлений ассоциативной памяти
- 9.4.9. Выровненные деревья
- 9.4.10. Сбалансированные деревья
- 9.5. Кратчайший остов
- 9.5.1. Определения
- 9.5.2. Схема алгоритма построения кратчайшего остова
- 9.5.3. Алгоритм Краскала
- Глава 10 Циклы
- 10.1. Фундаментальные циклы и разрезы
- 10.1.1. Циклы и коциклы
- 10.1.2. Независимые множества циклов и коциклов
- 10.1.3. Циклический и коциклический ранг
- 10.2. Эйлеровы циклы
- 10.2.1. Эйлеровы графы
- 10.2.2. Алгоритм построения эйлерова цикла в эйлеровом графе
- 10.2.3. Оценка числа эйлеровых графов
- 10.3. Гамильтоновы циклы
- 10.3.1. Гамильтоновы графы
- 10.3.2. Задача коммивояжера
- Глава 11 Независимость и покрытия
- 11.1. Независимые и покрывающие множества
- 11.1.1. Покрывающие множества вершин и ребер
- 11.1.2. Независимые множества вершин и ребер
- 11.1.3. Связь чисел независимости и покрытий
- 11.2. Построение независимых множеств вершин
- 11.2.1. Постановка задачи отыскания наибольшего независимого множества вершин
- 11.2.2. Поиск с возвратами
- 11.2.3. Улучшенный перебор
- 11.2.4. Алгоритм построения максимальных независимых множеств вершин
- 11.3. Доминирующие множества
- 11.3.1. Определения
- 11.3.2. Доминирование и независимость
- 11.3.3. Задача о наименьшем покрытии
- 11.3.4. Эквивалентные формулировки знп
- 11.3.5. Связь знп с другими задачами
- Глава 12 Раскраска графов
- 12.1. Хроматическое число
- Ух, . . . ,Vn одноцветные классы,доказательство
- 12.2. Планарность
- 12.2.2. Эйлерова характеристика
- 12.2.3. Теорема о пяти красках
- 12.3. Алгоритмы раскрашивания
- 12.3.1. Точный алгоритм раскрашивания
- 12.3.2. Приближенный алгоритм последовательного раскрашивания
- 12.3.3. Улучшенный алгоритм последовательного раскрашивания