11.1.1. Покрывающие множества вершин и ребер
Говорят, что вершина покрывает инцидентные ей ребра, а ребро покрывает инцидентные ему вершины.
Множество таких вершин, которые покрывают все ребра, называется вершинным покрытием. Наименьшее число вершин во всех вершинных покрытиях называется числом вершинного покрытия и обозначается а0.
Пример
Для полного графа а0(Кр) = р - 1.
Для полного двудольного графа ао(Кт,п) = min(m,n).
Для вполне несвязного графа а0(Кр] = 0.
Для несвязного графа a0(Gi U G2) = <*o(Gi) + a0(G2).
Множество таких ребер, которые покрывают все вершины, называется реберным покрытием. Наименьшее число ребер во всех реберных покрытиях называется числом реберного покрытия и обозначается а±.
ЗАМЕЧАНИЕ —
Для графа с изолированными вершинами ai не определено.
Пример
Для четного цикла ai(K2n) = n, для нечетного цикла ai(K2n+i) = n-f 1.
Для полного графа с четным числом вершин ai(K2n) = п, для полного графа с нечетным числом вершин a1(JC2n+i) = n H-1.
Для полного двудольного графа ai(Kmin) = max(m,n).
- Иркутский государственный технический университет
- 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. Улучшенный алгоритм последовательного раскрашивания