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

Летии по ТЕОРИИ ДоггуЮено Государственным «аиитетом СССР по пародногзу образованию в качестве учебного пособия для студентов, обучаюи1ихся по специал»нос»язв еМатемагика» и «Прикладная математика г МОСКВА «НАУКА» ГЛАВНАЯ РЕДАКИИЯ гРЯЗИКО-МАТЕМАТИЧЕСКОЙ 11ИТЕ1гАТУРЫ 1990 ББК 22Л74 л.з УД11 519.17 (075.8) Л в т о р ы: В. Л. ЕМЕЛИЧЕВ, О. И. МЕЛЬНИКОВ, В.

И. СЛРВЛНОВ, Р. И. ТЫШКЕВИт! Рецепзепты: !. Кафедра математпческих иетодов исследования операцию Воронежского государственного укиверситета. 2. Кафедра теории исследовапия операций Лепипградского государствеппого упиверситета. © впаувзз Фвзмэтлат гзэп Ч 1602100000 — ИО 35 9 053(02)-90 18ВЯ 5-02-013992-0 Лекции по теории графов/Е м е л и ч е в В. А., М е л ь в иков О И, Сер ванов В, И,, Тышкевич Р, И,— Мл Наука Гл, ред, физ.-мат, лиг,, 1990,— 334 с,— !ЯВИ 5-02-013992-0. Излагаются основы теории графов, обсуждаются некоторые. извествые проблемы.

Приводятся примеры сведения прикладных задач к задачам теории графов и использования аппарата этой теории. Отдельная глава посвящена комбинаторным алгоритмам, свлзанным с поиском структурвых и числовых характеристик графов. Каждая глава сопровождается упражпеяиямп. Для студентов вузов, обучающихся по специальностям аМатоматпказ и чПрпкладная математикат. Табл. 1. Ил. 211. Бполиогр. 32 каза. Посвящается Дмитрию Алексеевичу СУПРУНЕНКО Предисловие В основу настоящего учебного пособия положены курюы лекций, которые читались авторами в Белорусском государственном университете им.

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

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

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

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

С. Понтрягина и К. Куратовского, Х. Вагнера, С. Маклейпа, Х. Уитни, разбирается задача укладки графа на плоскости, даны некоторые характеристики непланарпости графа — род, толщина, число скрещиваний, искаженность. Глава УП посвящена эйлеровым и гамильтоновым графам. Она открывается критерием существования эйлерова цикла в графе.

Далее приводятся разнообразные достаточные условия гампльтоновости графа — результаты Х. Уитни (1932 г.), У. Татта (1943 г.), Г. Дирака (1952 г.), О. Оре (1960 г.), В. Хватала (1972 г.) и др. В главе УП1 исследуются степенные последовательности графов, т. е. списки степеней их вершин. Приводятся два критерия графичности последовательности натуральных чисел — критерий Гавела — Хакими и критерий Эрдеша — Галлаи. Изучается процедура построения реализации графической последовательности с предписанными теоретико-графовыми свойствами, Исследуются классы графов, определяемые степенными последовательностями,— расщепляемые графы, пороговые графы.

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

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

1 — Х1 при употреблении словосочетания «эффективный алгоритм»). Глава содержит изложение двух алгоритмов анализа графов — поиска в глубину и поиска в ширину. Исследуются задачи нахождения кратчайших путей в графе, построения паросочетаяий в двудольпом графе, поиска кратчайшего остова во взвешенном графе. Дается введение в теорию УР-полноты. Каждая глава кпиги иллюстрирована примерами сведения прикладных задач к задачам теории графов и использования аппарата этой теории.

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

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

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

леммы, следствия и рисунки нумеруются двумя числами: первое из них — зто номер параграфа, а второе — их порядковый номер, причем нумерация — сквозная внутри параграфа. Начало и конец доказательства обозначаются символами > и З соответственно. Следует сделать замечание относительно авторства приводимых теорем. В ряде случаев мы даем фамилии авторов и годы опубликования результатов, по большая часть теорем оказалась безымянной.

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

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

Их детальная и благожелательная критика во многом способствовала улучшению первоначального текста книги. Мы благодарим также редактора книги А. Д. Вайнштейна, внесшего ряд усовершенствований в текст. Мы особенно благодарны академику ЛН БССР Д. Л. Супруяепко и члену-корреспонденту ЛН СССР С. В. Иблонскому за постоянную помощь, ценные советы н доллер>яку. Введение Начало теории графов все единодушно относят к т736 г., когда Л. Эйлер не только решил популярную в то время задачу о кенигсбергских мостах, но и нашел критерий существования в графе специального маршрута (эйлерова цикла, как теперь его называют).