 |
- ⒶⒸЛовас Л... Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. (Matching theory, 1986) [Djv-Fax- 6.0M] [Pdf-Fax- 9.9M] Научное издание. Авторы: Ласло Ловас, Майкл Д. Пламмер (Laszlo Lovasz, Michael D. Plummer). Перевод с английского: Г.П. Гаврилов, В.В. Мартынюк, М.А. Никитина. Редактор перевода: Г.П. Гаврилова. Художник: Н.В. Зотова.
(Москва: Издательство «Мир»: Редакция литературы по математическим наукам, 1998)
Скан: AAW, OCR, обработка, формат Djv-Fax, Pdf-Fax: bolega, 2022
- ОГЛАВЛЕНИЕ:
Предисловие редактора перевода (5).
Предисловие (7).
Основные термины (31).
1. Паросочетания в двудольных графах (37).
1.0. Введение (37).
1.1. Теоремы Кенига, Ф. Холла и Фробениуса (40).
1.2. Алгоритм построения паросочетаний в двудольном графе: венгерский метод (49).
1.3. Дефицит, избыток и кое-что из теории матроидов (56).
1.4. Некоторые следствия из теорем о паросочетаниях в двудольных графах (69).
2. Теория потоков (84).
2.0. Введение (84).
2.1. Теорема о максимальном потоке и минимальном разрезе (86).
2.2. Потоковые алгоритмы (90).
2.3. Потоко-эквивалентные деревья (109).
2.4. Применение теории потоков в теории паросочетаний (117).
2.5. Паросочетания, потоки и меры (125).
3. Строение и размеры наибольших паросочетаний (134).
3.0. Введение (134).
3.1. Теорема Татта, лемма Галлаи и формула Бержа (135).
3.2. Структурная теорема Галлаи - Эдмондса (147).
3.3. Об исчислении барьеров (158).
3.4. Достаточные условия существования паросочетаний заданого размера (166).
4. Двудольные графы с совершенными паросочетаниями (177).
4.0. Введение (177).
4.1. Элементарные двудольные графы и их колосковая структура (178).
4.2. Минимальные элементарные двудольные графы (184).
4.3. Разложение на элементарные двудольные графы (196).
5. Общие графы с совершенными паросочетаниями (202).
5.0. Введение (202).
5.1. Элементарные графы: элементарные свойства (204).
5.2. Каноническое разбиение V(G) (210).
5.3. Насыщенные графы и купола (220).
5.4. Колосковая структура 1-расширяемых графов (238).
5.5. Еще кое-что о факторно-критических и бикритических графах (263).
6. Некоторые задачи теории графов, связанные с паросочетаниями (283).
6.0. Введение (283).
6.1. 2-паросочетания и 2-покрытия (283).
6.2. 2-бикритические и регуляризуемые графы (288).
6.3. Паросочетания, 2-паросочетания и свойство Кенига (291).
6.4. Гамильтоновы циклы и 2-паросочетания (301).
6.5. Задача китайского почтальона (304).
6.6. Оптимальные цепи, циклы, соединения и разрезы (319).
7. Паросочетания и линейное программирование (333).
7.0. Введение (333).
7.1. Линейное программирование и паросочетания в двудольных графах (346).
7.2. Паросочетания и дробные паросочетания (354).
7.3. Политоп паросочетаний (355).
7.4. Хроматический индекс (368).
7.5. Политопы дробных паросочетаний и полиэдры покрытий (375).
7.6. Размерность политопа совершенных паросочетаний (376).
8. Определители и паросочетания (392).
8.0. Введение (392).
8.1. Перманенты (395).
8.2. Метод формальных переменных (401).
8.3. Пфаффиан и число совершенных паросочетаний (405).
8.4. Перечисление совершенных паросочетаний, базирующееся на вероятностном подходе (418).
8.5. Многочлены, перечисляющие паросочетания (422).
8.6. Еще о числе совершенных паросочетаний (435).
8.7. Два приложения в физических науках (440).
9. Алгоритмы построения паросочетаний (447).
9.0. Введение (447).
9.1. Алгоритм Эдмондса (448).
9.2. Взвешенные паросочетания (460).
9.3. Алгоритм, основанный на теореме Галлаи - Эдмондса (468).
9.4. Алгоритм линейного программирования для построения паросочетаний (472).
10. Задача об f-факторе (477).
10.0. Введение (477).
10.1. Принципы сведения (479).
10.2. Структурная теория f-факторов (482).
10.3. Задача о наборах степеней вершин графов (501).
11. Матроидные паросочетания (507).
11.0. Введение (507).
11.1. Формулировки задачи о матроидных паросочетаниях (508).
11.2. Основная теорема о полиматроидном паросочетаний (527).
11.3. Паросочетания в специальных полиматроидах (536).
12. Вершинные упаковки и покрытия (546).
12.0. Введение (546).
12.1. Критические графы (548).
12.2. Политопы вершинных упаковок (562).
12.3. Паросочетания в гиперграфах (573).
12.4. Вершинные упаковки в графах, не содержащих клешней (579).
Литература (593).
Предметный указатель (637).
Указатель обозначений (645).
ИЗ ИЗДАНИЯ: Книга известных специалистов по комбинаторике (Венгрия, США), охватывающая разнообразные области дискретной математики - задачу о коммивояжере, теорию потоков, модель Изинга ферромагнетизма, теорию матроидов и линейное программирование. В ней представлены как классические методы и алгоритмы, так и новые подходы и конструкции: NP-полнота, теоремы Бержа, Татта, Галлаи - Эдмондса и др. Книга имеет явно энциклопедический характер, отличается прикладной направленностью и требует лишь минимальной математической подготовки.
Для математиков разных специальностей - геометров, алгебраистов, специалистов по дискретной математике и кибернетике, для инженеров и программистов, а также аспирантов и студентов технических и экономических вузов. |
 |
