МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
ОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
им. Ф.М. Достоевского
В.П. Ильев
ТЕОРИЯ ГРАФОВ
ВВОДНЫЙ КУРС
Учебное пособие
Омск
2012
ОМСКОГО ГОСУДАРСТВЕННОГО
УНИВЕРСИТЕТА
ИЗДАТЕЛЬСТВО

УДК 519.1
ББК 22.176я73
И457
Рекомендовано к изданию
редакционно-издателъским советом ОмГУ
Рецензенты
доктор физ.-мат. наук, профессор В.А. Романьков,
доктор физ.-мат. наук В.В. Сервах
И457 Ильев, ВЛ.
Теория графов. Вводный курс: учебное пособие
/ В.П. Ильев. - Омск: Изд-во Ом. гос. ун-та, 2012. -
80 с.
ISBN 978-5-7779-1527-6
Рассматриваются основные понятия, известные классические
утверждения и задачи теории графов. Приведён теоретический
материал и упражнения для практических занятий первой части
учебного курса «Теория графов и комбинаторные алгоритмы».
Для студентов математических специальностей очной формы
обучения.
УДК 519.1
ББК 22.176я73
ISBN 978-5-7779-1527-6
© В.П. Ильев, 2012
© Оформление. ФГБОУ ВПО
«ОмГУ им. Ф.М. Достоевского», 2012

Содержание
Введение 5
Упражнения 14
1. Маршруты, цепи, циклы 16
1.1. Определение графа. Примеры 16
1.2. Маршруты и метрика в графах 18
1.3. Эйлеровы циклы и цепи 20
1.4. Гамильтоновы циклы и цепи 23
Упражнения 25
2. Основные понятия и факты 29
2.1. Степени вершин графа 29
2.2. Изоморфизм графов. Помеченные и непомеченные
графы 30
2.3. Подграфы. Восстановление графов 33
2.4. Проблема изоморфизма. Инварианты графов .... 34
2.5. Связные и несвязные графы 38
2.6. Плоские и планарные графы 41
Упражнения 44
3. Деревья 47
3.1. Деревья и их свойства 47
3.2. Перечисление деревьев 49
3.3. Центр дерева 50
3.4. Изоморфизм деревьев 52
Упражнения 55
4. Связность 58
4.1. Вершинная и рёберная связность 58
4.2. k-связные графы. Критерии 2-связности 59
4.3. Отделимость и соединимость. Теорема Менгера . . 62
4.4. Рёберный аналог теоремы Менгера 67
Упражнения 68
3

5. Ориентированные графы 70
5.1. Основные понятия 70
5.2. Достижимость и связность 72
5.3. Эйлеровы и гамильтоновы орграфы 74
5.4. Ориентированные варианты теоремы Менгера ... 76
5.5. О проблеме восстановления орграфов 76
Упражнения 77
Список литературы 79
4

Введение
А. Возраст теории графов и её место в математике
Начиная разговор о какой-либо теории как математической дис-
циплине, было бы правильно определить ее возраст и место среди
других наук. Однако, в случае с теорией графов сделать это не
так-то просто.
Возьмём возраст. С одной стороны, теория графов относитель-
но молода, поскольку сформировалась как самостоятельная на-
ука только в середине XX в. Сам термин «граф» (от греческо-
го γραφω — пишу, черчу, рисую) получил распространение лишь
в 30-е гг. прошлого века, до тех пор использовались самые раз-
ные термины: «схема», «диаграмма», «карта», «сеть» и т. д. Тер-
мин «граф» окончательно закрепился в литературе после выхо-
да в свет в 1936 г. книги замечательного венгерского математика
Д. Кёнига «Теория конечных и бесконечных графов» [2] — первой
книги по теории графов.
С другой стороны, все исследователи единодушно сходятся в
том, что годом рождения теории графов следует считать 1736 г.,
когда был опубликован знаменитый трактат Л. Эйлера о Кё-
нигсбергских мостах [1] — первая публикация по теории графов.
Непросто также определить к какой области математики отне-
сти теорию графов. Всю математику принято делить на «чистую»
и «прикладную». Это деление весьма условно; так как некоторые
ее разделы входят сразу в обе части, — например, дискретная ма-
тематика (не связанная с предельным переходом, она оперирует
конечными или счётными множествами). Как говорил академик
С.Л. Соболев: «Нет чистой математики и прикладной математи-
ки, а есть математика и ее приложения».
Одни авторы считают теорию графов ветвью геометрии, по-
скольку графы — это геометрические объекты с присущими им
типично геометрическими атрибутами типа вершин, рёбер, гра-
ней, диаметра, связности, планарности и т. д. Другие однозначно
5

относят теорию графов к прикладной математике, мотивируя это
тем, что изначально графы были придуманы и применяются для
решения задач, имеющих практические приложения и возника-
ющих в физике, химии, электротехнике, экономике, социологии,
биологии и других областях.
Правы, видимо, и те, и другие. В 5-томной математической эн-
циклопедии [10] теория графов определяется как область дискрет-
ной математики, особенностью которой является геометрический
подход к изучению объектов.
Б. Из истории теории графов
Итак, «отцом» теории графов считается крупнейший математик
XVIII столетия (и, несомненно, один из величайших математиков
всех времён и народов) Л. Эйлер (1707-1783), написавший в 1736 г.
свое знаменитое рассуждение о Кёнигсбергских мостах [1]. Эйлер
в то время жил в Санкт-Петербурге, служил академиком в Пе-
тербургской Академии наук и, несмотря на молодость, был уже
довольно известным в Европе математиком.
В своём трактате Эйлер решил знаменитую задачу о кё-
нигсбергских мостах. В то время это была популярная голово-
ломка, которая привлекла внимание учёных разных стран. Что
это за задача?
Задача о кёнигсбергских мостах. Эйлеровы циклы
Вот выдержки из письма Эйлера итальянскому математику и
инженеру Мариньони, отправленному из Санкт-Петербурга в мар-
те 1736 г. (цитируется по книге [11]).
«Некогда мне была предложена задача об острове, расположен-
ном в городе Кенигсберге и окружённом рекой, через которую пе-
рекинуто семь мостов. Спрашивается, может ли кто-нибудь непре-
рывно обойти их, проходя только однажды через каждый мост. И
тут же мне было сообщено, что никто ещё до сих пор не смог это
проделать, но никто и не доказал, что это невозможно. Вопрос
6

этот, хотя и банальный, показался мне, однако, достойным вни-
мания тем, что для его решения недостаточны ни геометрия, ни
алгебра, ни комбинаторное искусство...
После долгих размышлений я нашёл лёгкое правило, основан-
ное на вполне убедительном доказательстве, с помощью которого
можно во всех задачах такого рода тотчас же определить, может
ли быть совершен такой обход через какое угодно число и как
угодно расположенных мостов или не может. Кёнигсбергские же
мосты расположены так, что их можно представить на следую-
щем рисунке, на котором А обозначает остров, а, В, С и D — части
континента, отделённые друг от друга рукавами реки» (рис. 1).
Рис. 1 Рис. 2.
Эйлер решил задачу о Кёнигсбергских мостах, хотя никогда не
бывал в Кёнигсберге (ныне российский город Калининград). Мало
того, он указал общие условия разрешимости или неразрешимости
задач подобного рода.
Чтобы прояснить математическую сущность задачи, Эйлер по-
ступил следующим образом: он изобразил участки суши точками,
а мосты — линиями, соединяющими эти точки. В результате по-
лучилась схема, изображённая на рис. 2. Такую схему называют
графом. Точки А, В, С и D называются вершинами, а отрезки
линий — рёбрами графа.
Теперь задача может быть сформулирована так:
Дан граф. При каких условиях существует маршрут, начинаю-
щийся и оканчивающийся в одной и той же вершине (т. е. замкну-
тый) и проходящий ровно один раз по каждому ребру?
Такой маршрут сейчас называют эйлеровым циклом, а граф,
7

содержащий эйлеров цикл — эйлеровым графом.
Рассмотрим связный граф (т. е. такой граф, в котором для
любых двух вершин существует маршрут, соединяющий их). Оче-
видно необходимое условие существования эйлерова цикла в лю-
бом графе: каждая вершина должна быть концом чётного число
рёбер (в этом случае говорят, что любая вершина имеет чётную
степень). Это условие не выполнено для графа, изображающего
кёнигсбергские мосты, следовательно, задача неразрешима.
Самое главное — Эйлер доказал, что это условие является до-
статочным для существования эйлерова цикла в любом связном
графе!
Теорема 1 (Эйлер). В связном графе существует эйлеров
цикл, если и только если все его вершины имеют чётную сте-
пень.
По поводу найденного им способа решать подобные задачи Эй-
лер писал:
«... Это решение по характеру своему, по-видимому, имеет мало
отношения к математике, и мне непонятно, почему следует скорее
от математика ожидать этого решения, чем от какого-нибудь дру-
гого человека, ибо это решение подкрепляется одним только рас-
суждением и нет необходимости привлекать для нахождения это-
го решения какие-либо законы, свойственные математике. Итак, я
не знаю, каким образом получается, что вопросы, имеющие совсем
мало отношения к математике, скорее разрешаются математика-
ми, чем другими».
Понятно, что Эйлер имел в виду современную ему математи-
ку первой половины XVIII столетия. Он сам и создавал новую
математику — дискретную!
Зададим себе вопрос: станет ли задача о кёнигсбергских мостах
разрешимой, если построить еще один мост? Ответ будет отри-
цательным, так как, добавив любое ребро, мы только уменьшим
число вершин нечётной степени в графе на рис. 2 с 4 до 2, и граф
8

все равно останется не эйлеровым. Однако, в нем уже будет суще-
ствовать незамкнутый маршрут, проходящий по каждому ребру
ровно один раз. Такой маршрут называется эйлеровой цепью, а
граф, содержащий эйлерову цепь, — полуэйлеровым.
Как следствие теоремы 1 можно получить критерий существо-
вания эйлеровой цепи в связном графе, также доказанный Эйле-
ром в его трактате о Кёнигсбергских мостах.
Следствие 1 (Эйлер). В связном графе существует эйле-
рова цепь тогда и только тогда, когда все его вершины за ис-
ключением, быть может, двух имеют четную степень.
Заметим, что неверно было бы формулировать следствие 1 без
оговорки «быть может». Ведь если все вершины имеют чётную
степень, то эйлерова цепь тоже существует (нужно взять эйлеров
цикл и удалить из него любое ребро).
Игра «Вокруг света». Гамильтоновы циклы
В XVIII-XIX вв. теория графов не получила должного разви-
тия, графы применялись в основном для решения занимательных
задач. Вот еще одна из них.
В 1859 г. известный математик, королевский астроном Ирлан-
дии сэр У. Гамильтон (1805-1865) (кстати, иностранный член-
корреспондент Петербургской Академии наук с 1837 г.) придумал
игру «Вокруг света». В его игре требовалось найти маршрут, про-
ходящий через все вершины додекаэдра так, чтобы побывать в
каждой вершине ровно один раз и вернуться назад (в вершинах
были написаны названия городов разных стран). Такой маршрут
теперь принято называть гамильтоновым циклом Граф, содер-
жащий гамильтонов цикл, называется гамильтоновым графом
Гамильтонов цикл существует далеко не во всяком графе. На
рис. 3 изображён самый простой негамильтонов граф, а граф на
рис. 4 — гамильтонов.
9

Постановки задач об эйлеровом цикле и о гамильтоновом цикле
очень похожи. Однако, задача о гамильтоновом цикле гораздо бо-
лее сложна, чем задача об эйлеровом цикле. В отличие от задачи
поиска эйлерова цикла до сих пор не найден критерий существо-
вания гамильтонова цикла в связном графе, и это несмотря на то,
что эта задача является одной из центральных в теории графов.
Более того, не известен также алгоритм поиска гамильтонова
цикла, который работал бы существенно более быстро, чем алго-
ритм полного перебора всех вариантов.
Задача о четырёх красках
В XIX в. была придумана ещё одна занимательная задача, ко-
торой суждено было стать одной из самых известных проблем не
только теории графов, но и всей математики. По степени популяр-
ности она уступает, пожалуй, лишь знаменитой проблеме Ферма
о разрешимости диофантова уравнения хп + уп = zn, решённой
Э. Уайлзом в конце XX в.
Около 1850 г. (более точная дата неизвестна) студент Универ-
ситетского колледжа в Лондоне Ф. Гутри обнаружил, что для рас-
краски карты графств Англии достаточно четырёх цветов (граф-
ства, имеющие общую границу, должны быть окрашены в разные
цвета). Он предположил, что четырёх цветов достаточно для рас-
краски любой плоской карты. Поразмыслив какое-то время над
этой гипотезой, Гутри пришёл с ней к своему профессору, извест-
ному шотландскому математику и логику А. де Моргану (1806-
10

1871), ставшему впоследствии первым президентом Лондонского
математического общества. Сохранилось письмо де Моргана сво-
ему другу и коллеге сэру У. Гамильтону, датированное октябрем
1852 г., в котором де Морган сообщал, что студент Гутри спра-
шивал его о проблеме четырёх красок, и что ему (де Моргану)
не удалось её решить. Это письмо является первым известным
документом, относящимся к задаче о четырёх красках (впрочем,
имеются сообщения, что проблему четырёх красок сформулиро-
вал Мёбиус ещё в 1840 г. [15]).
Следующий документ — заметка в Трудах Лондонского мате-
матического общества за 1878 г. В ней сообщается, что замеча-
тельный английский математик, профессор Кембриджского уни-
верситета А. Кэли (1821-1895) в своём выступлении перед членами
Лондонского математического общества между прочим сообщил,
что он не смог решить проблему четырёх красок. В 1879 г. бы-
ло опубликовано первое из многочисленных ошибочных решений,
ошибку в котором только в 1890 г. обнаружил английский матема-
тик П. Хивуд. Тогда же Хивуд доказал, что любая плоская карта
может быть раскрашена пятью красками.
Проблема четырёх красок считается задачей теории графов,
потому что её удобно формулировать на языке графов. Каждая
плоская карта порождает граф, вершины которого соответствуют
странам, и две вершины соединены ребром, если соответствующие
страны имеют общий участок границы. Рёбра в таких графах не
пересекаются вне вершин. Графы на плоскости, обладающие этим
свойством, называют плоскими. Для плоских графов задача о че-
тырёх красках может быть сформулирована так:
Задача о четырёх красках. Доказать или опровергнуть,
что вершины любого плоского графа можно правильно раскра-
сить четырьмя красками, т. е. раскрасить таким образом, что-
бы соседние вершины были окрашены в разные цвета.
Гипотеза четырёх красок состояла в том, что каждый плос-
кий граф можно правильно раскрасить четырьмя красками.
11

В XX в. интерес к данной проблеме продолжал возрастать. В
начале века известный американский математик Дж. Биркгоф
изучал свойства плоских графов, вершины которого нельзя пра-
вильно раскрасить в 4 цвета. В 1920 г. Ф. Франклин доказал, что
любой плоский граф, имеющий не более 25 вершин, можно пра-
вильно раскрасить в 4 цвета. Позже число вершин было увеличено
до сотни.
Важнейший шаг на пути решения проблемы был сделан в
1969 г. X. Хеешем, который свёл проблему 4 красок к исследова-
нию конечного множества U так называемых неустранимых кон-
фигураций. Он доказал, что в любом плоском графе G найдётся
подграф G', изоморфный некоторой конфигурации из U и такой,
что если G можно правильно раскрасить в 4 цвета, то это же
верно и для графа G. Количество неустранимых конфигураций,
вначале огромное, позже было уменьшено примерно до полутора
тысяч, что позволило использовать для их исследования компью-
теры.
В 1976 г. американские математики К. Аппель и В. Хакен объ-
явили о решении проблемы четырёх красок. Они сообщили, что
коллективу математиков и программистов под их руководством
удалось правильно раскрасить в 4 цвета все неустранимые конфи-
гурации, затратив на это около 2000 часов работы мощной ЭВМ.
Это первое в истории «машинное» доказательство чисто матема-
тического результата частью математического сообщества было
подвергнуто жёсткой критике и до сих пор признано не всеми
математиками. Позже Аппель и Хакен опубликовали алгоритми-
ческую версию доказательства (содержащую более 700 страниц),
в которой учли многие критические замечания в свой адрес.
В. Приложения теории графов
Уже в XIX в. графы стали применяться для решения практиче-
ских задач. Так, в 1857 г. уже известный нам английский матема-
12

тик А. Кэли применял графы при решении практических задач
органической химии. Он стремился перечислить изомеры предель-
ных углеводородов Cfc#2fc+2 с данным числом А: атомов углерода.
Некоторые из таких углеводородов показаны на рис. 5.
Η
Н-С-Н
I
Η
метан
• I ·
•—· ·
• 1 ·
• · ·
• φ ·
·—·—·
• · ·
•—·—·
т -1 φ
• ♦ ·
• ♦ 1—·
Ι ·
• i—·
этан
пропан
Рис. 5.
бутан изобутан
Такие связные графы без циклов называют деревьями. Кэли,
как математик, сформулировал задачу абстрактно: найти число
всех деревьев с η вершинами, каждое из которых имеет только
вершины степеней 1 и 4.
Впрочем, ещё ранее, в 1847 г. немецкий физик Г. Кирхгоф при-
менял деревья для расчета силы тока в электрических цепях. При
составлении полной системы уравнений для токов и напряжений
в электрической схеме он предложил представлять эту схему в ви-
де графа и находить в этом графе остовные деревья, с помощью
которых выделяются линейно независимые системы контуров и
находится значение силы тока в каждом контуре.
Практических задач, которые удобно решать с помощью гра-
фов, накапливалось все больше. Мощный толчок теории графов
дало развитие систем коммуникаций (железных дорог, сетей свя-
зи и т. д.), естественными моделями которых являются графы. В
начале XX в. теория графов стала постепенно оформляться в са-
мостоятельную математическую дисциплину. В математических
журналах публиковались всё новые и новые исследования, так
или иначе связанные с графами, и в 1936 г. вышла в свет первая
книга по теории графов [2].
13

В настоящее время теория графов находит широкие примене-
ния в различных областях человеческой деятельности, таких как
автоматика, электротехника, химия, биология, экономика, социо-
логия и многие другие.
Основу данного учебного пособия составляет курс лекций, в
течение многих лет читаемых автором студентам-математикам в
Омском государственном университете. При подготовке пособия
использованы монографии, учебники и другие источники, приве-
дённые в списке литературы. В конце каждой главы помещены
упражнения, предлагаемые студентам на практических занятиях
для лучшего усвоения теоретического материала. Все упражнения
носят учебный характер.
Упражнения
1. В компании 4 человека, каждый из которых знаком не ме-
нее, чем с двумя из остальных. Можно ли эту компанию рассадить
за круглым столом так, чтобы по обе стороны от каждого чело-
века сидели его знакомые?
2. Та же задача, но в компании 5 человек.
3. Найти все негамильтоновы 5-вершинные графы, степени
всех вершин в которых не меньше 2.
4. В компании 5 человек, каждый из которых знаком не ме-
нее, чем с тремя из остальных. Можно ли эту компанию рассадить
за круглым столом так, чтобы по обе стороны от каждого чело-
века сидели его знакомые?
5. Та же задача, но в компании б человек.
6. Доказать, что в любой компании из б человек всегда най-
дутся либо трое попарно знакомых, либо трое попарно незнако-
мых.
7. В любой ли компании из 5 человек найдутся либо трое
попарно знакомых, либо трое попарно незнакомых?
14

8. Наименьшее целое число г = г(т,п), для которого каж-
дый граф с г вершинами содержит либо полный га-вершинный
подграф, либо пустой η-вершинный подграф, называется числом
Рамсея (т, η ^ 2). Найти числа г(3,2), г(4,2), г(3,3).
9. Доказать, что в любой компании число тех, кто знаком с
нечётным числом членов компании, четно.
10. У короля 20 придворных. В результате интриг любые
двое придворных либо в ссоре друг с другом, либо друзья. Од-
ному из придворных стало известно, что королю надоели белые
парики и он хотел бы видеть чёрные. Придворный тут же сооб-
щил эту новость всем своим друзьям, те — своим друзьям и т. д.
Назавтра все, кто узнал эту новость, явились в чёрных париках.
Но узнали не все и часть придворных были в белых париках. Раз-
разился грандиозный скандал, в результате которого все друзья
перессорились, а все те, кто был в ссоре, наоборот, помирились.
Однако, чёрные парики показались королю чересчур мрачны-
ми и он сказал тому же придворному, что хорошо бы заменить их
на рыжие. Есть ли гарантия что ситуация не повторится?
11. Каждый из участников турнира встретился по одному ра-
зу со всеми остальными участниками, причём ни одна встреча не
закончилась вничью. Доказать, что среди спортсменов найдётся
такой, кто назовёт всех остальных участников турнира, если ста-
нет перечисляить тех, кого победил он сам, и тех, у кого выиграли
побеждённые им соперники.
12. На каждой из планет некоторой системы находится астро-
ном, наблюдающий ближайшую планету. Расстояния между пла-
нетами попарно различны. Доказать, что если число планет нечёт-
но, то какую-нибудь планету никто не наблюдает.
15

1. Маршруты, цепи, циклы
1.1. Определение графа. Примеры
Граф (неориентированный) состоит из непустого конечного мно-
жества V и конечного множества Ε неупорядоченных пар элемен-
тов из V (записывается G = (V, Е)). Элементы множества V = Vq
называются вершинами, а элементы множества Ε = Eq — рёбра-
ми графа G. Те и другие называются элементами графа.
Другими словами, неориентированный граф G — это па-
ра множеств (V,E), где V — непустое конечное множество,
а Е = {{и, ν} для некоторых и, ν Ε V}, причём возможно, что
какие-то пары {и, ν} присутствуют в Ε более одного раза и что в
некоторых парах и = v.
В дальнейшем будем опускать определение «неориентирован-
ный» и называть неориентированный граф просто графом.
Если {и, υ} £ Ε, то будем записывать е = uv и говорить, что
вершины и и ν смежны, а вершина и и ребро е инцидентны (так
же, как вершина υ и ребро е). Два ребра назваются смежными,
если они имеют общую вершину.
Степенью вершины ν в графе G называется число рёбер, ин-
цидентных вершине ν (обозначается <Iq{v) или d(v), если ясно, о
каком графе идёт речь).
Обычно граф изображается в виде схемы, на которой вершины
представлены точками, а рёбра — отрезками линий, соединяющи-
ми соответствующие точки. Такую схему называют геометриче-
ским представлением графа
Заметим, что по определению в графе могут быть кратные рёб-
ра, т. е. два и более ребра, соединяющие одну и ту же пару вер-
шин, и петли, т. е. рёбра, соединяющие вершины сами с собой.
Граф, в котором имеются кратные рёбра, называется мультигра-
фом, а граф без петель и кратных рёбер называют обыкновенным
графом. В дальнейшем всюду, если не оговорено противное, под
графом мы будем понимать именно обыкновенный граф.
16

Граф G = (V,E) с η вершинами и т рёбрами называется
(ji,m)-графом, (1,0)-граф называется тривиальным.
Примеры графов.
1. Пустой граф — это граф без рёбер (т. е. Ε = 0). Пустой
η-вершинный граф обозначается Оп.
2. Полный граф — это обыкновенный граф, любые две вершины
которого смежны. Полный η-вершинный граф обозначается Кп,
число рёбер в таком графе равно С\ = п'п2~ К
3. Двудольный граф— это граф, вершины которого разбиты на
две части (доли) таким образом, что концы каждого ребра при-
надлежат разным долям. Двудольный граф с долями Vi, V2 обо-
значается G = (Vi, V2; 2?).
Полный двудольный граф — это такой двудольный граф, в
котором любые две вершины, входящие в разные доли, смежны.
Полный двудольный граф, доли которого имеют мощности ρ и д,
обозначается КРФ число рёбер в таком графе равно pq.
4. Звезда — это полный двудольный граф Κ\Α.
5. Простой цикл длины η обозначается Сп. На рис. 1.1 приве-
дены два изображения простого цикла С$.
о *
Рис. 1.1.
6. Регулярный (или однородный) граф — это граф, все верши-
ны которого имеют одну и ту же степень. Если степень каждой
вершины равна к, то граф называется к-регулярным.
Кубические графы — это 3-регулярные графы.
7. Графы многогранников. На рис. 1.2 изображены графы пяти
Платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икоса-
эдра.
17

1 lr о 1
тетраэдр куб октаэдр
додекаэдр икосаэдр
Рис. 1.2.
1.2. Маршруты и метрика в графах
Маршрутом, соединяющим вершины и, ν (или (и, ν)-маршрутом)
называется чередующаяся последовательность вершин и рёбер
графа
(и = vh еь v2, е2,..., Vk, ek, vk+\ = ν), (1.1)
такая, что ег- = iw+ъ * = 1, ...,&. Маршрут (1.1) называется
замкнутым, если г>1 = Vfc+i·
Маршрут (1.1) можно задать последовательностью вершин
(vi, ^2,..., Vjb+i) или последовательностью рёбер (ei, е2,..., е&).
Длиной маршрута называется число рёбер в нём, причём каж-
дое ребро считается столько раз, сколько раз оно встречается в
данном маршруте.
Маршрут называется цепью, если все рёбра в нём различны,
и простой цепью, если все вершины в нём различны (кроме, воз-
з з
18

можно, крайних вершин). Замкнутая цепь называется циклом, а
замкнутая простая цепь — простым циклом. Простая цепь длины
к называется к-цепью и обозначается Р&, а простой цикл длины к
называется к-циклом и обозначается С^.
Лемма 1.1 (о выделении простой цепи). Всякий незам-
кнутый (и, г;) -маршрут содержит простую (и, ν)-цепь.
Доказательство. Если в данном (и, г>)-маршруте все вершины
различны, то он сам и есть простая (и, г>)-цепь.
Пусть теперь Vi — первая из вершин маршрута, имеющих в нём
повторения, a Vj — последнее её повторение в маршруте. Удаляя
все элементы циклической части маршрута между Vi и v^ заменим
его более коротким: (г>1, щ,..., ν*, г^+i,..., г^+i)·
Если в оставшемся (и, г>)-маршруте ещё есть повторения вер-
шин, то поступим с ними так же, и т. д. до тех пор, пока не полу-
чим простую (и, г?)-цепь.
Лемма доказана. ■
Следствие 1.1. Всякий замкнутый маршрут содержит
простой цикл.
Лемма 1.2 (об объединении простых цепей). Объедине-
ние двух несовпадающих простых {и, ν)-цепей содержит про-
стой цикл.
Доказательство. Пусть
Ρ = (иГ> U2, · . · , Ujfc+l), Q = {VUV2, . . . , Vt+i) —
несовпадающие простые цепи, где щ = v\ = и, щ+\ = vi+i = v.
Пусть ur+i,vr+i — первые, считая от щ несовпадающие верши-
ны этих цепей, a us — vt — первые из совпадающих вершин,
следующих за ur+i}vr+i. Тогда объединение (иг,г^)-фрагмента
цепи Ρ и (i7r, ^-фрагмента цепи Q является простым циклом:
С = (Ur,Ur+i,.. . ,We-i,lie,Vi-.i, . . .,Vr+l,Vr = ur)·
Лемма доказана. ■
19

Следствие 1.2 (свойство циклов). Если С и D — два не-
совпадающих простых цикла, имеющих общее ребро е, то граф
(CUD)-e содержит простой цикл, где (CUD) —e — граф, полу-
ченный удалением ребра е из графа, рёбрами которого являются
все рёбра циклов С и D и только они.
Доказательство. Пусть е = uv: Тогда С — е, D — е — несовпа-
дающие простые (и, г>)-цепи. Теперь свойство циклов следует из
леммы 1.2. ■
Расстоянием d(u, ν) между вершинами и, ν графа G называет-
ся длина кратчайшего (и, ν)-маршрута — он, естественно, являет-
ся простой цепью. Если в графе нет (и, г>)-маршрута, то полагаем
d(u,v) = оо. Полагаем также d(v,ν) — О для любой вершины
veV.
Граф G — (V, Е) называется связным, если для любых его
вершин и, ν в графе G существует (и, 1;)-маршрут.
Предложение 1.1. В связном графе G = (V, Е) расстояние
является метрикой, поскольку удовлетворяет всем аксиомам
метрики: для любых вершин u,v,w G V
1) d{u, v) ^ 0 и d(u, ν) = 0 <==> и = ν;
2) d(u,v) = d{v,u);
3) d(u, v) + d(v, w) ^ d(u, w),
1.3. Эйлеровы циклы и цепи
Пусть G = (V, Ε) — произвольный граф (возможно, мультиграф).
Цикл в графе G называется эйлеровым, если он содержит все рёб-
ра графа G. Граф называется эйлеровым, если в нём существует
эйлеров цикл.
Замечание 1.1. Поскольку цикл — это замкнутый марш-
рут, в котором все рёбра различны, то эйлеров цикл проходит
по каждому ребру ровно один раз.
20

Задача об эйлеровом цикле состоит в том, чтобы выяснить, яв-
ляется ли данный связный граф эйлеровым, и если да, то най-
ти эйлеров цикл. Эта задача была поставлена и решена в 1736 г.
Л. Эйлером.
Теорема 1.1 (Эйлер). В связном графе G = (У^Е) суще-
ствует эйлеров цикл, если и только если все его вершины имеют
чётную степень.
Доказательство. Необходимость. Эйлеров цикл, проходя
через каждую вершину графа G, входит в неё по одному ребру,
а выходит по другому. Значит, каждая вершина графа G должна
быть инцидентна чётному числу рёбер эйлерова цикла. А посколь-
ку эйлеров цикл содержит все рёбра графа С, то каждая вершина
должна иметь чётную степень.
Достаточность. Пусть граф G связен и все его вершины име-
ют чётную степень. Рассмотрим следующий алгоритм и докажем,
что он обязательно построит эйлеров цикл в графе G.
Алгоритм построения эйлерова цикла.
Выберем произвольную вершину vq и будем строить из неё
маршрут Со. Вершины маршрута запоминаем, а пройденные рёб-
ра удаляем из графа G. Действуем так до тех пор, пока в остав-
шемся графе G\ не будет рёбер, инцидентных очередной вершине
маршрута Со- Ясно, что процесс может прерваться только в ис-
ходной вершине г>о, и мы получаем цикл Со.
Если Со содержит все рёбра графа С, то он и есть искомый
эйлеров цикл. В противном случае в силу связности графа С най-
дется вершина v\ цикла Со, инцидентная некоторому ребру графа
G\. Начинаем строить из неё цикл С\ в графе G\.
Снова, если циклы Со и С\ содержат все рёбра графа С (т. е.
оставшийся граф G2 пуст), то конец. В противном случае в одном
из циклов Со, С\ найдётся вершина г>2, инцидентная какому-то
ребру графа G<i- Строим из неё цикл С2 в графе G2. И т. д.
21

В конце концов получим, что после построения цикла Ck остав-
шийся граф Gk+\ окажется пуст. Тогда конструируем эйлеров
цикл в графе G из ребер циклов Со, С\,..., Ck (см. рис. 1.3).
Теорема доказана. ■
Рис. 1.3.
Цепь в графе G называется эйлеровой, если она содержит все
рёбра графа G (очевидно, проходя по каждому ребру ровно один
раз). Граф, содержащий эйлерову цепь, иногда называют полуэй-
леровым.
Как следствие теоремы 1.1 можно получить критерий суще-
ствования эйлеровой цепи в связном графе, также доказанный
Эйлером в 1736 г.
Следствие 1.3 (Эйлер). В связном графе существует эй-
лерова цепь тогда и только тогда, когда все его вершины, за
исключением, быть может, двух, имеют чётную степень.
Доказательство. Необходимость очевидна.
Достаточность. Если все вершины имеют чётную степень, то
по теореме 1.1 существует эйлеров цикл, а значит, и эйлерова цепь.
Если все вершины, кроме двух, имеют чётную степень, то соеди-
ним эти две вершины ребром. Получим эйлеров граф, в котором
по теореме 1.1 есть эйлеров цикл. Удалив из него добавленное
ребро, получим эйлерову цепь.
Что и требовалось доказать. ■
22

1.4 с Гамильтоновы циклы и цепи
Пусть G — (V, Е) — произвольный граф. Простой цикл в графе
G называется гамильтоновым, если он содержит все вершины
графа G. Граф называется гамильтоновым, если он содержит
гамильтонов цикл.
Замечание 1,2. Поскольку простой цикл — это замкнутый
маршрут, в котором все вершины различны, то гамильтонов
цикл проходит по каждой вершине ровно один раз.
Задача о гамильтоновом цикле состоит в том, чтобы опреде-
лить, является ли данный связный граф гамильтоновым, и если
да, то найти гамильтонов цикл.
Можно рассматривать «незамкнутый» аналог задачи о гамиль-
тоновом цикле, и тогда это будет задача о гамильтоновой цепи.
Простая цепь в графе G называется гамильтоновой, если она
содержит все вершины графа G (очевидно, проходя по каждой
вершине ровно один раз). Граф, содержащий гамильтонову цепь,
называют полугамильтоновым.
Постановки задач об эйлеровом цикле и о гамильтоновом цик-
ле очень похожи. Однако, задача о гамильтоновом цикле гораздо
более сложна, чем задача об эйлеровом цикле. Ещё в XVIII веке
доказан простой критерий существования эйлерова цикла (теоре-
ма 1.1), а критерий существования гамильтонова цикла не найден
до сих пор. Известны лишь некоторые необходимые и некоторые
достаточные условия гамильтоновости. Далее будут рассмотрены
два наиболее известных достаточных условия существования га-
мильтонова цикла в связном графе (теоремы 1.2 и 1.3).
Теорема 1.2 (Оре). Пусть η ^ 3. Если в η-вершинном гра-
фе G для любой пары и, v несмежных вершин выполнено пера-
венство d(u) + d(v) ^ η, то G — гамильтонов граф.
Доказательство. От противного. Предположим, что граф G
удовлетворяет условию теоремы, но не является гамильтоновым.
23

Соединив две несмежные вершины такого графа ребром, мы вновь
получим граф, удовлетворяющий условию теоремы. Поскольку
полный граф гамильтонов, то существует максимальный нега-
мильтонов граф, удовлетворяющий условию теоремы; обозначим
этот граф G*. Таким образом, добавление любого ребра к графу
G* приводит к появлению в нём гамильтонова цикла. Поэтому лю-
бые две несмежные вершины графа G* соединены гамильтоновой
цепью.
Выберем в G* пару несмежных вершин ν\,νη и пусть Ρ =
(vi, г>2,..., wn-ii vn) — гамильтонова цепь в графе G*.
Если в графе G* вершины vi, Vi смежны, то вершины Vj_i, vn не
могут быть смежны, ибо в противном случае граф G* содержал бы
гамильтонов цикл С = (г>1, г>2,. · ., t^_i, vn, г>п-ъ..., V{, v\). Таким
образом, вершина vn несмежна в графе G* не менее, чем с а(у{)
вершинами, откуда d{yn) < η — 1 — d{v\). Следовательно, d(v\) +
d(vn) ^ η — 1, что противоречит условию теоремы.
Теорема доказана. ■
Как следствие теоремы 1.2 получаем следующее достаточное
условие гамильтоновости графа, независимо доказанное Г. Дира-
ком.
Теорема 1.3 (Дирак). Пусть η ^ 3. Если в п-вершинном
графе G для любой вершины ν выполнено неравенство d(v) ^ |,
то G — гамильтонов граф.
В отличие от задачи об эйлеровом цикле не найден также алго-
ритм поиска гамильтонова цикла, который работал бы существен-
но более быстро, чем алгоритм полного перебора.
Алгоритм полного перебора устроен следующим образом.
Фиксируем произвольную вершину η-вершинного графа G и гене-
рируем все \п~2 '' различных последовательностей остальных вер-
шин. Для каждой из последовательностей проверяем, определяет
ли она гамильтонов цикл.
24

Главный недостаток алгоритма полного перебора состоит в
том, что он требует в худшем случае просмотра факториального
числа вариантов, а п\ растет быстрее не только любого полинома,
но даже любой экспоненциальной функции видаап, а > 1.
Заметим также, что 70! « 1,2 · 10ш) (1,2 гугола), и даже при
η — 50 полный перебор всех п\ вариантов потребовал бы десятков
лет машинного времени.
Далее мы опишем схему метода, позволяющего значительно со-
кратить число шагов в алгоритме полного перебора.
Алгоритм поиска гамильтонова цикла.
Дан произвольный граф G — (У, Е), \V\ = п. Искомое решение
задачи о гамильтоновом цикле (если оно существует) будет иметь
вид (vb ..., vn, vn+i), где vn+i = v\.
Основная идея метода состоит в том, что мы строим реше-
ние (гамильтонов цикл) постепенно, начиная с последовательно-
сти (υ{). Вообще, имея частичное решение (vi,..., ν*), мы стара-
емся найти такую допустимую (т. е. ещё не пройденную) вершину
г/х-+1, которая может быть добавлена к решению (г>х,..., ν,·)..Если
такая вершина Vi+\ существует, мы добавляем её и продолжаем
процесс для последовательности (v\y..., ν2·, v2>i)· Если же такой
вершины г>г+1 не существует, то мы возвращаемся к частичнму
решению (vi,..., ^-i) и продолжаем процесс, отыскивая другую
допустимую вершину υ'{. По этой причине такой алгоритм назы-
вают также «алгоритмом с возвратом».
Упражнения
1.1. Имеется 10 костяшек домино:
0-1, 0-6, 1-2, 1-3, 2-3, 2-6, 3-4, 3-6, 4-5, 5-6.
Требуется выложить из них самую длинную цепь. Сколько в ней
костяшек?
1.2. Из полного комплекта костяшек домино изъяты все дуб-
ли и ещё две костяшки. Из оставшихся костяшек выкладывают
25

самую длинную цепь. Сколько в ней костяшек?
1.3. Можно ли обойти конём шахматную доску так, чтобы
каждый ход встречался ровно один раз? (Ход «встречался», ес-
ли конь переместился с одной клетки на другую любым из двух
возможных способов).
1.4. Та же задача для короля и ладьи.
1.5. Та же задача для короля и ладьи на доске размером 3x3.
Где возможно, найти обход.
1.6. Есть ли среди графов пяти Платоновых тел (рис. 1.2)
эйлеровы графы? Если да, то найти эйлеров цикл.
1.7. Для каких т, η графы Кп и Кт<а являются
а) эйлеровыми; б) полуэйлеровыми?
1.8. Найти эйлеров цикл в графах К$ и К^2·
1.9. Найти эйлеров цикл в графах Кч и К^.
1.10. Найти эйлеров цикл в графе
а) на рис. 1.4(a); б) на рис. 1.4(6).
Рис. 1.4.
1.11. Является ли эйлеровым графом 4-мерный куб
(рис. 1.5)? Если да, то найти эйлеров цикл.
1.12. Найти эйлерову цепь в графах К^2 и К^^-
1.13. Найти эйлерову цепь в графе из задачи 1.1.
26

Jk
fl
у
\Л
J
13
16
к
7Ι
12
Рис. 1.5.
11
Ν
14
15
1.14. Можно ли обойти конём все поля шахматной доски, по-
сетив каждое поле по одному разу, и вернуться на исходное поле?
Если да, то найти обход.
1.15. Та же задача для короля и ладьи.
1.16. Та же задача для короля и ладьи на доске размером
3x3. Где возможно, найти обход.
1.17. Можно ли обойти конём все поля доски размером 4x4,
посетив каждое поле по одному разу? Возвращаться на исходное
поле необязательно.
1.18. Есть ли среди графов пяти Платоновых тел (рис. 1.2)
гамильтоновы графы? Если да, то найти гамильтонов цикл. Изоб-
разить дерево поиска.
1.19. Для каких р, q граф КР:Я является
а) гамильтоновым; б) полугамильтоновым?
1.20. Найти гамильтонов цикл в графе Аз,з· Изобразить де-
рево поиска.
1.21. Найти гамильтонову цепь в графе Аз,4? Изобразить де-
рево поиска.
1.22. Гамильтонов ли 4-мерный куб (рис. 1.5)? Найти гамиль-
тонов цикл или доказать, что граф негамильтонов. Изобразить
дерево поиска.
27

1.23. Гамильтонов ли граф Петерсена (рис. 1.6)? Найти га-
мильтонов цикл или доказать, что граф негамильтонов. Изобра-
зить дерево поиска.
1.24. Гамильтоновы ли графы, изображенные на рис.
a) 1.7(a), б) 1.7(6)? Изобразить дерево поиска.
Φ
4
(а)
Рис. 1.7.
1.25. Показать, что условия теорем Оре и Дирака не явля-
ются необходимыми условиями гамильтоновости графа.
1.26. Доказать, что граф двудолен тогда и только тогда, ко-
гда в нём каждый цикл имеет чётную длину.
28

2. Основные понятия и факты
2.1. Степени вершин графа
Степенью вершины ν в графе G называется число рёбер, инци-
дентных вершине ν (обозначается dc(v) или d(v), если ясно, о
каком графе идёт речь). Вершина степени 0 называется изоли-
рованной, а вершина степени 1 — висячей. Минимальная и мак-
симальная степени вершин графа G обозначаются 6(G) и Δ((?),
соответственно.
Последовательность степеней вершин графа G, выписанных
в порядке неубывания, называется степенной последовательно-
стью или вектором степеней графа G.
Следующее утверждение связывает степени вершин графа с
числом его рёбер.
Лемма 2.1 (о рукопожатиях). Сумма степеней всех вер-
шин произвольного графа G = (V, Е) — чётное число, равное
удвоенному числу его рёбер:
Σα0(ν) = 2\Ε\. (2.1)
vev
Доказательство (индукция по числу рёбер). Если в графе G
нет рёбер, то Σ dc(v) = 0 = 2\Е\. Предположим, что формула
vev
(2.1) верна для любого графа, число рёбер в котором не превос-
ходит га, где га > 0.
Пусть \Е\ = т + 1. Рассмотрим произвольное ребро е = uv £ Ε
и удалим его из графа G. Получим граф G = (V, Е')9 в котором
\Е'\ — га. По предположению индукции J2 dc(v) — 2\Е'\ = 2га.
Тогда veV
J2 dG(v) = ]Г ασ(ν) + 2 = 2га + 2 = 2(га + 1) = 2\Е\.
veV veV
Лемма доказана. ■
29

Следствие 2.1. В любом графе число вершин нечётной сте-
пени четно.
Замечание 2.1. Понятие степени вершины и лемма о руко-
пожатиях переносятся и на мультиграфы.
2.2. Изоморфизм графов. Помеченные и непомеченные
графы
Рассмотрим графы, изображенные на рис. 1.1. Разные это графы
или одинаковые? С одной стороны, и тот и другой граф пред-
ставляют собой простой цикл Cs, и в этом смысле это один и тот
же граф. С другой стороны, при фиксированном множестве вер-
шин порядок прохождения вершин в этих циклах различен, по-
этому можно считать графы разными. Всё зависит от того, как
понимать суждение «графы одинаковы». Следующее определение
может служить формализацией этого понятия.
Графы G = (Vg, Eq), Η — (V#, £?#) называются изоморфны-
ми (записывается G = Я), если между множествами их вершин
существует взаимно однозначное соответствие φ : Vq -> V#, со-
храняющее смежность, т. е.
Vu, v e Vg uv e Eg <==> <p(u)ip{v) € Ен-
4
2
4 5 6 5
Рис. 2.1.
Например, графы, изображённые на рис. 2.1, изоморфны, а
графы на рис. 2.2 не изоморфны.
30

Рис. 2.2.
Замечание 2·2. Отношение изоморфизма графов является
отношением эквивалентности, так как оно рефлексивно, сим-
метрично и транзитивно.
Следовательно, множество всех графов разбивается на клас-
сы эквивалентности, состоящие из попарно изоморфных графов.
Естественно считать изоморфные графы одинаковыми, поскольку
их можно изобразить одним рисунком.
Если необходимо подчеркнуть, что рассматриваемые графы
различаются лишь с точностью до изоморфизма, говорят о непо-
меченных графах. Однако, бывают ситуации, когда всё-таки при-
ходится различать изоморфные графы. Граф называется поме-
ченным, если его вершины отличаются одна от другой какими-
нибудь метками, например, vi, г>2,..., vn, или номерами 1,2,..., п.
• 3 W Ν·3
Рис. 2.3.
1 1
л.
2·' 4·3 3· ·2
Рис. 2.4.
На рис. 2.3 изображены 3 разных помеченных графа, но поме-
ченные графы на рис. 2.4 одинаковы.
Несложно подсчитать количество помеченных п-вершинных
графов.
31

Теорема 2.1. Число рп различных помеченных п-вершинных
графов с фиксированным множеством вершин V равно 2 s .
Доказательство. В помеченном η-вершинном графе G мож-
но перенумеровать все пары вершин (таких пар всего С^ = п\п~ч}
и поставить графу G во взаимно однозначное сответствие его ха-
рактеристический eercmop длины к — w'w2"% j-я компонента ко-
торого равна
-{i
если пара вершин с номером j смежна,
в противном случае.
Тогда рп равно числу булевых векторов длины к = п ^ , т. е.
Теорема доказана. ■
Число qn различных (т. е. попарно неизоморфных) непомечен-
ных η-вершинных графов определить гораздо сложнее. На пер-
вый взгляд, числа рп и qn должны быть связаны соотношением
Qn — Pn/nl*, так как существует ровно п! различных пометок мно-
жества V, состоящего из η вершин. Однако, не из каждого непоме-
ченного графа получается ровно п! помеченных. Например, непо-
меченная простая цепь Ръ длины 2 порождает не 3! = 6, а всего 3
разных помеченных графа, изображённых на рис. 2.3).
Тем не менее, известна формула Пойа, дающая асимптотику
числа qn.
Теорема 2.2 (фомула Пойа). Числа qn и рп/п\ асимпто-
тически равны:
2 2
Чп
(Асимптотическое равенство /(n) ~ д{п) двух функций означает,
что lim Ш = 1).
п-лоо 9КЩ J
Итак, число непомеченных η-вершинных графов «приблизи-
тельно» в п! раз меньше числа помеченных, и это соотношение
тем точнее, чем больше п.
32

2.3. Подграфы. Восстановление графов
Подграфом графа G — (V, Е) называется произвольный граф
Η = (U,D) такой, что U С V, D С Ε (обозначается Я С G).
Подграф Η — (С/, D) называется порождённым подграфом графа
G = (У, Е)у если он обладает следующим свойством:
Vu, υ Ε U uv Ε D Φ=>· ш; € £".
Остовный подграф — это подграф графа G, содержащий все его
вершины.
Важные классы подграфов составляют подграфы, полученные
в результате удаления вершин и рёбер.
Если U С V, то через G — U будем обозначать подграф графа
G = (V,25), полученный удалением из G всех вершин множества
U вместе со всеми инцидентными им рёбрами. В случае, когда
подмножество U состоит из единственной вершины ν € V, будем
использовать обозначение G — v.
Если D С Е, то через G — D будем обозначать подграф графа
(7 = (V, i?), полученный удалением из G всех рёбер множества Ζλ
Аналогично, если D состоит из единственного ребра е £ Е, будем
использовать обозначение G — е.
Замечание 2.3. Подграф G — D— остовный. Подграф G — U
порождён множеством V\U.
С подграфами G — ν связана знаменитая гипотеза С. Улама о
восстановлении графов.
Пусть G = (УУЕ) — произвольный обыкновенный граф. Для
каждой вершины ν графа G построим подграф G — v. Семейство
{G — ν : ν € V} всех таких непомеченных подграфов называется
колодой графа G и обозначается P{G).
Заметим, что разные (т. е. неизоморфные) графы могут иметь
одинаковые колоды. Например, Р(К2) = Ρ(θ2) = {Oi,0i}· Ги-
потеза Улама утверждает, что это единственный пример.
33

Гипотеза восстановления (Улам). При η ^ 3 любой η-вер-
шинный граф однозначно с точностью до изоморфизма восста-
навливается по своей колоде.
Другими словами, любые два графа с одинаковыми колодами
изоморфны.
Гипотеза Улама, сформулированная в 1945 г., не доказана и не
опровергнута до сих пор, причём у специалистов даже нет еди-
ного мнения по вопросу её истинности или ложности. Гипотеза
доказана для всех η-вершинных графов при 3 ^ η < 11 и для
некоторых классов графов, в частности, для деревьев.
Гипотезу Улама часто называют гипотезой вершинной рекон-
струируемости. Наряду с ней известна также гипотеза рёберной
реконструируемости(Ф. Харари, 1964). Она формулируется ана-
логично, только вместо вершин удаляются рёбра. Эта гипотеза
также не доказана и не опровергнута, хотя и подтверждена для
некоторых классов графов.
2.4. Проблема изоморфизма. Инварианты графов
Одна из самых важных проблем теории графов — проблема изо-
морфизма: выяснить, изоморфны ли два данных графа. Проблема
эта, весьма интересная сама по себе, имеет широкие практические
приложения, прежде всего в органической химии. Традиционно
молекулы представляются в виде графов, вершины которых со-
ответствуют атомам, а рёбра — связям между атомами. Задача
идентификации структур (химических соединений) таким обра-
зом сводится к определению изоморфизма графов.
В общем случае проблема изоморфизма очень сложна. Если
пользоваться определением изоморфизма графов, то придётся пе-
ребрать все п! взаимно однозначных соответствий между множе-
ствами вершин двух графов и проверить, совпадают ли множества
их рёбер хотя бы при одном соответствии. Однако, такой способ
практически неприемлем в связи с очень быстрым ростом функ-
34

ции η! при увеличении п. Как уже отмечалось, даже при η = 50
перебор всех п! вариантов потребовал бы десятков лет машинного
времени.
Один из возможных методов решения проблемы изоморфизма
состоит в следующем: попытаться найти такие свойства графа,
которые определяли бы граф с точностью до изоморфизма, т. е.
найти полную систему инвариантов.
Инвариант графа G — это величина i(G) (число, набор чисел
или функция), связаная с графом и принимающая одно и то же
значение на любом графе, изоморфном G, т. е. G == Η => i{G) =
г(Н). Инвариант называется полным, если для любых графов G
и Я i(G)=i(H)=>G^H.
Примеры инвариантов.
1. Число n{G) вершин графа G.
2. Число m{G) рёбер графа G.
3. Минимальная степень 6(G) графа G.
4. Максимальная степень A(G) графа G.
5. Плотность </?(£?) графа G — наибольшее число попарно
смежных вершин.
6. Неплотность e(G) графа G — наибольшее число попарно
несмежных вершин.
7. Хроматическое число x(G) графа G — наименьшее %, для
которого граф G имеет правильную %-раскраеку множества вер-
шин.
В качестве инварианта можно рассматривать не одно число, а
систему чисел, например, степенную последовательность.
8. Степенная последовательность ds(G) = (di, di,..., dn) —
последовательность степеней всех вершин графа G, выписанных
в порядке неубывания: d\ ^ с?2 ^ ... ^ dn.
Задание последовательности (pojPi,P2» · · О равносильно зада-
нию многочлена Р(х) = ]£ Pk%k = Ро + V\x + Р2%2 + ... от фор-
мальной переменной х. Рассмотрим несколько инвариантов такого
35

вида.
9. F(G) = Σ fkxk = fix + hx2 + ... + Ux«, где ψ = φ{β) -
плотность графа G, Д — количество полных fc-вершинных под-
графов графа G.
10. E(G) = Σ екхк = eix 4- е2х2 + ... + ебяб, где б = с (С?) —
неплотность графа (7, е& — количество пустых порождённых
fe-вершинных подграфов графа G.
11. Q(G) = Σ Σ Qijx%y^ гДе 9у ~ количество порождённых
г-вершинных подграфов графа G, имеющих ровно j рёбер.
12. Инварианты, связанные с матричным заданием графа.
Пусть G = (V, Е) — помеченный η-вершинный граф,
V = {1,2,... ,п}. Составим (га х п)-матрицу Л = Л (С?) = (ау)
по правилу:
{1, если ij 6 25,
О, в противном случае.
Матрица A(G) симметрична и называется матрицей смеэюности
графа G. В общем случае матрица смежности не является инва-
риантом графа, так как при перенумерации вершин она может
претерпеть перестановку рядов (т. е. согласованную перестанов-
ку строк и столбцов). Но любая функция от а^·, не изменяюща-
яся при перестановках рядов матрицы Л((7), будет инвариантом
графа G. К ним относятся определитель матрицы Л (б?), харак-
теристический многочлен /(A) =. \A(G) — ХЕ\ и спектр графа —
множество корней характеристического многочлена.
Замечание 2.4. Никакой из инвариантов 1 — 12 не являет-
ся полным.
Тем не менее, полные инварианты существуют. Далее рассмот-
рим один из них.
36

Пусть G = (V,E) — η-вершинный граф, V — {1,2,... ,n},
/1(G) — его матрица смежности. Так как матрица A{G) симмет-
рична, для её задания достаточно выписать в определённом по-
рядке лишь элементы, расположенные выше главной диагонали,
например по столбцам:
^12, ais, «23, &14, a24, ^34, ■ ■ ■ ainj-fl2nj · · · > Λ(η-1)η·
Полученное двоичное слово длины & — п % называется дво-
ичным кодом матрицы A{G). Подобно матрице смежности, дво-
ичный код не является инвариантом графа. Число
μ(0) = а122° + а1г21 + а2322 + ... a(n-l)n2k-1
называется каноническим кодом матрицы A(G).
Канонические коды матриц смежности одного и того же графа,
отвечающие разным нумерациям его вершин, вообще говоря, раз-
личны. Наименьший из них (при всевозможных п\ нумерациях),
называется миникодом μ{0) графа G.
Пример 2.1. Вычислить миникод графа Р2.
Простая цепь Р2 допускает 3! = б нумераций вершин, но из-
за симметрии графа различных помеченных графов будет всего 3
(см. рис. 2.3). Поэтому различных матриц смежностей будет тоже
не 6, а 3, а значит и 3 разных канонических кода:
1 -2° + 1 -21 + 0 ·22 = 3 = μ(Ρ2),
1 · 2° + 0 ■ 21 + 1 · 22 = 5,
О · 2° + 1 · 21 + 1 · 22 - 6.
Теорема 2.3. (//(Gr),n(G)) — полная система инвариантов,
где //(С) — миникод, n(G) — число вершин графа G.
Доказательство. Очевидно, что n(G) — инвариант. Докажем,
что /x(G) — инвариант. Пусть G = Η и φ : Vq —> V# — изомор-
физм графов G и Η. Рассмотрим ту нумерацию вершин графа G,
которой соответствует миникод μ(£?). Занумеруем вершины графа
Η следующим образом: вершине φ(1) присвоим номер 1, вершине
φ(2) — номер 2, ..., вершине φ(η) — номер п, где η = n(G).
37

Очевидно, что этой нумерации будет соответствовать миникод
μ(Η) = μ(0).
Докажем теперь, что два числа μ((7),η((7) образуют полную
систему инвариантов. Если (μ((7),η((7)) = (μ(Η),η(Η)), то оди-
наковы двоичные коды матриц смежности A(G) и А(Н), отвечаю-
щие миникодам μ(0) = μ(#). Значит, одинаковы и сами матрицы
A(G) и А(Н). Поэтому G = Н, т. е. (/x(G), n(G)) — полная система
инвариантов.
Теорема доказана. ■
Замечание 2.5. Миникод η-вершинного графа G — целое
число в диапазоне от 0 до 2 2~ — 1.
Итак, полные инварианты (системы инвариантов) существуют,
но они не решают проблему изоморфизма, поскольку все извест-
ные в настоящее время полные инварианты являются «трудно-
вычислимыми»: процесс вычисления этих инвариантов сравним
по трудоёмкости с полным перебором всех п\ соотоветствий мно-
жеств вершин двух графов, требуемым для отыскания их изомор-
физма.
2.5. Связные и несвязные графы
Вершины и, ν в графе G называются соединимыми, если в G суще-
ствует (и, г>)-маршрут. Граф G называется связным, если любые
его две вершины соединимы. Тривиальный (1,0)-граф по опреде-
лению считается связным. Максимальный1 связный подграф гра-
фа G называется компонентой связности или просто компонен-
той графа G.
Ребро е называется циклическим, если оно принадлежит неко-
торому циклу, и ациклическим в противном случае.
1 Здесь «максимальный» означает максимальный по включению, т. е. не содержащийся
в связном подграфе с большим числом элементов (вершин и рёбер)
38

Лемма 2.2 (об удалении ребра). Пусть G = (V,E) —
связный граф, е € Е.
1) Если е — циклическое ребро, то граф G — е связен;
2) если е — ациклическое ребро, то граф G — е имеет ровно
две компоненты связности.
Доказательство. 1) Пусть ребро е = uv входит в цикл С,
который можно рассматривать как объединение ребра е и (и, υ)-
цепи Р.
Рассмотрим произвольные вершины s,t £ V я докажем, что
они соединимы в графе G — е. Так как по условию граф G связен,
то в нём существует (s, ^-маршрут. Если этот маршрут проходит
по ребру е, то, заменив в нём ребро е (и, г>)-цепыо Р, получим
новый (s, ^-маршрут, не проходящий по ребру е. Отсюда следует,
что граф G — е связен.
2) Если ребро е = uv — ациклическое, то, очевидно, вершины
и, ν входят в разные компоненты связности графа G—e. Докажем,
что этих компонент ровно две. Для этого достаточно доказать, что
произвольная вершина w Ε V, отличная от и, ν> находится в той
же компоненте графа G — е, что и одна из вершин и, v.
Так как граф G связен, то в нём существует простая (w, ги)-цепь
и простая (ν, и?)-цепь. Заметим, что ребро е должно входить хотя
бы в одну из этих цепей (иначе ребро е было бы циклическим).
Пусть, скажем, ребро е входит в простую (и, -ш)-цепь. Тогда е не
может входить ни в одну из (ν, гу)-цепей. Это означает, что w
принадлежит той же компоненте связности графа G — е, что и
вершина v.
Лемма доказана. ■
Следствие 2.2. Если граф G = (V, Е) имеет к компонент
связности и е G Е, то граф G — е имеет к или к + 1 компонент.
В силу леммы 2.2 связный граф после удаления ребра может
стать несвязным, но в нём будет ровно две компоненты связно-
сти. Кроме того, существуют связные графы, которые становятся
39

несвязными после удаления любого ребра — это деревья, в них
все рёбра ациклические.
В случае удаления вершин ситуация иная. Во-первых, при уда-
лений вершины связный граф может «развалиться» не на две, а
на большее число компонент. А во-вторых, имеет место следую-
щая
Лемма 2.3 (об удалении вершины). В любом нетриви-
альном связном графе G существует вершина, после удаления
которой граф остаётся связным.
Доказательство, Пусть s,i — максимально удалённые друг
от друга вершины графа G = (V, Е), т. е. d(s, t) = max.d(u, v).
Предположим, что граф G—t несвязен. Тогда существует такая
вершина w, что вершины s, w принадлежат разным компонентам
связности графа G — t. По условию граф G связен, следовательно,
в G существует (s, ги)-цепь} причём любая такая цепь проходит
через вершину t. Но тогда d(s, w) > d(s, £), противоречие. Значит,
граф G — t связен.
Лемма доказана. ■
Следствие 2.3. В любом нетривиальном связном графе су-
ществует не менее двух вершин, после удаления каждой из ко-
торых граф остаётся связным.
В заключение параграфа обсудим следующий вопрос: сколько
рёбер может иметь обыкновенный тг-вершинный граф? Тривиаль-
ными оценками числа т рёбер произвольного η-вершинного гра-
фа являются 0 < т ^ n ^ К Если, кроме того, известно, что граф
связен, то нижняя оценка числа рёбер может быть существенно
уточнена.
Теорема 2.4 (оценки числа рёбер связного графа).
Если G — связный (п,т)-граф, то
п(п — 1)
2
40

Доказательство. Доказательства требует только нижняя
оценка т ^ η — 1, докажем её индукцией по т. При т = О оценка
очевидна, так как в этом случае G — тривиальный граф, откуда
га = 1.
Предположим, что ш> 1и для графов с меньшим, чем га, чис-
лом рёбер неравенство верно. Если в G есть циклы, то рассмотрим
граф G—e, где е — произвольное циклическое ребро. Тогда по лем-
ме 2.2 об удалении ребра граф G — е связен, а по предположению
индукции число рёбер в нём т — 1 ^ η — 1, откуда га ^ η > η — 1.
Если же в графе G нет циклов, то по лемме 2.2 граф G — е имеет
ровно две компоненты связности, и по предположению индукции
т,{ ^ щ — 1, где щ, гщ — количество вершин и рёбер г-той ком-
поненты, г = 1,2. Тогда га — 1 = rai + гаг > ni + n<i — 2 = η — 2.
Следовательно, га ^ η — 1.
Теорема доказана. ■
2.6. Плоские и планарные графы
Довольно часто бывает важно выяснить, можно ли изобразить
граф на плоскости так, чтобы его рёбра не пересекались вне вер-
шин. Например, в печатных платах (микросхемах, изготовленных
печатным способом), проводники, нанесённые на поверхность изо-
ляционного материала, не должны пересекаться. Если клеммы та-
кой микросхемы считать вершинами графа, а проводники — рёб-
рами, то полученный граф будет плоским.
Плоский граф — это такой граф, вершины которого являются
точками плоскости, а рёбра — непрерывными плоскими линиями
без самопересечений, соединяющими вершины так, что никакие
два ребра не имеют общих точек вне вершин. Граф называется
планарным, если он изоморфен некоторому плоскому графу.
Например, граф К± — планарный (см. рис. 2.5).
Замечание 2.6. Несложно показать, что графы Хз.з и К$
непланарны (рис. 2.6).
41

Η ■ Ш· А
Рис. 2.5.
■^3,3
Рис. 2.6.
Эти графы называют графами Куратовского. Известный поль-
ский геометр К. Куратовский является одним из авторов крите-
рия планарности графа, который независимо в 1927 г. (на три года
раньше Куратовского) был также доказан замечательным совет-
ским математиком Л. Понтрягиным. Чтобы сформулировать этот
критерий, нам понадобится ещё одно определение.
Два графа называются гомеоморфнымц если их можно полу-
чить из одного и того же графа с помощью разбиений рёбер, т. е.
замены некоторых рёбер простыми цепями. На рис. 2.7 изображе-
ны графы, гомеоморфные Кз^ и К^.
Рис. 2.7.
Теорема 2.5 (Понтрягин-Куратовский). Граф планарен
тогда и только тогда, когда он не содержит подграфов, гомео-
морфных А"з,з или К$.
Чаще всего этот критерий используется для доказательства
непланарности того или иного графа.
-·#
42

Гранью плоского графа называется максимальное множество
точек плоскости, каждая пара из которых может быть соединена
непрерывной линией, не пересекающей рёбер графа.
Замечание 2.7. 1) Всякий плоский граф имеет одну и при-
том единственную неограниченную грань. Эта грань называет-
ся внешней, а все остальные — внутренними.
2) Каждая точка плоскости принадлеоюит хотя бы одной
грани плоского графа.
Лемма 2.4 (о гранях плоского графа). Пусть G — связ-
ный плоский граф, ν £ V — такая вершина, что граф G = G — ν
связен. Тогда число граней графов G uG связано соотношением
l = V + d(v) — 1, где d(v) — степень вершины ν в графе G.
Доказательство. Очевидно, граф G = G — ν тоже плоский.
Рассмотрим его грань F, содержащую «след» от вершины ν (точ-
ку, в которой в графе G располагалась вершина ν) — это может
быть и внешняя грань. Рёбрами, инцидентными вершине ν, грань
F разбивается на d — d(v) граней графа G (одна из этих гра-
ней может быть внешней). При удалении из графа G вершины ν
вместе со всеми инцидентными ей рёбрами эти d граней исчеза-
ют, а вместо них остаётся одна грань F графа G. Следовательно,
Лемма доказана. ■
Следующая формула впервые была доказана Л. Эйлером в
1758 г. для выпуклых многогранников. Она верна также для связ-
ных плоских графов.
Теорема 2.6 (формула Эйлера). Для всякого связного
плоского графа верна формула
η — т + I = 2,
где η — число вершин, т — число рёбер, I — число граней графа.
43

Доказательство. Индукция по числу вершин графа. При
η — 1 и η = 2 формула верна. Пусть теперь η > 3 и предпо-
ложим, что формула верна для любого плоского графа с числом
вершин, меньшим п.
Рассмотрим произвольный связный плоский граф G — (У, Е))
\V\ — п. По лемме 2.3 существует такая вершина ν Ε V, что
граф Gf = G — ν связен. По предположению индукции для графа
G формула верна: п' — т! + V — 2. Очевидно, что η — п! + 1,
т = га' + d(v). Кроме того, /==/' + d(v) — 1 в силу леммы 2.4.
Поэтому
n-m + / = (η' + 1) — (пг'-Ьd(v)) Η-(Ζ' + rf(v) — 1) = ri-mf+ 1' = 2.
Теорема доказана. ■
Упражнения
2.1. Доказать утверждение следствия 2.1.
2.2. Доказать, что в любом нетривиальном связном графе
обязательно найдутся хотя бы две вершины одинаковой степени.
2.3. Перечислить все помеченные и непомеченные 3-вершин-
ные графы.
2.4. Перечислить все непомеченные графы
а) с 4 вершинами, вычислить q^ б) с 5 вершинами, вычислить q$.
2.5. Чему равно число pn?m различных помеченных (п, т)-
графов?
2.6. Перечислить все помеченные
а) (4,1)-графы; б) (4,2)-графы; в) (4, 3)-графы.
2.7. Доказать, что графы, изображённые на рис. 2.1, изо-
морфны.
2.8. Доказать, что графы, изображённые на рис. 2.2, не изо-
морфны.
44

(a)
У
i <
4J
\
ν
(б)
]
Рис.
2.8.
(в)
2.9. Изоморфны ли графы, изображённые
а) на рис. 2.8(a) и 2.8(6); б) на рис. 2.8(6) и 2.8(b)?
2.10. Двудолен ли а) 3-мерный куб? б) 4-мерный куб?
2.11. Привести пример двух неизоморфных графов с наи-
меньшим числом вершин, имеющих одинаковые степенные после-
довательности .
2.12. Доказать, что определитель матрицы смежности гра-
фа — не полный инвариант.
2.13. Доказать утверждение замечания 2.4.
2.14. Доказать утверждение замечания 2.5.
2Л5. Любое ли целое число из промежутка [0,2 з — 1] яв-
ляется миникодом какого-либо η-вершинного графа?
2.16. Вычислить миникод графа а) С±\ б) Рз·
2.17. Восстановить 4-вершинный граф по его миникоду:
μ(β) = 11.
2.18. Восстановить 5-вершинный граф по его миникоду:
μ(β) = 31.
2.19. Пусть G — обыкновенный граф с η вершинами, т рёб-
рами и к компонентами связности. Доказать, что
(п-к)(п-к + 1)
η
к ^ т ^
45

2.20. Дополнением графа G = (V, Ε) называется такой граф
G = (V,E), что uv 6 Ε тогда и только тогда, когда uv SjL E.
Привести примеры графов или доказать, что таких примеров не
существует:
а) G связен, G несвязен;
б) G связен, G связен;
в) G несвязен, G несвязен.
2.21. Доказать, что следующие графы непланарны:
а) Я"з,з (старинная задача «Три дома, три колодца»); б) К$.
2.22. Пользуясь критерием Понтрягина-Куратовского, дока-
зать, что следующие графы непланарны:
а) 4-мерный куб Q± (рис. 1.5);
б) граф Петерсена (рис. 1.6).
2.23. Можно ли выбрать 6 точек на окружности так, чтобы
граф, вершинами которого являются эти точки, а рёбрами — дуги
окружности и 3 попарно пересекающиеся хорды, соединяющие эти
точки, был планарным?
2.24. Какое наибольшее число точек окружности можно вы-
брать так, чтобы граф, вершинами которого являются эти точки,
а рёбрами — дуги окружности и всевозможные хорды, соединяю-
щие несоседние точки, был планарным?
2.25. Планарен ли полный двудольный граф #2.4?
2.26. Планарен ли полный трёхдольный граф 1^2,2,2?
2.27. Любой ли планарный граф можно изобразить на плос-
кости так, чтобы все его внутренние грани были выпуклыми?
2.28. Где в доказательстве леммы 2.4 использовано условие
связности графа G — ν?
46

3. Деревья
3.1. Деревья и их свойства
Граф называется ациклическим, если в нём нет циклов. Дерево ■—-
это связный ациклический граф. Несвязный ациклический граф
называется лесом. Таким образом, компоненты связности леса яв-
ляются деревьями.
Известны и другие эквивалентные определения дерева. Неко-
торые из них приведены в следующей теореме.
Теорема 3.1 (о деревьях). Для (п, га)-графа G следующие
утверждения эквивалентны:
1) G — дерево;
2) G — связный граф и т = η — 1;
3) G — ациклический граф и т — η — 1;
4) G — ациклический граф и если любую пару его несмеж-
ных вершин соединить ребром, то полученный граф будет со-
держать ровно один цикл;
5) любые две вершины графа G соединены единственной про-
стой цепью.
Доказательство. 1) => 2). Очевидно, дерево — планарный
граф, имеющий ровно одну грань — внешнюю. По формуле Эйле-
ра (теорема 2.6) η — т + 1 = 2, откуда т = η — 1.
2) => 3). Пусть граф G связен и т = η — 1. Предположим про-
тивное, т. е. в G есть цикл, и пусть е — ребро этого цикла. Тогда
по лемме 2.2 (об удалении ребра) граф G — е связен и имеет η — 2
ребра. Однако, по теореме 2.4 число рёбер связного п-вершинного
графа не меньше η — 1, противоречие. Следовательно, G — ацик-
лический граф.
3) => 4). Докажем вначале, что граф G связен. Пусть к —
число компонент связности графа G и пусть г-тая компонента 7]
является (rii, га^-графом, г = 1,..., к. Так как Т{ — дерево, то по
47

ранее доказанному т\ — щ — 1. Тогда
η — 1 = т = V^ rrii = 2_](η·1 — 1) = /J щ — к = η — ky
г—1 г=1 г=1
откуда /с = 1, т. е. G — связный граф.
В связном графе G любые две несмежные вершины и, ν соеди-
нены простой цепью, поэтому добавление ребра е — uv приводит к
образованию цикла. Причем сразу два цикла при добавлении реб-
ра е образоваться не могут в силу свойства циклов (следствие 1.2).
4) => 5). Любые две несмежные вершины tt, v графа G соеди-
нимы, иначе при добавлении ребра гш не появится цикл; смежные
вершины тем более соединимы. Следовательно, в силу леммы 1.1
(о выделении простой цепи) любые две вершины графа G соеди-
нены простой цепью. Причём эта цепь единственная, так как в
противном случае по лемме 1.2 (об объединении простых цепей)
в графе G имелся бы цикл.
5) =4> 1). Поскольку любые две вершины графа G соединены
единственной простой цепью, то граф G связен. Кроме того, если
бы в нём имелся цикл, то любые две вершины этого цикла были
бы соединены более, чем одной простой цепью. Итак, G — связный
ациклический граф, т. е. G — дерево.
Теорема доказана. ■
Вершина степени 1 называется висячей вершиной или листом
дерева. Из теоремы о деревьях и леммы о рукопожатиях вытекает
следующее
Лемма 3.1 (о листьях дерева). В любом нетривиальном
дереве имеется не менее двух листьев.
Доказательство. По лемме 2.1 и теореме 3.1 для п-вершин-
ного дерева Τ — (У, Е)
Y^ d(v) = 2\Е\ - 2т - 2(га - 1) = 2п - 2 .
48

Так как в дереве Г степени всех вершин не меньше 1, т. е.
d(v) ^ 1 для любой вершины υ £ К, то хотя бы два слагаемых в
сумме слева должны быть равны 1.
Лемма доказана. ■
3.2. Перечисление деревьев
А. Кэли в 1889 г. подсчитал число различных деревьев, которые
можно построить на η вершинах.
Теорема 3.2 (Кэли). Число помеченных деревьев с η вер-
шинами равно t(n) = пп~2.
В дальнейшем было найдено множество различных доказа-
тельств этой замечательной формулы. Мы рассмотрим метод
Прюфера, он основан на следующей лемме.
Лемма 3.2. При η ^ 2 существует взаимно однозначное со-
ответствие между множеством всех помеченных п-вершин-
ных деревьев с метками 1,2,. ..,п и множеством всех слов
длины η — 2 в алфавите {1,2,..., п}.
Доказательство. 1. Докажем, что каждому дереву Τ с мно-
жеством вершин V = {1,2,... ,п} можно однозначно поставить
в соответствие слово длины η — 2 в алфавите {1,2,... ,п} (код
Прюфера).
Если η — 2, то сопоставим дереву Τ «пустое» слово длины 0.
Пусть теперь η ^ 3. Согласно лемме 3.1 в дереве Τ есть висячие
вершины (листья). Обозначим через ν\ первый лист дерева Τ (т. е.
висячую вершину с наименьшим номером), а через в\ — V\U\ —
соответствующее ребро дерева Т. Удалив из Τ вершину ν\ вместе
с ребром -ei, получим новое дерево Т\. В дереве Т\ снова найдём
первый лист V2 из V и ребро e<i — У2Щ. Эта редукция повторяет-
ся, пока после удаления ребра en_2 = vn-2^n~2 не останется един-
ственное ребро en_i = vn-\un-\. Тогда слово W — u\U2.-.un-2
49

однозначно определяется деревом Т, так как каждая вершина щ
определяется однозначно.
2. Покажем, что при η ^ 2 каждое слово вида W —
U\U2 ... wn_2, где щ Ε V = {1, 2,..., п} для любого г, однозначно
определяет некоторое дерево на множестве вершин V.
Найдём наименьший номер v\ Ε V, который не входит в Ж. Это
однозначно определяет ребро в\ = v\U\. Удалим v\ из У, ui из W и
продолжим построение для оставшихся чисел. После определения
ребра еп-2 — vn-2Un-2 в множестве V \ {г?1, г>2,..., г;п_2} останется
всего два числа. Они определяют последнее ребро en_i = vn-\vn.
Докажем, что граф Τ = (V, Л?) является деревом, где Ε —
{ei, ег, ·. ·, en_i}. Действительно, одно ребро en_i образует дерево.
Пусть рёбра en_i, еп_2,..., e^+i образуют дерево Т", 1 ^ г < η — 2.
Тогда рёбра en_i,en_2,... , e^+i,^, где е^ = у^щ, тоже образуют
дерево, так как щ является вершиной дерева Т', a Vi — нет.
Лемма доказана. ■
Доказательство теоремы 3.2. При η = 1 формула очевидно
верна. При η ^ 2 в силу леммы 3.2 число помеченных п-вершин-
ных деревьев равно числу слов длины η — 2, в которых каждая
«буква» может принимать любое из η значений 1,2,'..., п, а таких
слов всего пп~2.
Теорема доказана. ■
Замечание 3.1. Каждая вершина дерева появляется в коде
Прюфера d(v) — 1 раз, где d(v) — степень вершины ν в дереве.
3.3. Центр дерева
Эксцентриситетом вершины ν в связном графе G — (V, Е) на-
зывается величина ε(ν) — maxd(v, и) — расстояние от ν до самой
ueV
удалённой вершины. Радиусом связного графа G называется наи-
меньший из эксцентриситетов его вершин: r(G) = mme(v).
veV
Вершина ν Ε V называется центральной, если ε (ν) = r(G).
50

Множество всех центральных вершин графа называется его цен-
тром. Центр связного графа может состоять из одной или
нескольких вершин.
Центр дерева, изображённого на рис. 3.1, состоит из двух вер-
шин (возле каждой вершины указан её эксцентриситет). Смеж-
ность центральных вершин дерева была установлена в 1869 г.
К. Жорданом.
К-Л
5 4 4
Рис. 3.1.
5
А Л
1. 4 с2 ЛЩд1
Теорема 3.3 (Жордан). Центр любого дерева состоит из
одной или двух смежных вершин.
Доказательство. Утверждение теоремы очевидно для дере-
вьев с одной и двумя вершинами (это графы К\ и К2). Пусть
теперь Τ — дерево, имеющее не менее трёх вершин. Удалив из
Τ все листья, получим новое дерево Т1. Заметим, что эксцентри-
ситет каждой вершины дерева Т* на единицу меньше её эксцен-
триситета в дереве Т. Отсюда следует, что центры деревьев Г и
Т" совпадают. Продолжая процесс удаления листьев, мы получим
последовательность деревьев с тем же центром, что и в дереве Т.
Очевидно, что процесс непременно закончится либо деревом К^
либо деревом К^.
Теорема доказана. ■
Дерево, центр которого состоит из единственной вершины, на-
зывается центральным, а дерево, центр которого состоит из двух
смежных вершин — бицентралъным.
51

3.4. Изоморфизм деревьев
Для деревьев эффективно решается проблема изоморфизма. Рас-
смотрим метод, предложенный Дж. Эдмондсом, в основе которого
лежит линейное упорядочение множества всех конечных деревьев.
В частности, этот метод позволяет создать удобную систему ката-
логизации химических препаратов, что может существенно упро-
стить весьма актуальную задачу поиска химических патентов.
Пусть Τ — (У, Ε) — η-вершинное дерево, η ^ 3. Обозначим
через Vi множество всех листьев дерева Т. Если поддерево Г — Vi,
полученное из Τ удалением всех листьев вместе с инцидентными
им рёбрами, содержит не менее трёх вершин, то множество его
листьев обозначим V2, и т. д. В конце концов получим множество
Vrj содержащее менее трёх вершин. Вершины множества!^ будем
называть вершинами уровня i, причем уровень 1 будем считать
низшим, а уровень г — высшим.
Замечание 3.2. Всякая вершина уровня i, 1 < г < г, смеж-
на ровно с одной вершиной более высокого уровня и по меньшей
мере с одной вершиной более низкого уровня. Вершины одного
уровня смежны лишь в том случае, когда это уровень г, а дере-
во бицентральное.
Замечание 3.3. Множество Vr совпадает с центром дерева.
Замечание 3.2 следует из определения уровней, а замечание 3.3
является следствием теоремы 3.3.
В основе алгоритма Эдмондса лежит следующая процедура, с
помощью которой каждой вершине η-вершинного дерева Τ одно-
значно сопоставляется кортеж — конечная последовательность
натуральных чисел.
Заметим, что, приступая к кортежированию дерева, не обяза-
тельно заранее знать уровни его вершин, они выявляются в про-
цессе кортежирования.
52

Процедура кортежированил дерева
Итерация 1. Каждой вершине уровня 1 дерева Τ = {V, Ε) при-
писывается кортеж, состоящий из одного числа 1; при η = \V\ < 2
процедура заканчивается, а при η ^ 3 переходим на итерацию 2.
Итерация г (г ^ 2). Пусть все вершины уровней 1,2,..., г — 1
уже кортежированы, ν — вершина уровня г, a v\, г>2,..., vs — смеж-
ные с ней вершины низших уровней, расположенные в таком по-
рядке, что последовательность их кортежей
hll·1 l·1 h2h2 l·2 ИИ hs
^1^2 * * · *4(1)? Л1Л2 * * * Η(2)> ' — -> Л1Л2 · · * ^t(s)
является лексикографически невозрастающей. Припишем вер-
шине ν кортеж (А; + l)k\k\ · · · ^m^i^l · · · Щ<2) - * · ЩЬъ · ■ · Циу гДе
^ ~ Σ?=1 Ц. ~ сумма первых чисел кортежей.
Всё сказанное выполним для каждой вершины ν уровня г. По-
сле этого в случае г < г переходим на итерацию г + 1, а в случае
г — τ процедура заканчивается. Кортежи, сопоставленные цен-
тральным вершинам дерева, называются центральными. В слу-
чае бицентрального дерева соединяем кортежи центральных вер-
шин в один, приписывая лексикографически меньший кортеж к
лексикографически большему.
В дереве Τ на рис. 3.2 кортежированы вершины уровней 1
и 2. Две оставшиеся вершины (центральные) получают кортежи
С\ = 7311211 и С2 — 641111. Таким образом, центральный кортеж
дерева Τ равен с(Т) = 7311211641111.
Если ν — произвольная вершина уровня г, 1 < г ^ г, а е —
ребро, соединяющее её с вершиной более высокого уровня или
центральное ребро (в случае г = г), то ν-поддеревом Τν дерева Г
называется та из двух компонент подграфа Τ — е, которая содер-
жит вершину ν; если же ν — единственная центральная вершина
центрального дерева Т, то ^-поддерево совпадает с деревом Т.
Замечание 3.4. Для любой вершины υ дерева Τ длина её кор-
тежа совпадает с его первым числом, а оно равно числу вершин
в ν-поддереве Τν (доказывается индукцией по г).
53

Теорема 3.4 (Эдмондс). Два дерева изоморфны тогда и
только тогда, когда совпадают их центральные кортежи.
Доказательство. Необходимость. Если Τ = Τ7, то при лю-
бом изоморфизме φ этих деревьев множество V\ листьев дерева Τ
взаимно однозначно отображается на множество V{ листьев дере-
ва Т7, соответствуют друг другу также множества V<i и У2' (листья
поддеревьев Τ — V\ и Τ" — V{) и т. д. Поэтому соответствующие
вершины ν eVt и φ{ν) Ε Vt имеют одинаковый уровень и полу-
чают одинаковые кортежи. В частности, совпадают центральные
кортежи.
Достаточность. Пусть центральные вершины ν и г/ произ-
вольных деревьев ТиТ' имеют одинаковые кортежи. Докажем,
что ^-поддерево Τν дерева Г и. ^'-поддерево Т[, дерева V изоморф-
ны, причём изоморфизм можно установить так, чтобы вершина и
соответствовала вершине г/.
Действительно, по кортежу вершины ν однозначно восстанав-
ливаются кортежи смежных с ней вершин г>1,г>2,... ,vs низших
уровней, их количество и порядок следования, а в поддереве Tv
это все вершины, смежные с v. To же самое справедливо и для
вершин Vi,V2,...,v'3i смежных с ν' в поддереве Ту Значит, если
кортежи вершин ν и vf совпадают, то совпадают и кортежи вер-
шин Vj и Vp j = 1,2,..., 5. Применяя далее к каждой паре г^·, vfj
невисячих вершин такое же рассуждение, что и к паре г>, г/, мы в
конце концов продолжим соответствие до требуемого изоморфиз-
ма между деревьями Tv и Ту
Если деревья Τ и Τ — центральные, то Τ = Τ', так как Τ = Τν
иТ' = ТУ Если же деревья ГиГ7- бицентральные, то повторим
доказательство для второй пары центральных вершин деревьев Τ
и Т". Ясно, что из изоморфизма поддеревьев центральных вершин
следует изоморфизм деревьев Τ и Т\
Теорема доказана. ■
54

Упражнения
3.1. Верен ли критерий:
Граф G является деревом тогда и только тогда, когда некото-
рая его вершина соединена с каждой из остальных единственной
простой цепью?
3.2. Верен ли критерий:
Нетривиальный граф G является деревом тогда и только тогда,
когда G связен и любое его ребро является мостом?
3.3. Верен ли критерий:
Нетривиальный граф G является деревом тогда и только тогда,
когда G связен и любая его невисячая вершина является точкой
сочленения?
3.4. Перечислить все помеченные и непомеченные деревья
а) с 3 вершинами; б) с 4 вершинами.
3.5. Перечислить все непомеченные деревья с 5 вершинами.
3.6. Перечислить все непомеченные деревья
а) с б вершинами; б) с 7 вершинами.
3.7. Перечислить все непомеченные деревья с 8 вершинами.
3.8. Имеется 50 городов, между некоторыми из них проложе-
ны дороги с двусторонним движением. Из любого города можно
проехать в любой другой, причём по единственному маршруту.
Сколько всего имеется дорог?
3.9. У царя Салтана было два сына, звали их Гвидон и Дадон,
и дочь Василиса. Дадона и обоих его сыновей сгубила Шамахан-
ская царица, а из всех остальных детей и внуков царя Салтана
трое имели по трое детей, двое — по двое, а ещё один — одного
ребенка. Сколько всего внуков и правнуков было у царя Салтана?
(В ответе указать общее число внуков и правнуков.)
3.10. Старая мудрая Амёба поделилась пополам. Из всех её
потомков 100 тоже поделились пополам, а все остальные, за ис-
ключением одной маленькой амёбы, были проглочены злобными
головастиками. Сколько потомков старой Амёбы были проглоче-
ны головастиками?
55

3.11. В некотором поселке 1000 жителей. Ежедневно каждый
из них делится узнанными накануне новостями со всеми своими
знакомыми. Любая новость становится известной всем жителям
поселка. Доказать, что можно выбрать 90 жителей так, что если
одновременно всем им сообщить какую-то новость, то через 10
дней она станет известной всем жителям поселка.
3.12. Доказать, что любое дерево Τ имеет не менее Δ(Τ) ли-
стьев, где Δ(Τ) — наибольшая степень вершин дерева Т.
3.13. Вычислить код Прюфера дерева, изображённого
а) на рис. 3.3 (а) ; б) на рис. 3.3 (б).
8 £ L3 \2 ц_Ю
1 а а
б 13 12 11Д(
Д_Д 9id j j %
(а) (б)
Рис. 3.3.
3.14. Изоморфны ли деревья с кодами Прюфера
а) 122333 и 322111; б) 344555 и 455666?
3.15. Доказать утверждение замечания 3.4.
3.16. С помощью алгоритма Эдмондса выяснить, изоморфны
ли деревья, изображённые на рис. а) 3.4; б) 3.5.
•—·—· · · · ·—·
~4тг 'III'
Г'
\1
Рис. 3.4.
Рис. 3.5.
56

3.17. С помощью алгоритма Эдмондса выяснить, изоморфны
ли деревья, изображённые на рис. а) 3.6; б) 3.7; в) 3.8.
ψ, ν
ш
J 1 1
'Ν"
WW
Рис. З.б.
Рис. 3.7.
, Η Η Η 1
• 9 · ·— + » ·
г
^-ГЛУ
чг
11 τ τ i τ i
Рис. 3.8.
п~г
V
3.18. Восстановить дерево по его кортежу:
а) 641111631121; б) ТТ4211411121.
3.19. Восстановить дерево по его кортежу:
а) 731121154111; б) 1253111521111.
57

4. Связность
4.1. Вершинная и рёберная связность
Расмотрим два инварианта графа, характеризующие его «степень
связности».
Вершинной связностью или просто связностью нетривиаль-
ного графа G называется наименьшее число я{0) вершин гра-
фа G, в результате удаления которых получается несвязный или
тривиальный граф. Для тривиального графа 0\ по определению
полагаем я(0\) = 0. Из этого определения следует, что связность
несвязного графа равна 0, связность любого дерева равна 1, связ-
ность простого цикла х(Сп) = 2, а я(Кп) = η — 1 для любого
η ^2.
Граф G, изображённый на рис. 4.1, связен, но его связность
можно нарушить, удалив одну вершину. Если же попытаться на-
рушить связность этого графа путём удаления рёбер, то придётся
удалить не менее трёх рёбер.
4 7
Рис. 4.1.
Рёберной связностью нетривиального графа G называется
наименьшее число \{G) рёбер графа G, в результате удаления
которых получается несвязный граф. По определению полагаем
\{0\) — 0. Из определения сразу получаем, что рёберная связ-
ность несвязного графа равна 0, рёберная связность любого де-
рева равна 1, рёберная связность простого цикла \{Сп) = 2, а
Х(Кп) = η — 1 для любого η ^ 2. .
Для графа G, изображённого на рис. 4.1, >c{G) — 1 < 3 = X(G).
В 1932 г. Уитни показал, что обратное неравенство невозможно.
58

Теорема 4.1 (основное неравенство связности). Для
любого графа G — (V, Е)
>c{G) ^ A(G).
Доказательство. Если G — несвязный или тривиальный
граф, то >c(G) = X(G) = 0. Пусть G нетривиален и связен, следо-
вательно, X(G) ^ 1. Выберем в G множество L С Е, состоящее из
λ — A(G) рёбер, в результате удаления которых из графа G полу-
чается несвязный граф G — L. Из определения рёберной связности
и леммы 2.2 (об удалении ребра) следует, что граф G — L имеет
ровно две компоненты связности, причём концы любого ребра из
L принадлежат разным компонентам. Обозначим через Vi множе-
ство вершин i-й компоненты связности графа G — L, г = 1,2, и
пусть \Уг\ < \V2\.
Для каждого ребра из L выберем одну инцидентную ему вер-
шину следующим образом. Если jVi| = 1, то все выбранные вер-
шины лежат в 14, а если \Vi\ > 1, то вершины выбраны так, что-
бы среди оставшихся были вершины и из Vi, и из V^ Множе-
ство выбранных таким образом вершин обозначим U. Понятно,
что \U\ ^ λ. Удалим из G вершины множества U вместе с инци-
дентными им рёбрами. При этом из G будут удалены все рёбра
множества L и, может быть, ещё какие-то рёбра графа G. Заме-
тим, что полученный граф G—U несвязен или тривиален, поэтому
*{G)^\U\^\ = \{G).
Теорема доказана. ■
4.2. fc-связные графы. Критерии 2-связности
Граф G называется к-связным, если >c{G) > fc, и к-рёберно-связ-
ным, если λ (б?) ^ к.
По определению, если граф fc-связен, то он (к — 1)-связен, ... ,
2-связен и 1-евязен; нетривиальный граф 1-связен тогда и только
тогда, когда он связен.
59

Замечание 4.1. Из основного неравенства связности следу-
ет, что если граф к-связен, то он и к-рёберно -связен.
Вершина ν связного графа G называется точкой сочленения
или шарниром, если граф G — ν несвязен. Ребро с аналогичным
свойством называется мостом.
В теории графов 2-связным графам отводится особая роль,
прежде всего из-за многочисленных приложений. Дело в том,
что коммуникационные сети, граф-моделями которых являются
2-связные графы, уже достаточно надёжны, но ещё довольно дё-
шевы.
Известно довольно много критериев 2-связности графа. Неко-
торые из них приведены в следующей теореме.
Теорема 4.2 (критерии 2-связности). Пусть G=(V,E) —
связный η-вершинный граф, η ^ 3. Тогда следующие утвержде-
ния эквивалентны:
1) G' — 2-связный граф;
2) G не содержит точек сочленения;
3) любые две вершины графа G принадлежат некоторому про-
стому циклу;
4) для любых трёх вершин графа G существует простая цепь,
соединяющая любые две из них и проходящая через третью.
Доказательство. 1) =*► 2) Очевидно, так как если бы связный
граф G содержал точку сочленения, то его связность была бы
равна 1.
2) => 3) Пусть связный граф G не содержит точек сочлене-
ния, 5, t — две его произвольные вершины. Докажем вначале, что
в G непременно существует простой цикл, содержащий вершину 5.
Для этого заметим, что s не может быть висячей вершиной, ина-
че единственная смежная с ней вершина графа G была бы точкой
сочленения. Следовательно, d(s) ^ 2; пусть и, ν — две вершины,
60

смежные с s. Поскольку вершина s не является точкой сочлене-
ния, то в графе G — s существует простая (и, г>)-цепь. Эта цепь
вместе с рёбрами su и sv образует простой цикл, содержащий s.
Рассмотрим все простые циклы графа G, содержащие вершину
5, и обозначим через U множество всех вершин, входящих в эти
циклы. Осталось показать, что t £ U.
Предположим противное, т. е. t φ U. Пусть и — вершина в С/,
для которой расстояние d(u, t) минимально, и пусть Р$ — кратчай-
шая простая (и, £)-цепь, a Pi, Р<х — две простые (s, и)-цетт цикла,
содержащего s и и (рис. 4.2(a)).
(а) (б)
Рис. 4.2.
В силу условия 2) вершина и не является точкой сочленения,
поэтому граф G — и связен. Значит, в нём существует простая
($,£)~цепь Р, не содержащая и (рис. 4.2(6)). Обозначим через ν
ближайшую к s вершину цепи Р, которая также принадлежит Pq
(возможно, ν = £), а через w — последнюю вершину (s, ^-фраг-
мента цепи Р, которая принадлежит Pi или Ръ (возможно, w — s).
Для определённости будем считать, чтоги принадлежит Pi. Тогда
(s, и?)-фрагмент цепи Pi, (w, ^-фрагмент цепи Р, (г>, и)-фрагмент
цепи Ро и цепь Ръ вместе образуют простой цикл. Поэтому ν Ε U.
Так как υ Φ и< то d(v,t) < d(u,t), но это противоречит выбору
вершины и. Итак, t G U,
3)^4) Пусть и, ь\ w G V — произвольные вершины графа G.
Докажем, что в G существует простая (и, г»)-цепь, проходящая че-
рез вершину w. По условию граф G связен, следовательно, в нём
существует простая (u,w)-u£Ub P. В силу условия 3) существует
простой цикл С, содержащий вершины v, w. Если и £ С, то усло-
61

вие 4) выполнено, так как (г*, г^-фрагмент цикла С содержит w.
Поэтому будем считать, что и £ С. Пусть z — первая, считая от
и, вершина (it, гу)-цепи Р, принадлежащая циклу С (возможно,
z — w). Тогда искомая (и, г/)-цепь образована (иу <г)-фрагментом
цепи Ρ и (z, г;)-фрагментом цикла С, содержащим вершину w.
4) => 1) Для доказательства 2-связности графа G = (V, Е)
достаточно показать, что для любой вершины ν £ V подграф
G—v связен. Рассмотрим произвольные вершины и, w графа G—ν
и докажем, что они соединимы в G—v. По утверждению 4) в графе
G есть простая (щ г>)-цепь, проходящая через вершину w. Тогда
(и, ги)-фрагмент этой цепи не проходит через υ и, следовательно,
является простой {и, и?)-цепью в графе G — v. Поэтому граф G
2-связен.
Теорема доказана. ■
Замечание 4.2. Если в формулировке и доказательстве
теоремы 4-2 заменить «точки сочленения» на «мосты» и «про-
стые циклы и цепи» на «циклы и цепи», то получим аналогичные
критерии рёберной 2-связности графа.
Критерии ^-связности и рёберной ^-связности графа для любо-
го k ^ 2 будут получены в следующем параграфе как следствия
теоремы Менгера.
4.3. Отделимость и соединимость. Теорема Менгера
Классическая теорема, о которой пойдёт речь в этом параграфе,
была в 1927 г. доказана К. Менгером в топологических терминах.
Последующие доказательства этой теоремы, а также её вариантов
и обобщений на языке теории графов были основаны на ориги-
нальных идеях, оказавших заметное влияние на развитие теории
графов.
Пусть G = (К, Е) — связный граф, s,t — две его несмежные
вершины. Говорят, что множество вершин W С V разделяет вер-
шины Sjt, если они принадлежат разным компонентам связности
62

графа G—W, полученного из G удалением всех вершин множества
W вместе со всеми инцидентными им рёбрами. Несмежные вер-
шины s, t называются к-отделимыми, если к равно наименьшему
числу вершин, разделяющих s я t. Говорят также, что отдели-
мость вершин s,£ равна к.
Две простые цепи, соединяющие вершины s, t называются
вершинно-независимыми, если они не имеют общих вершин, от-
личных от 5 и ε. Вершины s,t называются l-соединимымщ если
наибольшее число вершинно-независимых (.s, £)-цепей равно /. Го-
ворят также, что в этом случае соединимость вершин s, t равна I.
Сформулируем как гипотезу следующее утверждение, справед-
ливость которого будет установлена в дальнейшем.
Гипотеза. Если несмежные вершины s, t связного графа
к-отделимы, то в этом графе существует к вершинно-независи-
мых простых (s, t)-цепей (т.е. их соединимость не меньше к).
Очевидно, что гипотеза верна для к = 1. Допустим, что гипо-
теза неверна для некоторого к = I ^ 2, и рассмотрим связный
граф G с наименьшим числом вершин, для которого при к = I
гипотеза неверна. Будем удалять из G рёбра до тех пор, пока не
получим такой граф Я, что для разделения вершин s, t в графе
Я требуется / вершин, а для разделения s,i в графе Я — е, где
е — произвольное ребро графа Я, уже достаточно I — 1 вершин.
Построенный таким образом граф Я назовём гипотетическим.
Изучим свойства графа Я. Первые четыре свойства выполнены
по построению графа Я.
Свойства гипотетического графа.
Свойство 1. Вершины s,t в графе Я /-отделимы.
Свойство 2. Вершины s, t в графе Я не являются Ζ-соедини-
мыми (т. е. их соединимость меньше/).
Свойство 3. Граф Я имеет наименьшее число вершин среди
всех графов, обладающих свойствами 1 и 2 (т. е. среди всех гра-
фов, для которых при к = / гипотеза неверна).
63

Свойство 4. Для всякого ребра е в графе Я — е для разделения
вершин s,t достаточно / — 1 вершин.
Свойство 5. Любое множество W вершин графа Я, содержа-
щее I вершин и разделяющее s и £, смежно либо с s, либо с t
(множество W называется смежным с вершиной 5, если каждая
вершина w EW смежна с s).
Докажем свойство 5. Предположим противное, и пусть W —
множество вершин, разделяющее вершины 5,i и состоящее из /
вершин, но не смежное ни с s, ни с t. Простую цепь, соединяю-
щую 5 с некоторой вершиной w € W и не содержащую других
вершин из W, назовём (s, ]№)-цепъю. Аналогично определяется
(W, Ь)-цепъ.
Заметим, что любая вершина w £ W входит в некоторую
(s, ]¥)-цепъ и в некоторую (W, £)-цепь. Иначе всякая (s, £)-цепь
либо вовсе не проходит через w, либо проходит через w, но со-
держит ещё какую-то вершину из W. Ив том и в другом случае
множество W \ {w} разделяет s и i, что невозможно, так как вер-
шины 5, t являются Ζ-отделимыми (свойство 1).
Заметим также, что любая (s, И^)-цепь и любая (W, £)-цепь ли-
бо вовсе не имеют общих вершин, либо пересекаются по един-
ственной вершине из W. В противном случае в Я нашлась бы
(s, £)-цепь, не содержащая вершин из W, и W не было бы разде-
ляющим множеством.
Так как множество W не смежно ни с s, ни с i, то среди вер-
шин всех (s, Ж)-цепей есть вершины, не принадлежащие множе-
ству W U {s}, и среди вершин всех (W, £)-цепей есть вершины, не
входящие в И^и{£}. Рассмотрим два новых графа: Щ, образован-
ный рёбрами всех (s, Ж)-цепей и I рёбрами вида {wt : w £ И^},
и Яг, образованный рёбрами всех (W, £)-цепей и I рёбрами вида
{sw : w € W}. Заметим, что вершины s, t являются /-отделимы-
ми в графах Ях и Нч (если бы в каком-то из этих графов можно
было разделить вершины s,i, удалив множество U, содержащее
менее / вершин, то это же множество U разделяло бы вершины
64

s,t и в графе Я). Каждый из графов #ь #2 имеет меньше вер-
шин, чем граф Я, поэтому в силу свойства 3 для графов Н\ и
Hi при к = I верна гипотеза: из /-отделимости вершин 5, t следует
существование I вершинно-независимых (s, £)-цепей, Тогда (s, W)~
фрагменты этих цепей из графа Н\ вместе с (И/, ^-фрагментами
этих цепей из графа Я2 образуют I вершинно-независимых (s,i)-
цепей в графе Я, что противоречит свойству 2. Свойство 5 дока-
зано.
Теорема 4.3 (Менгер). В связном графе несмежные вер-
шины к-отделимы тогда и только тогда, когда оник-соединимы.
Доказательство. Необходимость. Ясно, что если к вершин
разделяют s и i, то существует не более к вершинно-независимых
простых (s, £)-цепей. Таким образом, необходимость будет доказа-
на, если будет доказана сформулированная ранее гипотеза.
Докажем гипотезу индукцией по к. Для к — 1 она очевидна.
Предположим, что гипотеза верна для всех значений к < /, и
докажем её для к = I ^ 2. Допустим противное, что гипотеза
для к = I неверна, и как ранее построим гипотетический граф
Я = (Vff, Ен), обладающий свойствами 1 — 5.
Заметим, что любая вершина ν графа Я, отличная от s и £,
обладает следующим свойством:
если sv 6 Ен, то vt $ Ен- (4.1)
Докажем свойство (4.1) от противного. Предположим, что в Я
существует вершина ν, смежная как с s, так и с t. Поскольку ν
обязательно должна входить в любое разделяющее множество, то
в графе Я — ν для разделения s, t достаточно I — 1 вершин, и по
предположению индукции в Я — ν существует I — 1 вершинно-
независимых (s, £)-цепей. Добавляя вершину ν с рёбрами sv и vt,
получим I вершинно-независимых ($, £)-цепей в графе Я, что про-
тиворечит свойству 2 гипотетического графа Я. Свойство (4.1)
доказано.
65

Пусть Ρ — (s,ui,ii2,. · · ,£) — кратчайшая (з,£)-цепь в графе
Я. В силу (4.1) щ Φ t. Обозначим е = щщ. По свойству 4 гипо-
тетического графа Η существует множество С/, содержащее / — 1
вершин, которое в графе Η — е разделяет s и t. По свойству 1
множество U не разделяет вершины (s,£) в графе #, поэтому в
Η — U существует хотя бы одна (s,£)-ii,enb, причём любая такая
цепь должна содержать ребро е = щщ (так как она не является
(з,£)-цепью в графе Η — е). Поэтому множества W\ = U U {^i}
и VK2 = i/ U {г^} разделяют вершины s и i в Я и, содержат по /
вершин.
Из (4.1) следует, что щЬ <£ Ен- Тогда, используя свойство 5 для
Wi, получаем sw G Ен для всех w G U. Следовательно, в силу
(4.1) wt g Ен для всех w £ U. Но тогда, применяя свойство 5 к
И^2, получим SU2 € Ен, что противоречит выбору Ρ как кратчай-
шей (5,^)-цепи в Н. Противоречие.
Противоречие возникло, потому что мы предположили, что
при к = I гипотеза неверна. Значит, она верна. Необходимость
доказана.
Достаточность. Пусть вершины s, t ^-соединимы. Очевидно,
что тогда отделимость этих вершин не меньше к. Если бы отдели-
мость вершин s и t была равна I > к, то по доказанной гипотезе
в графе существовало бы / > к вершинно-независимых простых
(s7 £)-цепей. Противоречие.
Теорема доказана. ■
Из теоремы Менгера непосредственно вытекает следующий
критерий.
Следствие 4.1 (критерий ^-связности графа). Граф G
к'Связеп тогда и только тогда, когда любая пара его вершин
соединена не менее, чем к вершинно-независимыми цепями.
66

4.4. Рёберный аналог теоремы Менгера
Поскольку соединимость вершин в графе можно нарушить, уда-
ляя не только вершины, но и рёбра, естественно рассмотреть рё-
берные аналоги понятий соединимости и отделимости пары вер-
шин.
Пусть G = (V, Е) — связный граф, s, t — две его произвольные
вершины. Две простые цепи, соединяющие вершины s,i, назы-
ваются рёберно-независимыми, если они не имеют общих рёбер.
Вершины s, t называются l-рёберно-соединимымщ если наиболь-
шее число рёберно-независимых (s, £)-цепей равно I.
Говорят, что множество рёбер R С Ε разделяет вершины
5, £, если 5, t принадлежат разным компонентам связности графа
G — R. Вершины s, t называются к-рёберно-отделимыми, если к
равно наименьшему числу рёбер, разделяющих s и t.
Теорема 4.4 (рёберный аналог теоремы Менгера). В
связном графе G две вершины к-рёберно-отделимы тогда и
только тогда, когда они к-рёберно-саединимы.
Доказательство теоремы 4.4 легко получить, используя тео-
рему Менгера. С этой целью сопоставим графу G граф G', ко-
торый получается из G следующим образом. Каждая вершина
ν € Vq заменяется группой из da{v) попарно смежных вершин
графа G\ а рёбра графа (?', соединяющие вершины из разных
групп, попарно несмежны и находятся во взаимно однозначном
соответствии с рёбрами графа G (рис. 4.3).
Рис. 4.3.
Теперь доказательство теоремы 4.4 непосредственно вытекает
из следующей простой леммы.
67

Лемма 4.1. Для любых вершин s,t связного графа G в гра-
фе G1 существуют такие несмежные вершины s', t1 из групп,
соответствующих s, t, что
1) вершины , t k-рёберно-отделимы в графе G тогда и только
тогда, когда вершины s\t* k-отделимы в графе G';
2) вершины s, t k-рёберно-соединимы в графе G тогда и толь-
ко тогда, когда вершины s',£' k-соединимы в графе Q.
В качестве s\ tf можйо взять любую пару несмежных вершин
из групп, соответствующих s,i. ■
Следствие 4.2 (критерий рёберной fc-связности графа).
Граф k-рёберно-связен тогда и только тогда, когда любая пара
его вершин соединена не менее, чем к рёберно-независимыми
цепями.
К сожалению, приведённые доказательства теорем 4.3 и 4.4 не
являются конструктивными в том смысле, что не дают ни спосо-
ба получения максимального числа независимых простых цепей
между двумя вершинами графа G, ни способа отыскания величин
x(G), X(G). Эти задачи могут быть решены с помощью потоковых
алгоритмов.
Упражнения
4.1. Доказать, что для любого графа верны неравенства
k{G) ^ 6(G), X(G) ^ 6(G),
где 6(G) — минимальная степень вершин графа G.
4.2. Как велика может быть разность \{G) — >c{G) в
η-вершинном графе G?
4.3. Найти вершинную и рёберную связность графов пяти
Платоновых тел.
4.4. Найти вершинную и рёберную связность графа Петерсе-
на.
68

4.5. Найти вершинную и рёберную связность графа, изобра-
женного на рис. a) 4.4(a); б) 4.4(6).
4 3 4
(а) (б)
Рис. 4.4.
4.6. Доказать, что для любого связного кубического графа G
справедливо равенство >c{G) = X(G).
4.7. Верна ли гипотеза:
Для любого связного кубического графа G справедливо равенство
*(G) = A(G) = 3?
4.8. Какое наибольшее число точек сочленения может быть
в η-вершинном графе?
4.9. Какое наибольшее число мостов может быть в
η-вершинном графе?
4.10. Доказать критерий:
Связный граф G 2-связен тогда и только тогда, когда для любых
трёх вершин графа G существует простая цепь, соединяющая
любые две из них и не проходящая через третью.
4.11. Верен ли следующий критерий:
Связный граф G 2-рёберно-связен тогда и только тогда, когда
для любых трёх вершин графа G существует цепь, соединяющая
любые две из них и не проходящая через третью?
4.12. Доказать, что в 3-связном графе через любые три вер-
шины проходит простой цикл.
4.13. Доказать утверждение следствия 4.1.
4.14. Доказать утверждение следствия 4.2.
69

5. Ориентированные графы
В приложениях часто приходится рассматривать графы с ориен-
тированными рёбрами. Примерами таких графов могут служить
граф-модели сети автодорог с односторонним движением, сетевые
графики выполнения работ и т. д.
5.1. Основные понятия
Ориентированный граф (орграф) G состоит из непустого конечно-
го множества V и конечного множества Ε С V х V упорядоченных
пар элементов множества V. Обозначение: G = {V,E).
Элементы множества V называются вершинами, а элементы
множества Ε — дугами орграфа G.
Если е = uv — дуга, то вершина и называется началом дуги е,
а ν — её концом. Говорят, что дуга е инцидентна вершинам и, v.
Говорят также, что дуга е выходит из вершины и и заходит в
вершину v.
Вершины называются смежными, если одна из них является
началом, а другая— концом некоторой дуги. Дуги называются
смежными, если они имеют общую вершину.
Пусть G = (V, Е) — орграф и ν € V. Полустепенью исхода
d+(v) вершины ν называется число дуг, выходящих из ν, а по-
лустепенью захода d"(v) — число дуг, заходящих в v. Степень
вершины ν — это число инцидентных ей дуг: d(v) = d+(v) + d"(v).
Следующее утверждение является ориентированным аналогом
леммы 2.1 о рукопожатиях.
Лемма 5.1 (орлемма о рукопожатиях). Сумма полу сте-
пеней исхода всех вершин орграфа G = (К, Е) равна сумме полу-
степеней захода и равна числу дуг орграфа:
Σ<1+{ν) = Σα-{ν) = \Ε\.
vev vev
70

Доказательство легко получается по индукции, так как каж-
дая дуга добавляет по единице в первую и во вторую сумму. ■
Подграфом орграфа G = (V, Е) называется любой орграф Η =
(f/, D) такой, что U С V, D С Ε (обозначается Η С G). Подграф
Η — (U, D) называется порождённым подграфом орграфа G =
(V, Е), если он обладает следующим свойством:
Vit, v e U uv e D <=> uv e E.
Орграфы G = (Vq, Eg), Η = (V#, Eh) называются изоморфны-
ми (записывается G = Я), если между множествами их вершин
существует взаимно однозначное соответствие φ : Vq —> V#, со-
храняющее смежность, т. е.
Ми, ν е Vg uv e EG <=> φ(υ)φ{υ) € ΕΗ·
Пусть G = (Vy Ε) — орграф. Ориентированным маршрутом
(ормаршрутом) в орграфе G называется чередующаяся последо-
вательность его вершин и дуг
Ρ = (г>ь еь г>2, е2, г^,..., vk, ek, vfc+i), (5.1)
в которой е* = ViVi+i — дуга орграфа G, г = 1,..., к. Ормаршрут
Ρ называется также ориентированным (vi^Vk+i)-маршрутом.
Длина такого маршрута равна числу к его дуг. Ормаршрут Ρ
называется замкнутым, если υ\ ~ ν*+1·
Если в орграфе нет кратных дуг, то ормаршрут (5.1) мо-
жет быть задан последовательностью входящих в него вершин
(г?1,г>2?..., г>&, г%+1). В любом случае ормаршрут (5.1) можно за-
дать последовательностью дуг (еь ег,..., е&).
Ориентированный маршрут называется орцепъю, если в нём
все дуги различны, и простой орцепью (или путём), если все его
вершины различны. Замкнутая орцепь называется орциклом, а
замкнутый путь — контуром.
71

Последовательность (5.1) вершин и дуг орграфа G = (V, Е)
называется полумаршрутом, если для любого г — 1,..., к ли-
бо ег· =■ ViVi+i £ i?, либо вг = Vi+i^i € £*. Аналогично определяют-
ся полупуть и полуконтур.
Орграф называется обыкновенным, если он не содержит петель
и кратных дуг. Направленный орграф— это орграф, не имеющий
симметричных пар дуг, т. е. дуг вида uv и vu.
Неориентированный мультиграф, полученный из орграфа G
снятием ориентации всех дуг, называется основанием орграфа G и
обозначается Gb- Очевидно, что основанием направленного обык-
новенного орграфа является обыкновенный граф.
Примеры ориентированных графов.
1. Пустой орграф — это орграф без дуг; то же, что и пустой
неориентированный граф. Тривиальный орграф —- то же, что и
тривиальный неориентированный граф, состоящий из одной вер-
шины.
2. Полный орграф — это обыкновенный орграф, в котором лю-
бые две вершины соединены симметричной парой дуг. Полный
η-вершинный орграф обозначается КП7 число дуг в таком оргра-
фе равно п(п — 1).
3. Турнир — направленный орграф, основанием которого яв-
ляется полный граф. Число дуг в η-вершинном турнире равно
п(п—1)
2 *
5.2. Достижимость и связность
Существует три различных понятия связности орграфа.
Если в орграфе G = {УуЕ) существует ориентированный
(и, *;)-маршрут, то говорят, что вершина ν достижима из вер-
шины и. Любая вершина считается достижимой из самой себя.
Орграф называется сильно связным (или сильным), если лю-
бые его две вершины взаимно достижимы. Огрграф называется
72

односторонне связным (или односторонним), если для любой па-
ры его вершин хотя бы одна достижима из другой. Орграф назы-
вается слабо связным (или слабым), если любые две его вершины
соединены полу маршрутом. Орграф называется несвязным, если
он даже не является слабым.
На рис. 5.1(a) изображён сильно связный орграф, на
рис. 5.1(6) — односторонне связный (в нём вершина^ недостижи-
ма из г>2), а на рис. 5.1(b) — слабо связный орграф (в нём вершины
ν2 и V4 взаимно недостижимы).
г;4 v\ V4 vi V4 v\
Тривиальный орграф, состоящий из одной вершины, считается
одновременно сильным, односторонним и слабым.
Замечание 5.1. Каждый сильный орграф является одно-
сторонним, а каждый односторонний — слабым.
Замечание 5.2. Орграф несвязен тогда и только тогда, ко-
гда его основание — несвязный граф.
Ормаршрут или полумаршрут, содержащий все вершины ор-
графа, называется остовным.
Теорема 5.1 (критерий сильной связности). Орграф яв-
ляется сильно связным, если и только если в нём есть остовныи
замкнутый ормаршрут.
Доказательство. Необходимость. Пусть G = (V,E) —
сильно связный орграф иС= (vi, г'2,..., г%, v\) — замкнутый ор-
маршрут в (7, проходящий через максимально возможное число
73

вершин. Предположим, что этот ормаршрут не является остов-
ным, и рассмотрим некоторую вершину ν, не входящую в С.
Так как G — сильно связный орграф, то в нём существуют
ориентированный (г>1,г/)-маршрут Pi = (t>i,«2,... ,Ир, ν) и ори-
ентированный (г>, ^-маршрут Р2 = (г;, w2l.. - 7wq,vi). Но тогда
замкнутый ормаршрут
С" = (vu v2,..., vk, уъ иъ..., г/р, v, w2)..., wff, vi)
содержит большее, чем С, число вершин, что противоречит выбо-
ру ормаршрута С. Следовательно, С — остовный ормаршрут.
Достаточность. Пусть и> ν — две произвольные вершины
орграфа G, а С = (vi, i>2, ·«♦, и,..., ν,..., vny v{) — остовный
замкнутый ормаршрут. Тогда вершина ν достижима из и по
(и, г;)-фрагменту ормаршрута С, а вершина и достижима из ν по
(ν, ^-фрагменту С.
Теорема доказана. ■
Столь же просто доказываются следующие критерии односто-
ронней и слабой связности орграфа.
Теорема 5.2 (критерий односторонней связности).
Орграф является односторонне связным, если и только если в
нём есть остовный ормаршрут.
Теорема 5.3 (критерий слабой связности). Орграф яв-
ляется слабо связным, если и только если в нём есть остовный
полумаршрут.
5.3. Эйлеровы и гамильтоновы орграфы
Основные результаты об эйлеровых и гамильтоновых циклах в
неориентированных графах переносятся на ориентированные гра-
фы.
Орцикл, содержащий каждую дугу орграфа, называется эйле-
ровым орциклом. Орграф называется эйлеровым, если в нём есть
эйлеров орцикл.
74

Следующая теорема доказывается так же, как и в неориенти-
рованном случае.
Теорема 5.4 (критерий эйлеровости орграфа). Слабо
связный орграф является эйлеровым, если и только если для
каждой его вершины ν верно равенство d*(ν) = d~{v).
Контур (путь) в орграфе называется гамильтоновым, если он
содержит все вершины орграфа. Орграф называется гамильтоно-
вым, если в нём есть гамильтонов контур, и полугамильтоновым,
если в нём есть гамильтонов путь.
Следующие две теоремы, дающие достаточные условия гамиль-
тоновости орграфа, можно рассматривать как ориентированные
аналоги теорем Оре и Дирака (теоремы 1.2 и 1.3), однако их до-
казательство намного сложнее.
Теорема 5.5 (Мейниел). Пусть G — сильно связный
η-вершинный обыкновенный орграф, η ^ 2. Если для любой
пары его несмежных вершин и, ν справедливо неравенство
d(u) + d{v) ^ 2п — 1, то в G есть гамильтонов контур.
Теорема 5.6 (Гуйя-Ури). Пусть G — сильно связный
η-вершинный обыкновенный орграф, η ^ 2. Если для любой его
вершины υ справедливы неравенства d+(v) ^ η/2, d~(v) ^ η/2,
то в G есть гамильтонов контур.
Вообще, о гамильтоновых и полугамильтоновых орграфах из-
вестно немного. Как и в неориентированном случае, задачи распо-
знавания гамильтоновости и построения гамильтоновых контуров
и путей в произвольных орграфах гораздо сложнее, чем соответ-
ствующие задачи об эйлеровых орграфах. Однако, для турниров
эти задачи решаются довольно просто.
Теорема 5.7 (Редей). Всякий турнир полу гамильтонов.
Теорема 5.8 (Камион). Всякий сильно связный турнир га-
мильтонов.
75

5.4. Ориентированные варианты теоремы Менгера
Теорема Менгера может быть модифицирована для орграфов.
Пусть 5, t — две вершины слабо связного орграфа G = (V, Е).
Два (з,£)-пути называются вершинно-независимыми, если у
них нет общих вершин, отличных от s и t, и независимыми по
дугам, если они не имеют общих дуг.
Множество W вершин орграфа G называется (s, ^-разде-
ляющим, если в орграфе G — W вершина t не достижима из s.
Аналогично, множество R дуг орграфа G называется (s, t)-разде-
ляющим, если в орграфе G — R вершина t не достижима из s.
Теорема 5.9 (ориентированная теорема Менгера).
Пусть G = (V,E) — слабо связный орграф. Для любой пары
вершин s,t € V таких, что st ^ Е, наименьшее число вершин
в (s,i) -разделяющем множестве равно наибольшему числу
вершинно-независимых (s, t)-путей.
Теорема 5.10. Пусть G = (V,E) — слабо связный орграф.
Для любой пары вершин s,t G V наименьшее число дуг в
(s,i) -разделяющем множестве равно наибольшему числу неза-
висимых по дугам (s, t) -путей.
Доказательства этих теорем почти дословно, с учётом специ-
фики орграфов, повторяют доказательства теоремы Менгера и её
рёберного аналога (теоремы 4.3 и 4.4).
5.5. О проблеме восстановления орграфов
Было бы неправильно думать, что все утверждения, справедли-
вые для неориентированных графов, имеют аналоги для оргра-
фов. Ярким примером может служить гипотеза вершинного вос-
становления (гипотеза Улама). Как было указано в параграфе 2.3,
гипотеза Улама справедлива, за единственным исключением, для
всех неориентированных графов с небольшим числом вершин.
76

Для ориентированных графов гипотеза восстановления фор-
мулируется точно так же, как и для неориентированных. Однако,
для огрграфов гипотеза восстановления неверна, её опровержение
получено на турнирах. В 1967 г. Ф. Харари и Е. Палмер доказа-
ли, что при η ^ 5 любой η-вершинный турнир, не являющийся
сильным, однозначно восстанавливается по своей колоде. Но для
сильных турниров уже при η = 5 гипотеза неверна. На рис 5.2
изображена пара ^восстанавливаемых сильных турниров, т. е.
пара неизоморфных сильных турниров, имеющих одинаковые ко-
лоды. Позже П. Стокмейер нашел целое семейство невоестанав-
ливаемых сильных турниров.
Рис. 5.2.
Упражнения
5.1- Перечислить все попарно неизоморфные непомеченные
обыкновенные орграфы а) с 2 вершинами; б) с 3 вершинами.
5.2. Доказать теорему 5.2.
5.3. Доказать теорему 5.3.
5.4. Доказать теорему 5.4.
5.5. Орцепь, содержащая каждую дугу орграфа, называет-
ся эйлеровой. Сформулировать и доказать необходимое и доста-
точное условие существования эйлеровой орцепи в слабо связном
орграфе.
5.6. Пусть G — сильно связный η-вершинный обыкновенный
орграф, d(v) ^ η для любой его вершины v. Доказать, что тогда
в G есть гамильтонов контур.
77

5.7. Доказать теорему 5.7.
5.8. Доказать теорему 5.8.
5.9. Доказать теорему 5.9.
5.10. Доказать теорему 5.10.
5.11. Перечислить все попарно неизоморфные непомеченные
турниры а) с 3 вершинами; б) с 4 вершинами.
5.12. Доказать, что турниры, изображённые на рис. 5.2, не
изоморфны.
5.13. Проверить, что турниры, изображённые на рис. 5.2,
имеют одинаковые колоды.
5.14. Привести пример двух неизоморфных 4-вершинных
турниров, имеющих одинаковые колоды.
5.15. Вершина орграфа называется источником, если её по-
лустепень захода равна нулю, и стоком, если её полустепень ис-
хода равна нулю. Доказать, что в любом турнире может содер-
жаться не более одного источника и не более одного стока.
5.16. Доказать, что η-вершинный обыкновенный орграф
сильно связен, если для любой его вершины ν выполнены нера-
венства d+(v) ^ (η - 1)/2 и d'(v) ^ (п - 1)/2.
78

Список литературы
[1] Euler L. in: Commentationes Arithmetical Collectae. St. Peter-
burg, 1736. English transi.: Euler L. The Königsberg bridges //
Scientific American. V. 18. 1953.
[2] König D. Theorie der endlichen und unendlichen Graphen. Leipzig,
1936. Перепечатано в New York: Chelsea, 1950.
[3] Асанов M.О., Баранский В.А., Расин В.В. Дискретная матема-
тика: графы, матроиды, алгоритмы. СПб: Лань, 2010.
[4] Васильев Н.Б., Егоров A.A. Задачи Всесоюзных математиче-
ских олимпиад. М.: Наука, 1998.
[5] Дистель Р. Теория графов. Новосибирск: Изд-во Ин-та мате-
матики, 2002.
[6] Евстигнеев В.А., Мельников Л.С. Задачи и упражнения по тео-
рии графов и комбинаторике. Новосибирск: НГУ, 1981.
7] Емеличев В.А., Мельников О.И., Сарванов В.И., Тышке-
вич Р.И. Лекции по теории графов. М.: Наука, 1990.
8] Зыков A.A. Основы теории графов. М.: Наука, 1987.
9] Кюршак Й., Нейкомм Д., Хайош Д., Шурани Я. Венгерские
математические олимпиады. М.: Мир, 1975.
10] Математическая энциклопедия. Т. 1. М.: Сов. Энциклопедия,
1977.
11] Олехник С.Н., Нестеренко Ю.В., Потапов М.К. Старинные
занимательные задачи. М.: Наука, 1988.
12] Свами М, Тхуласираман К. Графы, сети и алгоритмы. М.:
Мир, 1984.
13] Уилсон Р. Введение в теорию графов. М.: Мир, 1977.
14] Харари Ф. Теория графов. М.: Мир, 1973. 2-е изд.: М., 2003.
15] Штейнгауз Г. Математический калейдоскоп. М.: Наука, 1981.
79

Учебное издание
Виктор Петрович Ильев
Теория графов. Вводный курс
Дизайн обложки З.Н. Образовой
Подписано в печать 28.12.2012. Формат 60 х 84 1/16.
Печ. л. 5,0. Усл. печ. л. 4,7. Уч.-изд. л. 3,6.
Тираж 150 экз. Заказ 410.
Издательство Омского государственного университета
644077, Омск-77, пр. Мира, 55а, госуниверситет
Отпечатано на полиграфической базе ОмГУ
644077, Омск-77, пр. Мира, 55а, госуниверситет

ОМСКОГО ГОСУДАРСТВЕННОГО
УНИВЕРСИТЕТА
В.П. Ильев
ТЕОРИЯ ГРАФОВ
ВВОДНЫЙ КУРС
Учебное пособие
9 785777 915276