флеров
Системы представителей множеств
Рассмотрим один из комбинаторных подходов к характеристике структуры конечных множеств. Уже по названию можно понять, что основной идеей является замена системы множеств собранием их представителей. Мы рассмотрим здесь несколько теорем, которые гарантируют существование определенных выборов при соответствующих предположениях. Они интересны сами по себе и могут быть использованы в качестве теорем существования в различных комбинаторных задачах.
-
Содержание
- Журавлев ю.И., Флеров ю.А. Дискретный анализ
- Элементы комбинаторики.
- Введение
- Два принципа комбинаторики
- Функции и размещения
- Числа Стирлинга первого рода
- Циклическая структура перестановок
- Упорядоченные размещения.
- Сочетания и биномиальные коэффициенты.
- Производящие функции
- Биномиальные коэффициенты
- Исчисление конечных разностей
- Разложения
- Полиномиальные коэффициенты
- Разбиения
- Число разбиений
- 1. Формула 1.
- 2. Формула 2.
- Числа Белла.
- Принцип включений - исключений
- Задача о числе беспорядков (Задача о встречах)
- Количество сюръективных отображений
- Перестановки с ограничениями на местоположение
- Системы представителей множеств
- Системы различных представителей
- Системы общих представителей
- Функции алгебры логики
- Элементарные высказывания
- Элементарные логические операции (функции)
- Алгебраические свойства элементарных операций
- Разложение функций алгебры логики по переменным
- Функциональная полнота систем функций алгебры логики
- 1. Замена переменных.
- 2. Суперпозиция функций алгебры логики.
- Замкнутые классы.
- Критерий полноты
- Представление о результатах Поста
- Элементы теории графов
- Степени вершин
- О машинном представлении графов.
- Поиск в графе
- Поиск в глубину в графе
- Поиск в ширину в графе
- Пути и циклы
- Связность
- Деревья
- Остовное дерево (каркас)
- Эйлеровы пути и циклы
- Aлгоритм построения эйлерова цикла
- Гамильтоновы пути и циклы
- Нахождение кратчайших путей в графе
- Алгоритм нахождения расстояния от источника до всех остальных вершин в ориентированном графе с неотрицательными весами ребер
- Максимальный поток в сети
- Рекомендуемая литература.
- Оглавление