Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии

Description

Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии: Пер. с англ. — M.: Мир, 1998. — 653 с., ил. ISBN 5-03-002517-0 Книга известных специалистов по комбинаторике (Венгрия, США), охватывающая разнообразные области дискретной математики — задачу о коммивояжере, теорию потоков, модель Изинга ферромагнетизма, теорию ма- троидов и линейное программирование. В ней представлены как классические методы и алгоритмы, так и новые подходы и конструкции: 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. Каноническое разбиение T7(G) 5.3. Насыщенные графы и купола 5.4. Колосковая структура l-расширяемых графов 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 Задача об /-факторе 10.0. Введение 10.1. Принципы сведения 10.2. Структурная теория /-факторов 10.3. Задача о наборах степеней вершин графов 11 Матроидные паросочетания 11.0. Введение 11.1. Формулировки задачи о матроидных паросочетаниях 11.2. Основная теорема о полиматроидном паросочетаний 11.3. Паросочетания в специальных полиматроидах 12 Вершинные упаковки и покрытия 12.0. Введение 12.1. Критические графы 12.2. Политопы вершинных упаковок 12.3. Паросочетания в гиперграфах 12.4. Вершинные упаковки в графах, не содержащих клешней Литература Предметный указатель Указатель обозначений