ББК 22.174 Л43 УДК 519.17(075.8) Авторы: В. А. ЕМЕЛИЧЕВ, О. И. МЕЛЬНИКОВ, В. И. САРВАНОВ, Р. И. ТЫШКЕВИЧ Лекции по теории графов/Е м е л и ч е в В. А., Мельни- ков О. И., СарвановВ И., ТышкевичР И—М: Наука Гл. ред. физ.-мат. лит., 1990.—384 с.—ISBN 5-02-013992-0. Излагаются основы теории графов, обсуждаются некоторые известные проблемы. Приводятся примеры сведения прикладных задач к задачам теории графов и использования аппарата этой теории. Отдельная глава посвящена комбинаторным алгоритмам, связанным с поиском структурных и числовых характеристик гра^ фов. Каждая глава сопровождается упражнениями. Для студентов вузов, обучающихся по специальностям «Мате- матика» и «Прикладная математика». Табл. 1. Ил. 211. Библиогр. 32 назв. Рецензенты: 1. Кафедра математических методов исследования операций Воронежского государственного университета. 2. Кафедра теории исследования операций Ленинградского го- сударственного университета. ут 1602100000—110 „,о< 053(02)-90 "0""1 ISBN 5-02-013992-Q ©«Наука». Фпзматлит. 199ft Посвящается Дмитрию Алексеевичу СУПРУНЕНКО Предисловие В основу настоящего учебного пособия положены кур- сы лекций, которые читались авторами в Белорусском государственном университете им. В. И. Ленина для сту- дентов-математиков и в Белорусском политехническом институте для студентов, обучающихся по специальности «Прикладная математика». Изложение материала в кни- ге ставит своей целью дать в руки студентов орудие, применимое как к наукам о поведении (кибернетика, теория информации, теория систем, теория игр), так и ж теории множеств, теории матриц, теории групп и к другим чисто абстрактным дисциплинам. Основной зада- чей этого учебного пособия является ознакомление сту- дентов с теоретическими основами теории графов. Вме- сте с тем большое внимание уделяется вопросам приме- нения теории графов к решению прикладных задач и в связи с этим,— построению эффективных алгоритмов. Книга состоит из двенадцати глав. В главе I даны основные понятия теории графов. Об- суждается гипотеза Келли — Улама о реконструируемо- сти, вводятся регулярные, двудольные и реберные гра- <фы, изучается группа автоморфизмов графа. Глава за- канчивается результатами, характеризующими свойства графов при большом числе вершин. Эти свойства отра- жают в некотором смысле типичный случай и потому формулируются в терминах «почти всех» графов. Глава II посвящена деревьям и остовам. Она содер- жит матричную теорему Кирхгофа о деревьях и теорему Кэли о числе помеченных деревьев. В этой же главе из- лагаются и обосновываются алгоритмы Краскала и При- ма для решения задачи об остове минимального веса. Глава III содержит элементарное замкнутое изложе- ние основ теории матроидов и трансверсалей, специаль- но приспособленное к нуждам теории графов. Глава IV касается понятий независимости и покры- тия. При этом понятия вершинного и реберного покры- тий в идейном плане объединены. f 3 В главе V излагаются вопросы, связанные с вершин- ной и реберной связностью графа, которые имеют непо- средственное отношение к надежности и живучести раз- личных сетей. Особо выделены двусвязные графы. При- водятся новое краткое доказательство известной теоремы Менгера (1927 г.) о вершинном разделении графа, при- надлежащее В. Маквайгу, и критерий Уитни (1932 г.) А-связности графа. В главе VI приводятся критерии планарности графа Л. С. Понтрягина и К. Куратовского, X. Вагнера, С. Мак- лейна, X. Уитни, разбирается задача укладки графа на плоскости, даны некоторые характеристики непланарно- сти графа — род, толщина, число скрещиваний, иска- женность. Глава VII посвящена эйлеровым и гамильтоновым графам. Она открывается критерием существования эйле- рова цикла в графе. Далее приводятся разнообразные до- статочные условия гамильтоповости графа — результаты X. Уитни (1932 г.), У. Татта (1943 г.), Г. Дирака (1952 г.), О. Оре (1960 г.), В. Хватала (1972 г.) и др. В главе VIII исследуются степенные последователь- ности графов, т. е. списки степеней их вершин. Приво- дятся два критерия графичности последовательности на- туральных чисел — критерий Гавела — Хакими и крите- рий Эрдёша — Галлаи. Изучается процедура построения реализации графической последовательности с предпи- санными теоретико-графовыми свойствами. Исследуются классы графов, определяемые степенными последова- тельностями,— расщепляемые графы,' пороговые гра- фы. Последний класс графов связан с минимиза- цией числа линейных неравенств, задающих булеву функцию. В главе IX обсуждаются вопросы раскраски вершин и ребер графа. Здесь рассматривается знаменитая гипо- теза четырех красок, вводится и изучается важный класс графов — совершенные графы, излагается теорема Визин- га о реберной раскраске. Глава Х отведена ориентированным графам. Рассмат- риваются обходы и базы в ориентированном графе, де- тально исследуются пути. В главе XI излагается теория гиперграфов, которые являются естественным обобщением графов. Здесь рас- сматриваются циклы в гиперграфе, независимые множе- ства вершин гиперграфа. Особое внимание уделено зада- чам реализации гнперграфов различными типами графов. Подобные задачи возникают при проектировании интег- ральных схем. В главе XII вводится понятие полиномиального ал- горитма (именно такие алгоритмы подразумеваются в гл. I—XI при употреблении словосочетания «эффектив- ный алгоритм»). Глава содержит изложение двух алго- ритмов анализа графов — поиска в глубину и поиска в ширину. Исследуются задачи нахождения кратчайших пу- тей в графе, построения паросочетаний в двудольном графе, поиска кратчайшего остова во взвешенном графе. Дается введение в теорию Л^Р-полноты. Каждая глава книги иллюстрирована примерами све- дения прикладных задач к задачам теории графов и ис- пользования аппарата этой теории. Обсуждается связь теории графов с проблемами надежности, задачами со- ставления расписаний, передачи информации, выбора проекта, распределения оборудования, проектирования интегральных схем и коробок скоростей и т. д. Выявле- ны связи теории графов с другими разделами дискретной математики, такими, например, как математическая ло- гика, булево программирование, теория кодирования. Для доказательства теоретико-графовых теорем используется аппарат алгебры. Для целей тренировки в конце каждой главы поме- щены упражнения; все они носят учебный характер. За последние годы теория графов развилась в столь обширный самостоятельный раздел дискретной математи- ки, что невозможно изложить все основные направления этого раздела в одной книге ограниченного объема. По этой причине очень трудно очертить круг вопросов, ко- торые должны входить в учебное пособие для студен- тов-математиков. Очевидно, что в содержании настоящей книги отражены наши взгляды. Однако некоторые во- просы теории графов, привлекательные для нас, напри- мер, сети, транспортные сети, потоки в сетях и т. д., оказались за пределами этой книги, поскольку они тра- диционно входят в другие учебные курсы — такие как «Исследование операций», «Методы оптимизации», «Ди- скретная математика». Мы мало касались проблемы изо- морфизма графов, которой, на наш взгляд, должна быть посвящена отдельная книга. Терминология теории графов, к сожалению, еще не установилась. Попытки ряда авторов унифицировать обо- значения и упорядочить терминологию до сих пор не увенчались успехом. Поэтому мы вынуждены наряду с 5 основным термином, как правило, приводить в скобках другие, широко употребляемые в современной советской и зарубежной литературе по теории графов. В книге принята сквозная нумерация параграфов. Теоремы, утверждения, леммы, следствия и рисунки ну- меруются двумя числами: первое из них — это номер па- раграфа, а второе — их порядковый помер, причем нуме- рация — сквозная внутри параграфа. Начало и конец доказательства обозначаются симво- лами О и < соответственно. Следует сделать замечание относительно авторства приводимых теорем. В ряде случаев мы даем фамилии авторов и годы опубликования результатов, но большая часть теорем оказалась безымянной. Это, конечно, не оз- начает, что мы претендуем па авторство. На различных стадиях работы над книгой мы поль- зовались советами и замечаниями, высказанными многи- ми коллегами и нашими учениками. Среди них М. С. Га- ращук, Г. М. Гутин, В. Э. Зверович, И. Э. Зверович, С. Г. Инджеян, А. Н. Исаченко, М. М. Ковалев, В. П. Ко- зырев, Н. М. Корнеенко, А. Д. Коршунов, А. В. Косточ- ка, А. П. Крачковский, А. Г. Левин, Л. С. Мельников, В. А. Перепелица, К. Ф. Присакару, В. Л. Тюрин, А. А. Черняк. Всем им мы выражаем искреннюю благо- дарность. Мы от души благодарим рецензентов — коллективы кафедры математических методов исследования операций Воронежского государственного университета и кафедры теории исследования операций Ленинградского государ- ственного университета; в частности, мы благодарны про- фессору Н. Н. Петрову и доценту И. Б. Руссману. Их детальная и благожелательная критика во многом спо- собствовала улучшению первоначального текста книги. Мы благодарим также редактора книги А. Д. Вайнштей- на, внесшего ряд усовершенствований в текст. Мы особенно благодарны академику АН БССР Д. А. Супрупенко и члену-корреспонденту АН СССР С. В. Яблонскому за постоянную помощь, ценные сове- ты и поддержку. Введение Начало теории графов все единодушно относят к 1736 г., когда Л. Эйлер не только решил популярную в то время задачу о кенигсбергских мостах, но и нашел критерий существования в графе специального маршру- та (эйлерова цикла, как теперь его называют). Однако этот результат более ста лет оставался единственным результатом теории графов. Лишь в середине XIX века инженер-электрик Г. Кирхгоф разработал теорию деревь- ев для исследования электрических цепей, а математик А. Кэли в связи с описанием строения углеводородов решил перечислительные задачи для трех типов деревь- ев. К этому же периоду относится появление знамени- той проблемы четырех красок. Родившись при решении головоломок и заниматель- ных игр (задачи о шахматном коне, о ферзях, «круго- светное путешествие», задачи о свадьбах и гаремах и т. п.), теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, от- носящихся к широкому кругу проблем. Графы букваль- но вездесущи. В виде графов можно, например, интер- претировать схемы дорог и электрические цепи, геогра- фические карты и молекулы химических соединений, свя- зи между людьми и группами людей. За последние три десятилетия теория графов превра- тилась в один из наиболее бурно развивающихся разде- лов математики. Это вызвано запросами стремительно расширяющейся области приложений. В теоретико-гра- фовых терминах формулируется большое число задач, связанных с дискретными объектами. Такие задачи вол- 7 никают при проектировании интегральных схем и схем управления, при исследовании автоматов, логических це- пей, блок-схем программ, в экономике и статистике, хи- мии и биологии, в теории расписаний и дискретной опти- мизации. Таким образом, теория графов становится одной из существенных частей математического аппарата ки- бернетики, языком дискретной математики. В значитель- ной степени через теорию графов происходит ныне про- никновение математических методов в науку и технику. Все это привело к тому, что теория графов появилась и в учебных планах наших университетов и технических вузов. Глава I Начальные понятия § 1. Определение графа Термин «граф» впервые появился в книге выдающе- гося венгерского математика Д. Кёнига в 1936 г., хотя начальные задачи теории графов восходят еще к Эйлеру (XVIII в.). Пусть V — непустое множество, V^ — множество всех его двухэлементных подмножеств. Пара (V, Е), где Е— произвольное подмножество множества V^, называется графом (неориентированным графом). В этой книге рассматриваются только конечные гра- фы, т. е. множество V предполагается конечным, хотя в определении графа конечность этого множества не тре- буется. Элементы множества V называются вершинами графа, а элементы множества Е — ребрами. Итак, граф — это конечное множество V вершин и множество Е ребер, Е ^ F'2'. Множества вершин и ребер графа G обознача- ются символами VG и EG соответственно. Вершины и ребра графа называются его элементами. Число \VG\ вершин графа G называется его порядком и обознача- ется через \G\. Если \G\ = n, \EG\ = m, то G называют (га, m) -графом. Говорят, что две вершины и и v графа смежны, если множество {и, и} является ребром, и не смежны в про- тивном случае. Если е = {и, v} — ребро, то вершины и и и называют его концами. В этой ситуации говорят так- же, что ребро е соединяет вершины и и v. Такое ребро обозначается символом ии. Два ребра называются смежными, если они имеют об- щий конец. Вершина v и ребро е называются инцидентными, ес- ли v является концом ребра е (т. е. е=ии), и не ин- цидентными в противном случае. Заметим, что смежность есть отношение между одно- родными элементами графа, тогда как инцидентность яв- ляется отношением между разнородными элементами. Множество всех вершин графа G, смежных с некото- рой вершиной v, называется окружением вершины и ц обозначается через No(u) или просто N(v). Графы удобно изображать в виде рисунков, состоя- щих из точек и линий, соединяющих некоторые из этих точек. При этом точки соответствуют вершинам графа, а соединяющие пары точек линии — ребрам. В качестве иллюстрации рассмотрим граф G, изображенный на рис. 1.1. Это (5, 6)-граф, VG={i, 2, 3, 4, 5}, EG = {{1, 2}, {1, 5}, {2, 3}, {2, 4}, {2, 5), {4, 5}}. Вершины 1 и 2 Рис. 1.2 смежны, а 1 и 3 не смежны. Вершина 1 и ребро {1, 2} инцидентны. N(2)= {1, 3, 4, 5}. Приведем примеры некоторых графов специального вида. Граф G называется полным, если любые две его вер- шины смежны, т. е. EG=(VG)(2). Полный граф порядка Рис. 1.3 п обозначается символом Кп, число ребер в нем равно /"•I = -"-^——/ . На рис. 1.2 изображены графы Кп, п sS 5. Граф называется пустым, если в нем нет ребер. Пу- стой граф порядка п обозначается через Оц. На рис. 1.3 показаны простыв циклы Сп (га == 3, 4) и простые цепи Рп (п = 2, 3, 4). Очевидно, что Кг = Ру, Рис. 1.4 а Кз = Сз. На рис. 1.4 приведены два изображения про- стого цикла С&. 10 На рис. 1.5 изображены колеса Wn (п = 3, 4, 5). За- метим, что ТУз == К^ и I Wn \ = п + 1. На рис. 1.6 изображен граф Петерсена. Красивыми примерами являются графы пяти плато- новых тел (т. е. правильных многогранников): тетраэд- ра, куба, октаэдра, додекаэдра, икосаэдра (рис. 1.7). Ниже неоднократно используются термины «разбие- ние» и «покрытие». Набор подмножеств множества S на- зывается покрытием множества S, если объединение этих Рис. 1.5 Рис. 1.6 подмножеств совпадает с S. Покрытие называется раз- биением, если никакие два из входящих в него подмно- жеств не пересекаются. Граф называется двудольным, если существует такое разбиение множества его вершин на две части {доли), что концы каждого ребра принадлежат разным частям. Если при этом любые две вершины, входящие в разные доли, смежны, то граф называется полным двудольным. Полный двудольный граф, доли которого состоят из р и из q вершин, обозначается символом Кр_у. При р = 1 получаем звезду К\д. Очевидно, что К\^\ =- Кч = Ру, К\^ = = Рз, Кч,1=С\, На рис. 1.8 изображены звезда К\^, и полный двудольный граф 7?з,з- Заметим, что одна из долей двудольного графа мо- жет быть пустой. Так, 0\ — двудольный граф с одной пустой долей, Оч можно трактовать как двудольный граф с двумя одновершинными долями или как двудольный граф, одна из долей которого содержит две вершины, а другая является пустым множеством. Аналогично двудольным определяются k-долъный и полный k-долъный графы для k == 3, 4, ... На рис. 1.9 приведен трехдольный граф. Легко подсчитать число всех графов с фиксирован- ным множеством вершин V. Эти графы различаются сво- ими ребрами, и потому их число равно количеству под- (") множеств в F'2', т. е. 2'27, где га == |У|. Однако эти графы 11, Тетраэдр не всегда следует различать. Как в применениях тео- рии графов, так и в самой этой теории чаше существенно лишь то, что есть объекты (вершины графа) и связи между объектами (ребрами). С этих позиций графы, ко- торые получаются один из другого изменением наимено- ваний вершин, разумно не различать. Оформим эти со- ображения в виде следующего определения. Пусть G и Н — графы, а <р: VG -- VH — биекция. Ес- ли для любых вершин и и у графа G их образы (р(и) Куб Рис. 1.8 и (f(v) смежны в Н тогда и только тогда, когда и и v смежны в G, то эта биекция называется изоморфизмом графа G на граф Н. Если такой изоморфизм существует, то мы пишем G ^ Н (тогда и Н ^ G) и говорим, что гра- фы G и Н изоморфны. Например, три графа, представленные на рис. 1.10, изоморфны (почему?), а графы на рис. 1.11 не изоморф- ны (почему?). Вопрос о том, изоморфны ли два данных Рис. 1.10 графа, в общем случае оказывается сложным (см., на- пример, [18]). Очевидно, что отношение изоморфизма графов явля- ется эквивалентностью, т. е. оно симметрично, транзи- тивно и рефлексивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны. Изоморфные графы естественно отожде- ствлять, т. е. считать совпадающими (их можно изобра- зить одним рисунком). Они могли бы различаться конн- 13 ретной природой своих элементов, но именно это игно- рируется при введении понятия «граф». В некоторых ситуациях все же приходится различать изоморфные графы, и тогда полезно понятие «помечен- ный граф». Граф порядка п называется помеченным, если его вершинам присвоены некоторые метки, напри- мер, номера 1, 2, ..., п. Отождествив каждую из вер- шин графа с ее номером (и, следовательно, множество вершин—с множеством чисел {1, 2, ..., п}}, определим Рис. 1.11 равенство помеченных графов G и Н одного и того же порядка: G = Н тогда, когда EG == EH. На рис. 1.12 изо- бражены три разных помеченных графа. При необходимости подчеркнуть, что рассматривае- мые графы различаются лишь с точностью до изомор- физма, говорят: «абстрактный граф». Строго говоря, аб- 2 1 страктный (или непомеченный) граф — это класс изо- морфных графов. Число gn непомеченных графов порядка п определя- ется сложно. Известна формула Пойа gn дающая асимптотику числа gn- Эта формула означает, (")/ что две функции g(n}= gn и /(и) = 2\2// п\ асимптотиче- ски равны, т. е. lim g(n)/f(n) == 1 (см. книгу [29], 71->со где излагается целый ряд результатов, связанных с чис- лом графов, имеющих те или иные предписанные свой- ства). 44 Как отмечалось выше, верно Утверждение 1.1. Число In помеченных графов (^) порядка п равно 2 . Итак, число помеченных графов порядка п «пример- ио» в га! раз больше числа непомеченных. Этот факт кажется интуитивно ясным: существует ровно п\ поме- ток множества, состоящего из п вершин. Однако послед- нее отнюдь не означает, что из каждого непомеченного графа получается п\ помеченных. Например, все пометки пустого графа приводят к одному и тому же помеченно- му графу; простая цепь Рз порождает три, а не шесть помеченных графов (рис. 1.12). Но все же, как пра- вило, каждый непомеченный граф приводит к п\ поме- ченным графам. Для произвольного графа G следующим образом оп- ределяется дополнительный граф (или дополнение) G'. VG = VG, и любые две несовпадающие вершины Рис. 1.13 смежны в G тогда и только тогда, когда они не смежны в G (рис. 1.13). Очевидно, что G =3 G и G s= Н, если G ^ Н. Граф, изоморфный своему дополнению, называется самодополнительным. Например, /У], Р^ и Со — самодопол- нительпые графы. Самодополнитсльные графы составля- ют важный, хотя и экзотический, класс графов, опре- деленным образом связанный с проблемой распознавания изоморфизма графов (.см., например, [18]). Иногда приведенное выше определение графа оказы- вается недостаточным и приходится рассматривать бо- лее общие объекты, в которых две вершины могут сое- диняться более чем одним ребром. Так возникает поня- тие «мультиграф». Мультиграф—это пара (V. Е), где V—непустое множество (вершин), а Е—семейство под- 1Э множеств множества У2' (ребер). Употребление терми- на «семейство» вместо «множество» означает, что эле- менты множества У12' могут в Е повторяться, т. е. до- пускаются кратные ребра. Дальнейшее обобщение состоит в том, что кроме крат- ных ребер допускаются еще петли, т. е. ребра, соединя- ющие вершину саму с собой. Псевдограф — это пара (V, Рис. 1.14 Е), где V — непустое множество (вершин), a ? — неко- торое семейство неупорядоченных пар вершин (ребер), не обязательно различных. На рис. 1.14 изображены мультиграф и псевдограф. Изучаются также ориентированные графы. Тогда мно- жество F'2' двухэлементных подмножеств заменяется де- картовым квадратом У2, состоящим из упорядоченных пар элементов множества V. Итак, ориентированный Рис. 1.15 Рис. 1.16 граф (или орграф)—это пара (V, А), где V—множе- ство вершин, А — множество ориентированных ребер, ко- торые называются дугами, A s V2. Если a=(v\, v^)— дуга, то вершины v\ и УЗ называются ее началом и кон- цом соответственно. На рисунке дуги отмечаются стрел- ками, указывающими направление от начала к концу (см. рис. 1.15). Аналогично определяется ориентирован- ный мулътиграф (см. рис. 1.16). Рассматриваются также смешанные графы, у которых есть и дуги, и неориенти- рованные ребра. Для всех этих видов графов естественно вводится по- нятие изоморфизма как бдекции между множествами 16 вершин, сохраняющей смежность, кратности ребер, пет- ли и направления дуг. Графы в смысле нашего первого определения назы- ваются еще простыми (или обыкновенными). Хотя часто- для теории несущественно, какие из этих видов графов (простые, мульти- или псевдо-) рассматриваются, однако главный персонаж этой книги — простой граф. Ради со- кращения речи термин «граф» употребляется и в других ситуациях (например, вместо «мультиграф» или «ориен- тированный граф»), по подобные случаи либо специаль- но оговариваются, либо ясны из контекста. § 2. Подграфы Граф Н называется подграфом (или частью) графа G, если VH i= VG, EH = EG. Если Н — подграф графа G, то говорят, что Н содержится в G. Подграф Н называ- ется остовным подграфом (или фактором), если VH = = VG. Если множество вершин подграфа Н есть U,. а множество его ребер совпадает с множеством всех ре- бер графа G, оба конца которых принадлежат U, то Н 4 54545 2 3. Рис. 2.1 называется подграфом, порожденным (или индуцирован- ным) множеством U, и обозначается через G(U). На рис. 2.1 изображены граф G и три его подграфа Н\, Н^ и Нъ, среди которых Нз является остовным, а Нг — порожденным. Рассматриваются также подграфы, порожденные мно- жествами ребер. Для Е' '= EG множество ребер порож- денного подграфа G(E') совпадает с Е', а множество вер- шин — с множеством концов ребер из Е'. Важный класс подграфов составляют подграфы, по- лученные в результате удаления вершин. Пусть и — вер- шина графа G. Граф Gv = G — и получается из графа G в результате удаления вершины v и всех инцидентных ей ребер. Очевидно, что Gv=G(VG\v). На рис. 2.2 изо- В. А. Емеличев и др. . IT Теорема 10.3 (X. Уитнп, 1932 г.). Пусть G и Н — связные графы, |G|>4, |Я1>4 и L(G)^L(H). Тогда G ?^ Н и, более того, для всякого изоморфизма ср: L{G)-*- —- L(H) существует единственный изоморфизм ^: G -^ Я, индуцирующий (р, т. е. такой, что (р(е) == ^ (и) ^i (v) для любого ребра е == пи графа G. > Изоморфизм ср реберных графов L(G) и L(H) бу- дем рассматривать как биекцию EG -> EH между мно- жествами ребер графов G и II, при которой смежным реб- рам соответствуют смежные, а несмежным — несмежные. Лемма 10.4. Если ребра е, (i=l, r) составляют звезду К^г в графе G, то их образы (р(е;) составляют та- кую же звезду Ki,r в графе II. 1> Доказательство леммы. При г == 2 утверж- дение леммы верно по определению изоморфизма графов. Пусть г = 3 и ребра е\, ез, ез составляют в графе G звез- ду -Й'1,з. Поскольку граф G связен и порядок его более четырех, то в нем есть четвертое ребро е, смежное с каж- дым из ребер е; или точно с одним из них. Таким же свой- ством обладает ср(е) по отношению к ф(ег). Ребра (p(ci) составляют в графе Н либо звезду Ki,s, либо треугольник. Но ребро, смежное с каким-либо ребром треугольника, смежно ровно с двумя из ребер. Тем самым доказано, что ребра (р(е.) составляют звезду в графе Н. Нужное ут- верждение доказано для г = 3. Очевидно, что для г > 3 оно просто получается по индукции. <1 Поскольку отображение ср~1: L(H)->- L(G) также яв- ляется изоморфизмом реберных графов, то из предыду- щей леммы вытекает следующее утверждение: ребра е, (i = 1, г) составляют максимальную (относительно вклю- чения) звезду К\,т в графе G тогда и только тогда, когда их образы <р(е,) составляют максимальную звезду К\_т в графе Н. Итак, изоморфизм ср определяет биекцию между мно- жествами максимальных звезд графов G и Н. Очевидно, что в каждой из этих звезд более одного ребра, и потому в ней есть лишь одна центральная вершина. Максималь- ную звезду графа G с центром х обозначим через So (х). Очевидно, что если (p(So(x) )= 8н(х'), то соответствие •ф: х >->• х' является инъекцией множества всех вершин графа G, не являющихся концевыми, в аналогичное под- множество вершин графа Н. Из соображений симметрии следует, что ^ — бпекция. Теперь распространим действие отображения 'ф на концевые вершины графа G. Пусть v — одна из таких вер- 40 шин. В графе G есть смежная с ней вершина х степени большей, чем 1. Положим хи = е и выберем в звезде Sif(x') такое ребро е' =x'v', что (р(с)==е'. Покажем, что degi/=l. (1) Пусть это не так. Тогда в звезде Sn(v') есть ребро е^= == е . Следовательно, в звезде (р~1 (Su(u')) есть ребро е^ = cp^^i)! смежное с ребром е, но не входящее в So(x). По тогда вершина v — конец этого ребра и deg v ^ ^ 1. Равенство (1) доказано. Положив •ф(У)= и', получим инъекцию множества кон- цевых вершин графа G в множество концевых вершин графа Н. Из соображений симметрии теперь следует, что •ф — биекция. Итак, построена биекцпя г[з: VG ->- VH. Докажем, что эта биекция является графовым изоморфизмом. Сохраним обозначение SG (ж) и в том случае, когда deg ж = 1. В этой ситуации So (х) содержит одно ребро, инцидентное вер- шине х, и не является максимальной звездой. Смежность вершин жиг/в графе G означает, что звезды So (х) и Sa(y) имеют общее ребро. Поэтому (xy^EG)^(x'y'^ EH). Доказано, что 'ф: G ->- Н — изоморфизм графов. Из опре- деления отображения ip видно, что оно индуцирует (р, т. е. ф(е)== х'у' == '^(х)^(у) для любого ребра е = ху s EG. Существование нужного изоморфизма ip доказано. Остается доказать единственность. Пусть, напротив, есть два изоморфизма ^\ ^= г^, удовлетворяющих условию теоремы. Тогда ipi (д)^ ^(а) для некоторой вершины а е VG. Рассмотрим произвольное ребро е == ах в гра- фе G. Тогда Tpi (a)^i (ж) = (р(е) = ^-2(a)t2(a-), и, следовательно, тр2(ж)= ipi (а). Если deg a > 1 и ay — другое ребро G, то аналогично получаем ^2(у)= ^i(a)= =^2 (ж), что противоречит пнъективности ^2. Если же dega=l, то из •ф2(ж)= ipi (а) получаем deg х = 1, что противоречит связности G. <1 Известно, что не всякий граф является реберным, на- пример, звезда К\^ не есть реберный граф. (Характерп- зация реберных графов имеется в книге [7].) Однако класс реберных графов достаточно содержателей. Об этом свидетельствует, в частности, тот факт, что гипотеза ре- 41 берной реконструируемое™ произвольных графов эквива- лентна гипотезе вершинной реконструпруемости реберных графов. Приведем без доказательства следующую теорему. Теорема 10.5 (Р. Хеммпнджер, 1969 г.). Связный граф G с более чем тремя ребрами реберно реконструи- руем тогда и только тогда, когда реберный граф L(G} вершинно реконструируем. Отметим еще любопытную связь, существующую меж- ду матрицей инцидентности графа G и матрицей смеж- ности реберного графа L(G). Утверждение 10.6. Если I = I(G)—матрица ин- цидентности графа G и A =A(L(G))—матрица смежно- сти графа L(G), записанная при той же, что и I, нуме- рации ребер, то Г1 = А + 2Е, (2) где Е—единичная матрица порядка \EG\. \> Рассмотрим элемент произведения /т/, занимающий позицию (k, I): (7 -Оьг =27г)&7pг. Р Последняя сумма равна числу вершин графа G, инцидент- ных обоим ребрам с номерами k и I. При k •= I это число равно 2. Если k ^ I, то это число по определению есть эле- мент А» матрицы А. Равенство (2) доказано. < Следствие 10.7. Любой корень характеристиче- ского полинома всякого реберного графа не меньше, чем —2. > Пусть G — реберный граф. Тогда для него верно равенство (2). С другой стороны, пусть Ах == Кх для не- нулевого вектора х. Тогда Пх =(^+2) х (в силу равен- ства (2)). Теперь рассмотрим квадрат длины вектора 1х: \IxV = xтITIx =(К + 2)xтx=(\ + 2) Ы2. Следовательно, ^+2^0,^^— 2. < § 11. Группа автоморфизмов графа Характеристикой симметрии графа является его груп- па автоморфизмов. Произвольная подстановка (р на множестве вершин графа G, сохраняющая отношение смежности, т. е. такая, что образы (р(й) и ср(у) вершин и и v смежны тогда и только тогда, когда смежны сами вершины и и и, назы- вается автоморфизмом графа G. 42 Иными словами, автоморфизм графа — это изоморфизм графа на себя. Любой граф G имеет по меньшей мере один автомор- физм — тождественное преобразование е: VG ->- VG, при котором е(У)=у для любой вершины v. Очевидно, что если (р — автоморфизм графа G, то и обратная подстанов- ка (р~1 также является автоморфизмом, если же подста- новки ср и •Ф обе суть автоморфизмы, то и их произведение (рт|) — автоморфизм. Поэтому верно следующее (важное, хотя и очевидное) Утверждение 11.1. Множество всех автоморфиз- мов графа относительно операции умножения подстановок является группой. Группа автоморфизмов графа G обозначается через AutG. Очевидно также Утверждение 11.2. Всякий автоморфизм графа G является также автоморфизмом дополнительного гра- фа G, т. е. Aut G = Aut G. Поскольку среди двух графов G •si G хотя бы один яв- ляется связным, то в силу утверждения 11.2, когда мы имеем дело с группой автоморфизмов, достаточно рассмат- ривать лишь связные графы. Введем важное понятие орбиты группы подстановок. Пусть Г — произвольная группа подстановок на мно- жестве V. Определим на V бинарное отношение ~, поло- жив v, -- v для и, v е V тогда и только тогда, когда в Г существует такая подстановка s, что s(u)=v. Очевидно, что отношение ~ является отношением эквивалентности и, следовательно, множество V разбивается на классы эк- вивалентных элементов: все элементы, входящие в один класс, переводятся подстановками из группы Г друг в друга, а элементы из разных классов друг в друга не пе- реводятся. Эти классы называются орбитами группы Г. Разбиение множества вершин графа G на орбиты груп- пы Aut G — важная задача. В сущности, применение к графу автоморфизма означает перенумерацию его вер- шин, причем отношение смежности должно сохраняться. Поэтому для любого автоморфизма (р у вершины графа v и ее образа Пусть Г — группа порядка п > 1 (для п = 1 выше приводились примеры). Построим граф G описанным ни- же способом. В качестве исходного множества вершин возьмем множество всех элементов группы Г. Каждую упорядоченную пару (и, v) несовпадающих вершин сое- диним простой цепью Рщ, длины 3, добавляя всякий раз по две новые вершины Яи„ и Ьцс: Puv =(», вис, &„„, и). За- 44 тем к каждой из вершин uuv «приклеим» простую цепь Р(а, к, v) длины I (а, и, v), все вершины которой, исклю- чая а„,.,—новые. Аналогично построим цепи Р(Ъ, и, v) длины I (Ь, и, v). При этом будем соблюдать следующее условие: длины всех цепей попарно различны всегда, кро- ме случая, когда и^и == и^и^, и, v, ui, vi <= Г. В послед- нем случае должпо быть 1(а, и, v)=l(a, Mi, vi), l(b, и, v)-=I(b, щ, У)). (1) Построенный таким образом граф обозначим буквой G. (На рис 11.3 показаны соответствующие графы для Рпс. 11.3 п == 2 и 3. В этой ситуации Г — циклическая группа: Г ={у, v'1 == е} при п = 2, Г = {v, и2, v3 = е} при п = 3.) Докажем, что группы Aut G и Г изоморфны. Вначале 45 в) Докажите, что при т < п граф Gm является порождоппым подграфом графа Gn. 15. Докажите, что элемент матрицы (Л (С'))*, занимающий по- зицию (i, /), равен числу (г, /^-маршрутов длины k в графе G. 16. Постройте граф, центр которого: а) состоит ровно из одной вершины; б) состоит ровно из трех вершин и не совпадает с множеством всех вершин; в) совпадает с множеством всех вершин. 17. Докажите, что два графа, изображенные па рис, 6.2, ко- спектральны. 18. Матрица называется вполне унимодулярной, если каждый ее минор равен 1, —1 или 0. Докажите, что матрицы инцидептно- Рис. 1.1 Рис. 1.2 ста двудольного графа и ориентированного графа вполне упимо- дулярны. 19. Докажите, что диаметр графа не превосходит его удвоенно- го радиуса. 20. Приведите пример графа, диаметр и радиус которого равны. 21. Докажите, что (п, м)-граф связен, если в нем отсутст- вуют циклы нечетной длины и т > (п— l)2/^. 22. Является ли граф, изображенный на рис. 1.1, двудольным? 23. Найдите расстояние d(u, v} в графе, изображенном па рис. 1.2. 24. Докажите, что при п > 2 звезда К^п не является ребер- ным графом. 25. Найдите группы автоморфизмов графа, изображенного па рис. 11.5, простой цопи Рп, простого цикла Сп и графа Петерсена. Докажите, что группа автоморфизмов графа Петерсепа изоморфна симметрической группе iS'5. 26. Найдите граф минимального порядка, отличного от 1, с тождественной группой автоморфпзмов. 27. Докажите, что число помеченных графов, изоморфных не- которому графу G порядка п, равно ra!/|Aut<31. 28. Сколько помеченных графов порождают простая цепь Рп и простой цикл Сп? Глава II Деревья Как показано в § 4, среди графов с фиксированными порядком и числом компонент лишь один имеет макси- мальное число ребер. Другой крайний случай — мини- мальное число ребер — приводит к большому классу гра- фов. Наиболее важными среди них являются связные гра- фы, которые называются деревьями. Класс деревьев зани- мает в теории графов особое положение. С одной сторо- ны, это достаточно просто устроенные графы, и многие задачи, весьма сложные в общей ситуации, для деревьев решаются легко. Доказано, например, что все деревья ре- конструируемы; несложно распознается изоморфизм де- ревьев. С другой стороны, деревья часто встречаются в об- ластях, на первый взгляд не имеющих отношения к тео- рии графов. Деревья открывались независимо несколько раз. Ещо в прошлом веке Г. Кирхгоф ввел деревья и применил их к исследованию электрических цепей, а А. Кэли, пере- числяя изомеры насыщенных углеводоров, еще раз от- крыл деревья и первым исследовал их свойства. Тогда же деревья были введены и исследованы К. Жорданом как чисто математический объект. § 13. Определение дерева Деревом называется связный граф, не содержащий циклон. Любой граф без циклов называется ациклическим (пли лесом). Таким образом, компонентами леса являют- ся деревья. На рис. 13.1 изображены все деревья шестого порядка. Существует несколько вариантов определения дерева; некоторые из них отражены в следующей теореме. Теорема 13.1. Для (га, т}-графа G следующие ут- верждения эквивалентны: 1) G — дерево; 2) G — связный граф и m = п — i; 53 Глава III Матроиды и трансверсали В этой главе вводится новый комбинаторный объект — матроид, появляющийся в результате обобщения хорошо известного читателю понятия линейной зависимости. Хо- тя понятие «матроид» возникло относительно давно,— в 30-е годы нашего столетия (впервые это понятие ввел X. Уитнп)—место теории матроидов в математике и, тем более, в математическом образовании первоначально не было осознано. Теперь же, когда открываются все новые и новые классы матроидов, объединяющая роль идеи мат- роида, позволяющая с возрастающим успехом применять к решению комбинаторных проблем методы алгебры, ста- новится все более ясной. Для пас матроиды интересны, прежде всего, по двум причинам. Первая — их связь с теорией графов. Факти- чески, именно соответствие между некоторыми теоретико- графовыми и алгебраическими понятиями привело к со- зданию теории матроидов. Вторая причина состоит в том, что задачи оптимизации па матроидных структурах ре- шаются с помощью простого, так называемого «жадного» алгоритма, который является обобщением алгоритма Кра- скала для нахождения остовного дерева минимального веса в связном взвешенном графе (§ 15). «Жадный» ал- горитм изучается в этой главе. § 16. Азбука теории матроидов Известно несколько эквивалентных друг другу опре- делений матроида. Эти определения различаются тем, что учитывают различные свойства независимости. Начнем с определения, основанного па свойствах максимальных независимых множеств — баз. Матроидом М называется пара (Е, ^}, где Е — конеч- ное непустое множество, а И? (или д5(М))—непустое множество его подмножеств (называемых базами), удов- летворяющее следующим двум условиям {аксиомы баз). 64 B.I. Никакая из баз не содержится в другой базе. В.2. Если B{ и Да — базы, то для любого элемента Ъ е В\ существует такой элемент с е В^, что (В\\Ъ} U с —• также база. Элементы множества Е называются элементами мат- роида М. Число \Е\ называется порядком матроида М. Понятие матроида является естественным обобщением понятия линейной независимости. А именно, если Е — конечная система векторов некоторого линейного про- странства, содержащая ненулевой вектор, то в Е суще- ствует максимальная линейно независимая подсистема — база системы Е. Напомним, что все базы системы Е удов- летворяют аксиомам баз B.I и В.2. Следовательно, всякая такая система вместе с ее базами является матроидом. Этот матроид называется векторным. Очевидно, что в обозначениях аксиомы В.2 либо Ъ <= Вч и тогда можно взять с = Ъ, либо c<=B^\Bi, иное противо- речило бы аксиоме B.I. Поэтому совокупность аксиом B.I и В.2 равносильна совокупности аксиом B.I и В'.2. Если Bi, Вг^^ и be=Bi\Bs, то в 52\5i сущест- вует такой элемент с, что (В i\b) U с f= ?S. Утверждение 16.1. Все базы матроида равно- мощны. > Пусть Bi и В-г— базы, ]5]1 =s? \Bz\ и Bi = {61, Ьч.,... ..., bp}. Согласно аксиоме В.2 в базе В-г существует такой элемент ci, что 5'==(5i\bi)Ud={ci, &2, ..., Ър}е=^. Далее, существует такой элемент С2 е В^, что В" = (5'\Ь2) U C2 = {Cl, C2, Ьз, . . ., Ьр) е ^. Итерируя этот процесс, получим базу В = {с\, Cz, ..., Ср), являющуюся подмножеством в Вч и потому совпадаю- щую с 2?2 в силу B.I. Следовательно, \Вч\ = р. < Мощность базы матроида М назовем его рангом и обозначим через р(М). Любое подмножество базы матроида называется не- зависимым. В частности, пустое множество независимо. Совокупность всех независимых подмножеств элементов матроида М обозначим через У (М) (или просто Э}. Ни- же множество У{М) называется набором независимых множеств матроида М. Очевидно, что Ш(М} совпадает с множеством элемен- тов из У{М), максимальных относительно включения, так что множества S!{M) и 2f (M) определяют друг друга. 5 В. А. Емеличев и др. °° Список литературы ОСНОВНАЯ 1. Б е р ж К. Теория графов и ее применения,— М.: ИЛ, 1962.— 319 с. 2. 3 ы к о в А. А. Основы теории графов.— М.: Наука, 1987.— 381 с. 3. О р е О. Теория графов.— М.: Наука, 1980,— 336 с. 4. С в а м и М., Т х у л а с и р а м а п К. Графы, сети и алгорит- мы.— М.: Мир, 1984.— 454 с. 5. Т а т т У. Теория графов.— М.: Мир, 1988. 6.Уилсон Р. Введение в теорию графов.—М.: Мир, 1977.— 207 с. 7. X a pap и Ф. Теория графов.—М.; Мир, 1973—300 с. ДОПОЛНИТЕЛЬНАЯ 8. А и г пер М. Комбинаторная теория.—М.: Мир, 1982.—556 с. 9.Ахо X., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.—М.: Мир, 1979.—536 с. 10. Б а с а к е р Р., С а а т и Т. Конечные графы и сети.— М.: Наука, 1974—368 с. 11. Б е л о в В. В., В о р о б ь е в Е. М., Ш а т а л о в В. Е. Теория графов.—М.: Высшая школа, 1976.—392 с. 12. Г а в р и л о в Г. П., С а п о ж е н к о А. А. Сборник задач по дискретной математике.— М.: Наука, 1977.— 368 с. 13. Г э р и М., Джонсон Д. Вычислительные машины и труд- норешаемыо задачи.— М.: Мир, 1982.— 416 с. 14. Д о н е ц Г. А., Шор Н. 3. Алгебраический подход к пробле- ме раскраски плоских графов.— Киев: Наукова думка, 1982.— 143 с. 15. Е в с т и г н е е в В. А. Применение теории графов в програм- мировании.— М.: Наука, 1985.— 352 с. 16. Е в с т и г и е е в В. А., М е л ь н и к о в Л. С. Задачи и упраж- нения по теории графов п комбинаторике.— Новосибирск, Изд- во НГУ, 1981.- 88 с. 17. Е м е л и ч е в В, А., К о в а л е в М. М., К р а в ц о в М. К. Мно- гогранники, графы, оптимизация.— М.: Наука, 1981.— 341 с. 18. 3 е м л я ч е н к о В. Н., К о р н е е н к о Н. М., Тышкевич Р. И. Проблема изоморфизма графов // Теория сложности вычисле- ний, I. Записки научных семинаров ЛОМИ.—1982.—Т. 118.— С. 83-158. 19. 3 ы к о в А. А. Теория конечных графов.— Новосибирск, Нау- ка, 1969.— 543 с. 375 .Зыков А. А. Гиперграфы Ц УМН.— 1974.— Т. 29, вып. 6.— С. 89—154. .Коршунов А. Д. Основные свойства случайных графов с большим числом вершин и ребер // УМН.—1985.— Т. 40, вып. 1.—С. 107—173. .Крпстофпдес Н. Теория графов. Алгоритмический под- ход.— М.: Мир, 1978.— 432 с. .Маркус К., М и н к X. Обзор по теории матриц п матрич- ных неравенств.— М.: Наука, 1972.— 232 с. П а п а д и м и т р и у X., С т а и г л и ц К. Комбинаторная оп- тимизация. Алгоритмы и сложность.— М.: 1985.— 510 с. .Рейнгольд Э., Нивергельт Ю., Д е о Н. Комбинатор- ные алгоритмы. Теория и практика.— М.: Мир, 1980.— 476 с. Р и н г е л ь Г. Теорема о раскраске карт.—М.: Мир, 1977.— 256 с. С е р г и е н к о И. В. Математические модели и методы реше- ния задач дискретной оптимизации.— Киев: Наукова думка, 1985.—381 с. Теория графов: Сборник переводов/Под ред. В. Б. Алексеева, Г. П. Гаврилова, А. А. Сапоженко.— М.: Мир, 1974.— 223 с. Х a pap и Ф., Палмер Э. Перечисление графов.—М.: Мир, 1977.— 324 с. Холл М. Комбинаторика.—М.: Мир, 1970.—424 с. Цветкович Д., Дуб М., Захс X. Спектры графов. Тео- рия и приложения.— Киев: Наукова думка, 1984.— 381 с. Яблонский С. В. Введение в дискретную математику.— М : Наука, 1986.— 384 с. Предметный указатель Автоморфизм графа 42 Аксиомы баз 64 — независимости 66 — ранга 67 — циклов 67 Алгоритм детерминированный 367 — Дийкстры 343 — жадный 93 — Краскала 60 — линейный 322 — недетерминированный 367 — отыскания кратчайших путей 350 — поиска в глубину 325, 332 — — — ширину 348 — полиномиальный 322 — построения минимального остова 337, 340 — — наибольшего паросочетания 357 — — совершенного паросочетания 359 — Прима 61 — укладки графа на плоскости 178 — Флёри 195 База матроида 64 — орграфа 293 Базис коциклов матроида 81 — разрезов графа 84 — циклов графа 84 — — матроида 81 Валентность вершины 26 Вершина висячая 26 — доминирующая 26 — изолированная 26 — концевая 26 — периферийная 35 — центральная 36 Вес подграфа 36 — ребва 36 Вход задачи 321 Гиперграф 298 — абсолютный 307 — бихроматический 309 — двойственный 299 — /t-однородный 299 »— /t-униформвый 299 Гиперграф ft-раскрашиваемый 306 — fe-хроматический 306 — ft-цветвой 306 — связный 301 —, удовлетворяющий условию Хел- ли 311, 313 Гипотеза Бержа 272 — Келли — Улама 18 — Рамачандрана 286 вершинной — реконструируемости 18 — — реберной 18 — Хадвигера 264 — Харари 18 — четырех красок 255 Грани карты смежные 255 Граница грани плоского графа 153 Грань плоского графа 153 — — — внешняя 153 — — — внутренняя 153 Граф 9 — абстрактный 14 — ациклический 53 — бихроматический 237 — взвешенный 36 — внешнепланарный 189 — — максимальный 189 — выпуклый прямолинейный 163 — гамильтонов 196 — гамильтоново связный 207 — двойственный абстрактно 172 — — геометрически 169 — двудольный 11 — додекаэдра 11 — дополнительный 15 — икосаэдра 11 — клик 112 — конечный 9 — куба 11 — кубический 33 — неориентированный 9 — непомеченный 14 — обыкновенный 17 — однородный 32 — октаэдра 11 — ориентированный 16 — пересечений 38 — Петерсена 11 — планарный 150 — плоский 150 — — максимальный 158 — полный 10 — помеченный 14 — пороговый 224 — простой 17 — пустой 10 377 Граф раскрашиваемый реберно 248 — расщепляемый 222 — реберный 38, 311 — регулярный 33 — реконструируемый 18 — решетки 207 — самодополнительный 15 — сбалансированный 15 — связный 23 — смешанный 16 — совершенный 268 — тетраэдра 11 — тороидальный 184 — триангулированный 272 — эйлеров 192 — ft-дольный 11 — h-раскрашиваемый 235 — fe-связный 136 — fe-хроматический 236 Графы изоморфные 13 — коспектральные 29 — платоновых тел 11 Группа автоморфизмов графа 43 Дерево 53 — остовное 57 — г, корнем ориентированное 324 — Штейнера 62 Дефицит двудольного графа 128 Диаметр 35 Длина входа задачи 321 — маршрута 22 — списка 319 Игра «Кругосветное путешествие» 196 Изоморфизм графов 13 — матроидов 73 Индекс хроматический 248 Нскаженность графа 187 Каркас 55 Карта 255 — ft-раскрашиваемая 255 Класс цветной 238, 248 Клика 111 — максимальная til — наибольшая 111 Кобаза 68 Колесо 11 Колода графа 18 Компонента 24, 301 — базовая 293 — связная 24, 301 — сильная 282 — сильно связная 282 — fe-связная 136 Конденсация 282 Контур гамильтонов 286 Коостов 72 Коцикл 69 Критерий Гавела—Хакими 211 — Эрдёша — Галлаи 213 Куб п-мерный 20 Лемма о рукопожатиях 26 Лес 53 Лист 141 Емкость графа шенноновская 109 Задание графа списками смежно- сти 320 — — списком ребер 319 Задача коммивояжера 206 — об остове минимального веса 60 — о восьми ферзях 102 — — выполнимости 371 — — гаремах 90 — — кёнигсбергских мостах 191 — — кратчайшем остове 60 — — — пути 342 — — назначениях 124 — — пересечении матроидов 100 — — пяти ферзях 109 — — свадьбах 87 — — трех домах и трех колодцах 152 — проектирования коробки скорос- тей 237 — размещения минимаксная 36 — распознавательная 365 — распределения оборудования 236 — составления расписаний 236 — Штейнера евклидова 62 — — на графах 62 — — прямоугольная 62 — JVP-полная 370 — NP-трудная 373 Замыкание транзитивное 297 Звезда 11 Знак Магомета 192 378 Маршрут 22 — ориентированный 280 — остовный 281 Матрица весов 319 — инцидентности 31 — Кирхгофа 30 — клик 115 — смежности 27 — — приведенная 30 Матроид 64 — бинарный 79 — векторный 70, 74 — графический 74 — двойственный 69 — дискретный 70 — матричный 21 — однородный 100 — представимый 75 — разбиения 92 — разрезов графа 72 — свободный 70 — трансверсальный 92 — тривиальный 70 — циклов графа 72 Множество внутренне устойчивое 102 — графа степенное 232 — доминирующее 109 — — минимальное 109 — — наименьшее 109 — независимое 102, 304 — — максимальное 102 — — наибольшее 102, 304 Множество ребер графа независимое 122 — трансверсальное гиперграфа 303 — элементов матроида зависимое 67 — — — козависимое 69 — — — конезависимое 69 — — — независимое 66 Мост 134 Мультиграф 15 — ориентированный 16 Набор независимых множеств мат- роида 65 Неплотность графа 103 Область связности 24, 301 Обхват 22 Объединение графов 19 — — дизъюнктное 19 — матроидов 95 Окружение 10, 125 Оператор 318 — «конец» 319 — присваивания 319 Операция элементарная 318 Опора 111 Орграф 16 — гамильтонов 286 — односторонне связный 280 — односторонний 280 — реберный 297 — сильно связный 280 — слабо связный 281 — транзитивный 291 — эйлеров 286 Ориентация графа 32 Основание графа 283 Остов 55 Отец вершины ордерева 327 Отождествление вершин графа 21 Очередь 323 Пара векторов графическая 284 Паросочетание 122, 303 — максимальное 122 — наибольшее 122, 303 — совершенное 123 Петля 16 Плотность 111 Подграф 17 —— индуцированный 17 — остовный 17 — порожденный 17 Поддерево с корнем 327 Подразбиение ребра 160 Подцепь 22 Поиск в глубину 323 — — ширину 37 Покрытие вершинное 111 — — минимальное 111 — — наименьшее 111 — реберное 122 — — минимальное 122 — — наименьшее 122 Полином графа характеристиче- ский 29 — — хроматический 247 Полуконтур 280 Полумаршрут 280 Полупуть 280 Полустепень захода вершины 283 — исхода вершины 283 Полуцепь 280 Порядок гиперграфа 298 — графа 9 — матроида 65 Последовательность графа степен- ная 26 — графическая 209 — правильная 209 — производная 212 — расщепляемая 223 — угадывающая 367 — униграфическая 211 Потомок вершины ордерева 327 Предок вершины ордерева 327 Представление гиперграфа кёнигово 300 — матроида 75 — списка последовательное 319 Проблема изоморфизма графов 115 — изоморфного подграфа 115 — изоморфной вложимости 115 — Кёнига 47 — клики 115 Произведение графов 20 — — модульное 116 Пространство коциклов матроида 81 — разрезов графа 84 — циклов графа 84 — — матроида 81 Псевдограф 16 Путь в орграфе 280 Радиус графа 35 Разложение матроидное 120 — множества вершин полярное 222 — "пороговое 228 Размер входа задачи 321 Ранг графа 28 — коциклический 56 — матроида 65 — подмножества элементов матрои- да 67 — циклический 56, 303 Раскраска вершинная 235, 306 — минимальная 236 — последовательная 238 — правильная 235, 306 — реберная 248 Расстояние между вершинами 34 Расщепление вершины 22 Реализация гиперграфа 310 — — строгая 314 Реконструкция 18 Род графа 184 Сабли Магомета 192 Сепаратор 145 Система различных представителей 87 Слияние вершин 21 Сложность алгоритма 321 Спектр графа 29 Список 319 Стек 322 Степень вершины 26, 299 379 Степень графа 34 — — регулярного 32 — — сильная 108 — ребра 299 Структура данных 377 Стягивание ребра 21 Сын вершины ордерева 327 Толщина графа 186 Точка сочленения 134 — Штейнера 62 Трансверсаль 87 — независимая 88 — частичная 87 Триангуляция плоская 157 Трудоемкость алгоритма 321 Турнир 283 Тэта-граф 197 Укладка графа 151 Униграф 211 Фактор 17 Функция матроида коранговая 69 — — ранговая 67 Центр графа 36 Цепь 22, 300 Цепь диаметральная 35 — простая 22 Цикл 22 — гамильтонов 196 — матроида 67 — простой 22 — эйлеров 192 Часть графа 17 Число клиновое 111 — матроидное 120 — независимости 103, 304 — паросочетания 122, 303 — покрытия вершинного 111 — — кликового 112 — — реберного 122 — пороговое 228 — связности 133, 134 — скрещиваний 184 — Хадвигера 21 Эксцентриситет вершины 35 Ядро 294 ft-компопента 196 .'-процедура 212 га-последовательность 209 Оглавление Предисловие ..........•••• " Введение ..........•«••• ^ Глава I. НАЧАЛЬНЫЕ ПОНЯТИЯ ........ 9 § 1. Определение графа ......... 9 § 2. Подграфы ............ 17 § 3. Операции над графами ........ 1° § 4. Цепи, циклы, компоненты ....... 22 § 5. Степени вершин графа ........ 26 § 6. Матрицы, ассоциированные с графом .... 27 § 7. Регулярные графы ......... 32 § 8. Метрические характеристики графа .... 34 § 9. Критерий двудольности графа ...... 36 § 10. Реберный граф .......... 38 § 11. Группа автоморфизмов графа ...... 42 § 12. «Почти все» графы ......... 47 Упражнения ............. 51 Главе 11. ДЕРЕВЬЯ ............ 53 § 13. Определение дерева ......... 53 § 14. Матричная теорема Кирхгофа ...... 57 § 15. Остов минимального веса ......< 60 Упражнения ............. 63 Глава III. МАТРОИДЫ И ТРАНСВЕРСАЛИ ..... 64 § 16. Азбука теории матроидов ....... 64 § 17. Двойственный матроид ........ 68 § 18. Примеры матроидов ......... 70 § 19. Изоморфизм матроидов ........ 73 § 20. Представление матроида ....... 75 § 21. Бинарные матроиды ......... 79 § 22. Трансверсали ........... 87 § 23. Жадный алгоритм ......... 92 § 24. Объединение и пересечение матроидов ... 95 Упражнения ............. 100 Глава IV. НЕЗАВИСИМОСТЬ И ПОКРЫТИЯ .... 102 § 25. Независимые множества и покрытия .... 102 § 26. Клика ............. Ill § 27. Проблемы клики, изоморфной вложимости и изо- морфного подграфа ......... 115 § 28. Интерпретации независимых множеств , . . 117 § 29. Паросочетания , . . ....... 122 381 § 30. Паросочетания в двудольном графе . . . . 124 § 31. Двудольные графы и семейства подмножеств . 128 § 32. Паросочетапия и покрытия ....... 130 Упражнения . . . .......... 132 Глава V. СВЯЗНОСТЬ ........... 133 § 33. Вершинная связность и реберная связность . . 133 § 34. Двусвязные графы ......... 137 § 35. Теорема Менгера .......... 145 Упражнения ............. 148 Глава VI. ПЛАНАРНОСТЬ . . . ...... 150 § 36. Плоские и планарпые графы . ..... 150 § 37. Грани плоского графа. Формула Эйлера . . . 153 § 38. Плоские триангуляции ........ 157 § 39. Критерии планарности ........ 159 § 40. Двойственность и планарность ...... 169 § 41. Алгоритм укладки графа на плоскости . . . 175 § 42. Характеристики пепланарных графов .... 183 Упражнения ............. 187 Глава VII. ОБХОДЫ ........... 191 § 43. Эйлеровы графы .......... 191 § 44. Гамильтоновы графы . . . ..... 196 Упражнения ............. 207 Глава VIII. СТЕПЕННЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ . . 208 § 45. Графическая последовательность ..... 209 § 46. Критерии графичности последовательности . . 211 § 47. Реализация графической последовательности с мак- симальной связностью . . . . . . . . 217 § 48. Гамильтонова реализация графической последова- тельности ............ 220 § 49. Расщепляемые графы . . ...... 222 § 50. Пороговые графы .......... 223 § 51. Пороговое разложение графа ...... 228 § 52. Степенное множество графа ....... 232 Упражнения ............. 234 Глава IX. РАСКРАСКИ . . . ....... 235 § 53. Правильная раскраска ........ 235 § 54. Оценки хроматического числа ...... 238 § 55. Хроматический полином ........ 245 § 56. Раскраска ребер .......... 248 § 57. Связь матроидных разложений графов с раскраска- ми .............. 252 § 58. Раскраска планарных графов ...... 255 § 59. Проблема четырех красок ....... 260 § 60. Другие подходы к раскраске графов .... 264 § 61. Совершенные графы ......... 267 § 62. Триангулированные графы ....... 272 Упражнения ............. 277 Глава X. ОРИЕНТИРОВАННЫЕ ГРАФЫ . . ... 279 § 63. Основные определения ........ 279 § 64. Полустепени исхода и полустепени захода . . 283 382 § 65. Обходы ............. 286 § 66. Пути ............. 290 § 67. База и ядро . . ......... 293 Упражнения ............. 296 Глава XI. ГИПЕРГРАФЫ .......... 298 § 68. Основные определения и свойства ..... 298 § 69. Независимые множества ........ 304 § 70. Раскраски ............ 306 § 71. Реализации гиперграфа ........ 310 Упражнения ............. 315 Глава XII. АЛГОРИТМЫ .......... 317 § 72. Предварительные сведения ....... 317 § 73. Поиск в глубину .......... 323 § 74. Отыскание двусвязных компонент ..... 327 § 75. Минимальный остов ......... 334 § 76. Кратчайшие пути . . . ...... 342 § 77. Наибольшие паросочетания и задача о назначениях 354 § 78. Труднорешаемые задачи . . . .... 364 Упражнения ............. 373 СПИСОК ЛИТЕРАТУРЫ .......... 375 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ......... 377 Учебное издание ЕМЕЛИЧЕВ Владимир Алексеевич МЕЛЬНИКОВ Олег Исидорович САРВАНОВ Владимир Иванович ТЫШКЕВИЧ Регина Иосифовна Лекции по теории графов Заведующий редакцией Е. Ю. Хован Редактор А. Д. Вайнштейн Художественный редактор Т. Н. Нолъченко Технический редактор С. Я. Шкллр Корректоры О. А. Бутусова, И. Я. Нришталь ИБ Н 32506 Сдано в набор 10.05.89, Подписано к печати 04.10.90. Формат 84Х108/32. Бумага тип. .Ni 2. Гарнитура обыкновенная. Печать высокая. Усл. печ. л. 20,16. Усл. кр.-отт. 20,16. Уч.-изд. л. 20,99. Тираж 22 000 экз. Заказ М 666. Цена 1 р. Издательско-гроизводственное и книготорговое объединение «Наука» Главная редакция физико-математической литературы 117071 Москва В-71, Ленинский проспект, 15 Четвертая типография издательства «Наука» 630077 Новосибирск, 77, Станиславского, 25