лекции по МОТС / ДИСКРЕТНАЯ МАТЕМАТИКА Графы
11.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. Улучшенный алгоритм последовательного раскрашивания