11.1.2. Независимые множества вершин и ребер
Множество вершин называется независимым, если никакие две из них не смежны. Наибольшее число вершин в независимом множестве вершин называется вершинным числом независимости и обозначается (30.
Пример
Для полного графа Ро(Кр) = 1.
Для полного двудольного графа 0о(Кт>п) = max(m,n).
Для вполне несвязного графа /Зо(лр) = р.
Для несвязного графа (30(Gi U G2) = /3o(Gi) + /30(G2).
Множество ребер называется независимым, если никакие два из них не смежны. Наибольшее число ребер в независимом множестве ребер называется реберным числом независимости и обозначается /9j.
ЗАМЕЧАНИЕ -
Независимое множество ребер называется также паросочетанием.
Пример
Для четного цикла /3i(K^n) = п, для нечетного цикла f3i(K2n+i) = n-l.
Для полного графа с четным числом вершин ^(К^п} = п, для полного графа с нечетным числом вершин /^(.ft^n+i) = n — l.
3. Для полного двудольного графа (3i(Km^n) = min(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. Улучшенный алгоритм последовательного раскрашивания