Фрич Р., Перегуд Е.Е., Мациевский С.В. Избранные главы теории графов

Под. ред. С. В. Мациевского. Пер. с нем. Е. Е. Перегуда.
Учебное пособие. — Калининград: Изд-во РГУ им. И. Канта, 2008.— 205 с.: ил. На обложке: гравюра старого Кёнигсберга со своими семью мостами.
В издании использованы три языка: русский, английский и немецкий.
Краткое учебное пособие по теории графов с алгоритмическим уклоном, которое соответствует желаниям русских и возможностям немецких преподавателей.
Книга предназначена для изучения теории графов и некоторых смежных вопросов (раскраски карт, задачи коммивояжера) дискретной математики. Может быть использована на первых курсах высших учебных заведений.
Замечания и предложения можно направлять по электронному адресу редактора matsievsky@newmail.ru.
Предисловие.
Избранные проблемы теории графов.
Введение. Задача о Кёнигсбергских мостах. Основные понятия. Теоремы Эйлера. Алгоритм построения Эйлеровой цепи. Гамильтонов цикл. Орграфы. Подграфы, компоненты связности, подразбиения.
Планарные графы.
Плоские графы. Звездообразные полигоны. Максимально плоские графы. Теорема Вагнера и Фари. Теорема Эйлера о полиэдре и непланарные графы. Теорема Куратовского. Другие критерии планарности.
Дополнительные проблемы теории графов.
Теорема Менгера. Паросочетания. Взвешенные графы. Сети.
Np-полные задачи, задача коммивояжера.
Введение. Классы сложности задач. Задача коммивояжера. Метод ветвей и границ.
Задача о четырех красках.
Об истории. Раскраска карты стран. К теореме о четырех красках. Конфигурации. Карты стран на поверхностях.
Список литературы.
Популярная литература. Учебники. Монография.
Литература и оглавления.
Популярная литература. Учебники. Монография.
Краткая хронология.
Глоссарий.
Указатели.
Указатель обозначений. Именной указатель. Предметный указатель.