Математика

Эйлеровы графы и смежные вопросы

год издания — 2002, кол-во страниц — 335, ISBN — 5-03-003115-4, 0-444-88395-9, тираж — 3000, язык — русский, тип обложки — твёрд. 7БЦ, масса книги — 555 гр., издательство — Мир

цена: 500.00 руб

Eulerian Graphs and
Related Topics
Herbert Fleischner
Institute for Information Processing
Austrian Academy of Sciences
Vienna, Austria
Elsevier Science Publishers B.V., 1990

Пер. с англ. В. А. Евстигнеева, А. В. Косточки и Л. С. Мельникова

Формат 70x100 1/16. Печать офсетная

Монография известного австрийского математика посвящена теории эйлеровых графов — одному из интенсивно развивающихся разделов теории графов. Это первая монография по данной теме. В книге собраны как классические, так и современные результаты в этой области, уделено внимание алгоритмическим вопросам, сформулирован ряд нерешённых проблем. Изложение сопровождается большим количеством примеров и графических иллюстраций. В книгу включена впервые переведённая на русский язык основополагающая статья Эйлера 1736 г., посвящённая известной задаче о кёнигсбергских мостах.

Книга будет полезна как специалистам в различных областях математики, так и всем, кто применяет теорию графов.

От редактора перевода	5
Предисловие	8
Глава I. Введение	11
Глава II. Три столпа теории эйлеровых графов	15
Решение одной задачи, связанной с геометрией положения	16
О возможности обхода линейного комплекса без повторений и прерываний	33
Из «Analysis situs» О. Веблена	38
Глава III. Основные понятия и предварительные результаты	39
III.1. Смешанные графы и их основные части	40
III.2. Некоторые связи между графами и (смешанными) (ор)графами. Подграфы	45
III.З. Графы, получающиеся из заданного графа	50
III.4. Маршруты, цепи, пути, циклы, деревья; связность	53
III.5. Совместимость, циклический порядок множества К_v^* и соответствующие эйлеровы цепи	72
III.6. Паросочетания, 1-факторы, 2-факторы, 1-факторизации, 2-факторизации, двудольные графы	75
III.7. Вложение графов в поверхности; изоморфизмы	81
III.8. Раскраска плоских графов	89
III.9. Гамильтоновы циклы	92
III.10. Матрицы инцидентности и смежности, потоки и напряжения	97
III.11. Алгоритмы и их сложность	100
III.12. Заключительные замечания	102
Глава IV. Характеризационные теоремы и их следствия	104
IV.1. Графы	104
IV.2. Орграфы	110
IV.3. Смешанные графы	113
IV.4. Упражнения	119
Глава V. Некоторые возможные обобщения	121
V.I. Разложения на цепи, путевые/цикловые разложения	121
V.2. Результаты о чётности	122
V.3. Двойные проходы	124
V.4. Пересечение границы: расщепления графов	124
V.5. Упражнения	126
Глава VI. Различные типы эйлеровых цепей	127
VI.1. Эйлеровы цепи, избегающие некоторых переходов	127
VI.2. Попарно совместимые эйлеровы цепи	155
VI.3. A-цепи в плоских графах	183
VI.4. Упражнения	266
Глава VII. Преобразования эйлеровых цепей	270
VII.1. Преобразование произвольных эйлеровых цепей в графах	271
VII.2. Преобразование эйлеровых цепей специального типа	276
VII.3. Преобразование эйлеровой цепи в орграфах	304
VII.4. Заключительные замечания и некоторые открытые проблемы	309
VII.5. Упражнения	311
Список литературы	314
Предметный указатель	329

Книги на ту же тему

Теория графов, Оре О., 1968
Теория графов, Харари Ф., 1973
Ориентированные графы и конечные автоматы, Мелихов А. Н., 1971
Графы, сети и алгоритмы, Свами М., Тхуласираман К., 1984
Группы и их графы, Гроссман И., Магнус В., 1971
Теория просачивания для математиков, Кестен X., 1986
Введение в прикладную комбинаторику, Кофман А., 1975
Анализ алгоритмов. Вводный курс, Макконнелл Д., 2002
Дискретная математика для программистов, Хаггарти Р., 2004
Введение в дискретную математику, Яблонский С. В., 1979
Экстремальные задачи дискретной математики: учебник, Канцедал С. А., 2016
Комбинаторные задачи и (0, 1)-матрицы, Тараканов В. Е., 1985
Графы и их применение, Оре О., 1965
Алгоритмы решения экстремальных задач, Романовский И. В., 1977

http://knigoprovod.ru

/Наука и Техника/Математика

ОГЛАВЛЕНИЕ

Книги на ту же тему