Прикладные задачи теории графов теория паросочетаний в математике, физике, химии. - купить книгу в интернет-магазине CentrMag по лучшим ценам! (00-01096074)

Описание Отзывы

Развернуть ▼

Репринтное издание
Книга известных специалистов по комбинаторике (Венгрия, США), охватывающая разнообразные области дискретной математики - задачу о коммивояжере, теорию потоков, модель Изинга ферромагнетизма, теорию матроидов и линейное программирование. В ней представлены как классические методы и алгоритмы, так и новые подходы и конструкции: NP-полнота, теоремы Бержа, Татта, Галлаи - Эдмондса и др. Книга имеет явно энциклопедический характер, отличается прикладной направленностью и требует лишь минимальной математической подготовки.
Для математиков разных специальностей — геометров, алгебраистов, специалистов по дискретной математике и кибернетике, для инженеров и программистов, а также аспирантов и студентов технических и экономических вузов.

Содержание
Предисловие редактора перевода
Предисловие
Основные термины
1 Паросочетания в двудольных графах
1.0. Введение
1.1. Теоремы Кёнига, Ф. Холла и Фробениуса
1.2. Алгоритм построения паросочетаний в двудольном графе: венгерский метод
1.3. Дефицит, избыток и кое-что из теории матроидов
1.4. Некоторые следствия из теорем о паросочетаниях в двудольных графах
2 Теория потоков
2.0. Введение
2.1. Теорема о максимальном потоке и минимальном разрезе
2.2. Потоковые алгоритмы
2.3. Потоко-эквивалентные деревья
2.4. Применение теории потоков в теории паросочетаний
2.5. Паросочетания, потоки и меры
3 Строение и размеры наибольших паросочетаний
3.0. Введение
3.1. Теорема Татта, лемма Галлаи и формула Бержа
3.2. Структурная теорема Галлаи - Эдмондса
3.3. Об исчислении барьеров
3.4. Достаточные условия существования паросочетаний заданого размера
4 Двудольные графы с совершенными паросочетаниями
4.0. Введение
4.1. Элементарные двудольные графы и их колосковая структура
4.2. Минимальные элементарные двудольные графы
4.3. Разложение на элементарные двудольные графы
5 Общие графы с совершенными паросочетаниями
5.0. Введение
5.1. Элементарные графы: элементарные свойства
5.2. Каноническое разбиение P (G)
5.3. Насыщенные графы и купола
5.4. Колосковая структура 1-расширяемых графов
5.5. Еще кое-что о факторно-критических и бикритических графах
6 Некоторые задачи теории графов, связанные с паросочетаниями
6.0. Введение
6.1. 2-паросочетания и 2-покрытия
6.2. 2-бикритические и регуляризуемые графы
6.3. Паросочетания, 2-паросочетания и свойство Кёнига
6.4. Гамильтоновы циклы и 2-паросочетания
6.5. Задача китайского почтальона
6.6. Оптимальные цепи, циклы, соединения и разрезы
7 Паросочетания и линейное программирование
7.0. Введение
7.1. Линейное программирование и паросочетания в двудольных графах
7.2. Паросочетания и дробные паросочетания
7.3. Политоп паросочетаний
7.4. Хроматический индекс
7.5. Политопы дробных паросочетаний и полиэдры покрытий
7.6. Размерность политопа совершенных паросочетаний
8 Определители и паросочетания
8.0. Введение
8.1. Перманенты
8.2. Метод формальных переменных
8.3. Пфаффиан и число совершенных паросочетаний
8.4. Перечисление совершенных паросочетаний, базирующееся на вероятностном подходе
8.5. Многочлены, перечисляющие паросочетания
8.6. Еще о числе совершенных паросочетаний
8.7. Два приложения в физических науках
9 Алгоритмы построения паросочетаний
9.0. Введение
9.1. Алгоритм Эдмондса
9.2. Взвешенные паросочетания
9.3. Алгоритм, основанный на теореме Галлаи — Эдмондса
9.4. Алгоритм линейного программирования для построения паросочетаний
10 Задача об f-факторе
10.0. Введение
10.1. Принципы сведения
10.2. Структурная теория f-факторов
10.3. Задача о наборах степеней вершин графов
11 Матроидные паросочетания
11.0. Введение
11.1. Формулировки задачи о матроидных паросочетаниях
11.2. Основная теорема о полиматроидном паросочетаний
11.3. Паросочетания в специальных полиматроидах
12 Вершинные упаковки и покрытия
12.0. Введение
12.1. Критические графы
12.2. Политопы вершинных упаковок
12.3. Паросочетания в гиперграфах
12.4. Вершинные упаковки в графах, не содержащих клешней
Литература
Предметный указатель
Указатель обозначений

5.0

★ ★ ★ ★ ★

0 отзывов

Пока нет отзывов. Будьте первым, кто оставит отзыв.