Избранные главы теории графов

Купить бумажную книгу и читать

Автор: Фрич Р., Перегуд Е.Е., Мациевский С.В.

Название: Избранные главы теории графов

Издательство: Калининград: Изд во Ргу им. И. Канта

Год: 2008

Формат: pdf

Размер: 6 mb

Для сайта:

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

Книга предназначена для изучения теории графов и некоторых смежных вопросов (раскраски карт, задачи коммивояжера) дискретной математики. Может быть использована на первых курсах высших учебных заведений.

Предисловие.

Избранные проблемы теории графов.

Введение. Задача о кёнигсбергских мостах. Основные понятия. Теоремы Эйлера. Алгоритм построения Эйлеровой цепи. Гамильтонов цикл. Орграфы. Подграфы, компоненты связности, подразбиения.

Планарные графы.

Плоские графы. Звездообразные полигоны. Максимально плоские графы. Теорема Вагнера и Фари. Теорема Эйлера о полиэдре и непланарные графы. Теорема Куратовского. Другие критерии планарности.

Дополнительные проблемы теории графов.

Теорема Менгера. Паросочетания. Взвешенные графы. Сети.

Np-полные задачи, задача коммивояжера.

Введение. Классы сложности задач. Задача коммивояжера. Метод ветвей и границ.

Задача о четырех красках.

Об истории. Раскраска карты стран. К теореме о четырех красках. Конфигурации. Карты стран на поверхностях.

Список литературы.

Популярная литература. Учебники. Монография.

Литература и оглавления.

Популярная литература. Учебники. Монография.

Краткая хронология.

Глоссарий.

Указатели.

Указатель обозначений. Именной указатель. Предметный указатель.