Введение в теорию графов

В последние годы теория графов, являясь важным математическим инструментом в таких разнообразных областях знаний, как исследования операций, химия, социология или генетика, стала самостоятельным предметом. Книга «Введение в теорию графов» Робина Уилсона широко используется в качестве учебника для бакалаврата по математике, информатике и экономике, а также в качестве введения в предмет для не математиков.Вводные главы представляют собой базовый курс, содержащий определения и примеры. В них рассматриваются связность, эйлеровы и гамильтоновы пути и циклы, а также деревья. Далее следуют две главы о планарных графах и раскраске графов с отдельным рассмотрением проблемы четырех красок. Следующая глава посвящена теории трансверсалей и связности с приложениями к сетевым потокам. Последняя глава по теории матроидов связывает воедино материал предыдущих глав. В приложении обсуждаются алгоритмы и их эффективность.Текст этого нового издания был тщательно пересмотрен, а некоторые разделы были реорганизованы и перенумерованы.Добавлен новый материал, в частности относящийся к доказательству теоремы о четырех красках, к укреплению прямоугольных каркасов и к алгоритмам. Увеличено количество упражнений и представлено больше решений, чем ранее.Об автореРобин Уилсон — заслуженный профессор математики в Открытом университете и заслуженный профессор геометрии в Грешем-колледже в Лондоне. Ранее работал в Кебл-колледже в Оксфордском университете, а сейчас преподает в Пемброк-колледже. Он известный популяризатор математики, написавший и отредактировавший почти 40 книг по теории графов, комбинаторике, истории математики и музыки.Отзывы экспертов:»Отличное введение в популярную тему».— Г. Джонс, Саутгемптонский университет»Если бы этой книги не было, ее нужно было бы написать!»— Б. Купер, Университет Лидса»Я всегда считал книгу Уилсона незаменимым учебником по теории графов для студентов».— Д. Шарп, Университет ШеффилдаОглавление книги Робин Уилсон «Введение в теорию графов»Предисловие 10Введение 12Глава 1. Определения и примеры 21Глава 2. Пути и циклы 50Глава 3. Деревья 86Глава 4. Планарность 111Глава 5. Раскраска графов 137Глава 6. Паросочетания, свадьбы и теорема Менгера 171Глава 7. Матроиды 193Приложение 1. Алгоритмы 209Приложение 2. Количества графов 213Условные обозначения 214Список литературы 215Решения к избранным упражнениям 218Предметный указатель 236