Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов Изд. 5, испр.

Отзывы

Президент Республики Беларусь, рассмотрев материалы, представленные Комитетом по Государственным премиям Республики Беларусь, постановляет: присудить Государственную премию Республики Беларусь за учебники: Емеличеву Владимиру Алексеевичу, Мельникову Олегу Исидоровичу, Сарванову Владимиру Ивановичу, Тышкевич Регине Иосифовне – за работу "Учебное пособие "Лекции по теории графов" для высших и средних специальных заведений".

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

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

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

Авторы книги смогли сочетать удачную организацию включенного материала с лаконичностью и прозрачностью изложения строгих математических утверждений. Удачны также выбор, концептуальное понимание и изложение основных тем, важных для приложений.

В книге хорошо сочетаются стиль изложения, понятный студентам, с большим объемом информации, которая требуется специалистам. При этом отражено современное состояние теории, включены все важные достижения последних лет.

Книга обладает многими педагогическими достоинствами. Читается она как-то "сразу". Ясный и четкий язык, строгая логическая последовательность суждений, уместное употребление графических иллюстраций заслуживают высокой оценки. Из огромного числа фактов теории графов авторы выбрали совокупность, необходимую и достаточную для того, чтобы служить ее основой.

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

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

Работа носит во многом оригинальный характер, как по стилю изложения, так и по результатам. Ее выпуск – это заметное событие в создании отечественной учебной и научной литературы по теории графов.

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

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

Сочетание классических результатов с наиболее важными последними достижениями дают прекрасную возможность использовать учебник не только для изучения предмета, но и для организации научно-исследовательской работы студентов.

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

Книга написана с незаурядным педагогическим мастерством и отличным знанием предмета. Уровень изложения вполне доступен широкому кругу студентов, строгость в доказательстве важных теорем сочетается с вниманием к изложению мотивировок.

Книга является важным подспорьем для всех, кто работает в теории графов, для начинающих и для опытных исследователей.

Учебник является образцом полноты изложения. Он особенно важен студентам и лекторам, которые желают повысить свое образование.

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

Оглавление

Предисловие

В основу настоящего учебного пособия положены курсы лекций, которые читались авторами в Белорусском государственном университете им.В.И.Ленина для студентов-математиков и в Белорусском политехническом институте для студентов, обучающихся по специальности "Прикладная математика". Изложение материала в книге ставит своей целью дать в руки студентов орудие, применимое как к наукам о поведении (кибернетика, теория информации, теория систем, теория игр), так и к теории множеств, теории матриц, теории групп и к другим чисто абстрактным дисциплинам. Основной задачей этого учебного пособия является ознакомление студентов с теоретическими основами теории графов. Вместе с тем большое внимание уделяется вопросам применения теории графов к решению прикладных задач и в связи с этим, – построению эффективных алгоритмов.

Книга состоит из двенадцати глав.

В главе I даны основные понятия теории графов. Обсуждается гипотеза Келли–Улама о реконструируемости, вводятся регулярные, двудольные и реберные графы, изучается группа автоморфизмов графа. Глава заканчивается результатами, характеризующими свойства графов при большом числе вершин. Эти свойства отражают в некотором смысле типичный случай и потому формулируются в терминах "почти всех" графов.

Глава II посвящена деревьям и остовам. Она содержит матричную теорему Кирхгофа о деревьях и теорему Кэли о числе помеченных деревьев. В этой же главе излагаются и обосновываются алгоритмы Краскала и Прима для решения задачи об остове минимального веса.

Глава III содержит элементарное замкнутое изложение основ теории матроидов и трансверсалей, специально приспособленное к нуждам теории графов.

Глава IV касается понятий независимости и покрытия. При этом понятия вершинного и реберного покрытий в идейном плане объединены.

В главе V излагаются вопросы, связанные с вершинной и реберной связностью графа, которые имеют непосредственное отношение к надежности и живучести различных сетей. Особо выделены двусвязные графы. Приводятся новое краткое доказательство известной теоремы Менгера (1927 г.) о вершинном разделении графа, принадлежащее В.Маквайгу, и критерий Уитни (1932 г.) k-связности графа.

В главе VI приводятся критерии планарности графа Л.С.Понтрягина и К.Куратовского, X. Вагнера, С.Маклейна, X. Уитни, разбирается задача укладки графа на плоскости, даны некоторые характеристики неплапарности графа – род, толщина, число скрещиваний, искаженность.

Глава VII посвящена эйлеровым и гамильтоновым графам. Она открывается критерием существования эйлерова цикла в графе. Далее приводятся разнообразные достаточные условия гамильтоновости графа – результаты X. Уитни (1932 г.), У.Татта (1943 г.), Г.Дирака (1952 г.), О.Оре (1960 г.), В.Хватала (1972 г.) и др.

В главе VIII исследуются степенные последовательности графов, т.е. списки степеней их вершин. Приводятся два критерия графичности последовательности натуральных чисел – критерий Гавела–Хакими и критерий Эрдёша–Галлаи. Изучается процедура построения реализации графической последовательности с предписанными теоретико-графовыми свойствами. Исследуются классы графов, определяемые степенными последовательностями, – расщепляемые графы, пороговые графы. Последний класс графов связан с минимизацией числа линейных неравенств, задающих булеву функцию.

В главе IX обсуждаются вопросы раскраски вершин и ребер графа. Здесь рассматривается знаменитая гипотеза четырех красок, вводится и изучается важный класс графов – совершенные графы, излагается теорема Визинга о реберной раскраске.

Глава X отведена ориентированным графам. Рассматриваются обходы и базы в ориентированном графе, детально исследуются пути.

В главе XI излагается теория гиперграфов, которые являются естественным обобщением графов. Здесь рассматриваются циклы в гиперграфе, независимые множества вершин гиперграфа. Особое внимание уделено задачам реализации гиперграфов различными типами графов.

Подобные задачи возникают при проектировании интегральных схем.

В главе XII вводится понятие полиномиального алгоритма (именно такие алгоритмы подразумеваются в гл.I–XI при употреблении словосочетания "эффективный алгоритм"). Глава содержит изложение двух алгоритмов анализа графов – поиска в глубину и поиска в ширину. Исследуются задачи нахождения кратчайших путей в графе, построения паросочетаний в двудольном графе, поиска кратчайшего остова во взвешенном графе. Дается введение в теорию NP-полноты.

Каждая глава книги иллюстрирована примерами сведения прикладных задач к задачам теории графов и использования аппарата этой теории. Обсуждается связь теории графов с проблемами надежности, задачами составления расписаний, передачи информации, выбора проекта, распределения оборудования, проектирования интегральных схем и коробок скоростей и т.д. Выявлены связи теории графов с другими разделами дискретной математики, такими, например, как математическая логика, булево программирование, теория кодирования. Для доказательства теоретико-графовых теорем используется аппарат алгебры.

Для целей тренировки в конце каждой главы помещены упражнения; все они носят учебный характер.

За последние годы теория графов развилась в столь обширный самостоятельный раздел дискретной математики, что невозможно изложить все основные направления этого раздела в одной книге ограниченного объема. По этой причине очень трудно очертить круг вопросов, которые должны входить в учебное пособие для студентов-математиков. Очевидно, что в содержании настоящей книги отражены наши взгляды. Однако некоторые вопросы теории графов, привлекательные для нас, например, сети, транспортные сети, потоки в сетях и т.д., оказались за пределами этой книги, поскольку они традиционно входят в другие учебные курсы – такие как "Исследование операций", "Методы оптимизации", "Дискретная математика". Мы мало касались проблемы изоморфизма графов, которой, на наш взгляд, должна быть посвящена отдельная книга.

Терминология теории графов, к сожалению, еще не установилась. Попытки ряда авторов унифицировать обозначения и упорядочить терминологию до сих пор не увенчались успехом. Поэтому мы вынуждены наряду с основным термином, как правило, приводить в скобках другие, широко употребляемые в современной советской и зарубежной литературе по теории графов.

В книге принята сквозная нумерация параграфов. Теоремы, утверждения, леммы, следствия и рисунки нумеруются двумя числами: первое из них – это номер параграфа, а второе – их порядковый номер, причем нумерация – сквозная внутри параграфа.

Следует сделать замечание относительно авторства приводимых теорем. В ряде случаев мы даем фамилии авторов и годы опубликования результатов, но большая часть теорем оказалась безымянной. Это, конечно, не означает, что мы претендуем на авторство.

На различных стадиях работы над книгой мы пользовались советами и замечаниями, высказанными многими коллегами и нашими учениками. Среди них М.С.Гаращук, Г.М.Гутин, В.Э.Зверович, И.Э.Зверович, С.Г.Инджеян, А.Н.Исаченко, М.М.Ковалев, В.П.Козырев, Н.М.Корнеенко, А.Д.Коршунов, А.В.Косточка, А.П.Крачковский, А.Г.Левин, Л.С.Мельников, B. А.Перепелица, К.Ф.Присакару, В.Л.Тюрин, А.А.Черняк. Всем им мы выражаем искреннюю благодарность.

Мы от души благодарим рецензентов – коллективы кафедры математических методов исследования операций Воронежского государственного университета и кафедры теории исследования операций Ленинградского государственного университета; в частности, мы благодарны профессору Н.Н.Петрову и доценту И.Б.Руссману. Их детальная и благожелательная критика во многом способствовала улучшению первоначального текста книги. Мы благодарим также редактора книги А.Д.Вайнштейна, внесшего ряд усовершенствований в текст.

Мы особенно благодарны академику АН БССР Д.А.Супруненко и члену-корреспонденту АН СССР C. В.Яблонскому за постоянную помощь, ценные советы и поддержку.

Об авторах

Емеличев Владимир Алексеевич

Доктор физико-математических наук, профессор Белорусского государственного университета, лауреат Государственной премии Республики Беларусь. Действительный член Нью-Йоркской академии наук, член редколлегий ряда международных научно-теоретических журналов в России, Украине и Молдове. Научные интересы — дискретная оптимизация, полиэдральная комбинаторика, теория графов, анализ устойчивости многокритериальных дискретных задач. Автор и соавтор нескольких монографий и учебных пособий.

Мельников Олег Исидорович

Профессор механико-математического факультета Белорусского государственного университета, доктор педагогических наук, кандидат физико-математических наук. Научные интересы: теория графов, обучение дискретной математике в высшей и средней школе. Лауреат Государственной премии Республики Беларусь.

Сарванов Владимир Иванович

Кандидат физико-математических наук, заведующий отделом Института математики Национальной академии наук Беларуси. Лауреат Государственной премии Республики Беларусь. Научные интересы: теория графов, дискретная оптимизация, комбинаторная вычислительная геометрия. Автор и соавтор нескольких учебных пособий.

Тышкевич Регина Иосифовна

Доктор физико-математических наук, профессор Белорусского государственного университета. Лауреат Государственной премии Республики Беларусь. Заслуженный работник народного образования Беларуси. Основатель белорусской школы теории графов. Научные интересы — теория графов, дискретная оптимизация, комбинаторный анализ. Автор и соавтор нескольких монографий и учебных пособий. Награждена медалью Франциска Скорины.