|
В.Липский. Комбинаторика для программистов.
| | Оглавление
0.1 Предисловие редактора перевода.
0.2 От автора.
Введение в комбинаторику
1.1 Основные понятия
1.2 Функции и размещения.
1.3 Перестановки: разложение на циклы знак перестановки.
1.4 Генерирование перестановок
1.5 Подмножества множества множества с повторениями
1.6 k-элементные подмножества биномиальные коэффициенты.
1.7 Генерирование k-элементных подмножеств.
1.8 Разбиения множества
1.9 Числа Стирлинга второго и первого рода
1.10 Генерирование разбиений множества.
1.11 Разбиения чисел.
1.12 Производящие функции
1.13 Принцип включения и исключения
1.14 Задачи
Алгоритмы на графах
2.1 Машинное представление графов.
2.2 Поиск в глубину в графе
2.3 Поиск в ширину в графе
2.4 Стягивающие деревья (каркасы).
2.5 Отыскание фундаментального множества циклов в графе
2.6 Нахождение компонент двусвязности.
2.7 Эйлеровы пути
2.8 Алгоритмы с возвратом (back-tracking).
2.9 Задачи
3 Нахождение кратчайших путей в графе
3.1 Начальные понятия.
3.2 Кратчайшие пути от фиксированной вершины.
3.3 Случай неотрицательных весов — алгоритм Дейкстры
3.4 Пути в бесконтурном орграфе.
3.5 Кратчайшие пути между всеми парами вершин транз. замыкание.
3.6 Задачи
4 Потоки в сетях и родственные задачи
4.1 Максимальный поток в сети
4.2 Алгоритм построения максимального потока
4.3 Наибольшие паросочетания в двудольных графах.
4.4 Системы различных представителей.
4.5 Разложение на цепи.
4.6 Задачи
5 Матроиды
5.1 Жадный алгоритм решения оптимизационных задач.
5.2 Матроиды и их основные свойства
5.3 Теорема Рамо-Эдмондса
5.4 Матричные матроиды
5.5 Графовые матроиды
5.6 Матроиды трансверсалей
5.7 Задачи
Предметный указатель
А
алгоритм генерирования всех перестановок всех подмножеств k-элементного множества всех последовательностей Дейкстры Диница жадный для матричного матроида для матроида трансверсалей Краскала нахождения всех гамильтоновых циклов всех разбиений числа кратчайшего пути множества элементарных циклов графа разбиения семейства всех подмножеств множества на симметричные цепи расстояний от источника до всех вершин в бесконтурном графе эйлерового цикла нумерации вершин бесконтурного графа определения знака перестановки построения максимального потока в сети с возвратом Уоршалла Флойда Хопкрофта-Карпа антицепь
Б
Беллман Р.Е. бинарный код Грэя порядка п блок графа разбиения
В
вектор инверсивный величина потока вершина графа изолированная отец потомок свободная сын вес дуги элемента матроида ветвь
Г
Гамильтон Р.В. Гейл Д. генерирование множества перестановок подмножеств k-элементных разбиений числа граница верхняя нижняя граф бесконтурный выпуклый
Д
двудольный двусвязный неориентированный ориентированный связный сильно связный графы изоморфные группа перестановок степени п группа симметрическая степени п Дейсктра Э.В. Джонсон СМ. Дилворт Р.П. Диниц Е.А. двоичный n-мерный куб де Брейн Н.Д. дерево бинарное стягивающее графа деревья изоморфные диаграмма Феррерса длина пути сети увеличивающей цепи дуга
З
задача NP-полная закон Кирхгофа замыкание отношения транзитивное знак перестановки измельчение разбиения инверсия инволюция источник
К
Карп P.M. Кениг Д. КлосС Краскал Д.В. класс эквивалентности клика комбинация без повторений коммутатор размерности N x N компонента двусвязности связности сильной связности конец пути контур корень дерева стягивающего коэффициент биномиальный кратность элемента
Л
лес стягивающий линия матрицы
М
матрица бистохастическая инциденций перестановочная смежности соседства ребер матроид база графа Предметный указатель графовый двойственный матричный ранг свободный трансверсалей матроиды изоморфные метод Лума Флойда метод увеличивающих цепей метод Форда-Беллмана множество матроида зависимое независимое с повторениями частично упорядоченное мост графа мощность множества
Н
начало пути
О
область левая правая оптимальность по Гейлу отец вершины отношение антисимметричное бинарное транзитивное замыкание симметричное транзитивное эквивалентности очередь
П
палиндром пара упорядоченная паросочетание паскаль (язык) перестановка нечетная обратная тождественная четная перманент матрицы петля подграф подмножество k-элементное собственное подпространство матроида натянутое на множество поиск в глубину в ширину покрытие вершинное порядок антилексикографический лексикографический частичный потенциал вершины сети поток поток максимальный псевдомаксимальный потомок вершины принцип включения-исключения произведение декартово Коши рядов пропускная способность вершины дуги
Р
разреза псевдоцикл путь в графе гамильтонов длина Предметный указатель конец критический начало эйлеров Радо разбиение множества числа
С
самосопряженное сопряженное разложение на циклы размещение объектов по ящикам упорядоченное разность симметрическая разрез сети минимальный ранг матроида расстояние ребро решетка ряд Маклорена формальный секция коммутатора сеть сеть СРМ PERT перестраиваемая размерности N х N
Т
трехсекционная Клоса система различных представителей система различных представителей общая сложение рядов сложность временная вычислительная по памяти список инцидентности стек степень вершины сток суперпозиция перестановок сын вершины Троттер Х.Ф. теорема венгерская Дилворта Радо-Эдмондса Холла тождество Коши точка сочленения транзитивное замыкание отношения трансверсаль частичная транспозиция треугольник Паскаля
У
УоршаллС увеличивающая цепь длина
Ф
Феррерс Н.М. Флойд Р.В. Форд Л.Р. фундаментальное множество циклов функция взаимно однозначная на производящая экспоненциальная ядро Предметный указатель
Х
Холл Ф. Хопкрофт Дж. хорда
Ц
цепь цепь симметричная
Ч
чередующаяся цикл гамильтонов де Брейна порядка п матроида разложения перестановки эйлеров элементарный число Белла Стирлинга второго рода Фибоначчи
Ш
шаг алгоритма
Э
Эгервари Э. Эдмондс Дж. экспоненциальная производящая функция элемент зависимый от множества
Я
ядро функции
|
|
| |
|
| |
|
|
Найдите то что искали здесь:
|
|
| |
