Графы и их применение. Комбинаторные алгоритмы для программистов

Графы и их применение

2-е издание, исправленное

Костюкова Н.И.

Национальный Открытый Университет “ИНТУИТ”
2016

2

УДК 519.1(07)
ББК 16
К72
Графы и их применение. Комбинаторные алгоритмы для программистов / Костюкова Н.И. - M.:
Национальный Открытый Университет “ИНТУИТ”, 2016 (Основы информационных технологий)
ISBN 978-5-9556-0069-7

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

(c) ООО “ИНТУИТ.РУ”, 2007-2016
(c) Костюкова Н.И., 2007-2016

3

Основные понятия теории графов

Определение графа. Определение орграфа. Полный граф. Полный ориентированный
граф. Двудольный граф. Степень вершины. Связность графа. Задачи, приводящие к
графам

Определение графа

Графом 
 называется пара 
, где 
 — непустое конечное множество

элементов, называемых вершинами, а 
 — конечное семейство неупорядоченных

пар элементов из 
 (необязательно различных), называемых ребрами.

Употребление слова “семейство” говорит о том, что допускаются кратные ребра.
Будем называть 
 ” множеством вершин ” , а 
 — семейством ребер графа 
.

О каждом ребре вида 
 говорят, что оно соединяет вершины  и 
 Каждая петля 

 соединяет вершину  саму с собой.

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

Определение орграфа

Орграфом 
 называется пара 
, где 
 — непустое конечное множество

элементов, называемых вершинами, а 
 — конечное семейство упорядоченных пар

элементов из 
, называемых дугами (или ориентированными ребрами ). Дуга, у

которой вершина  является первым элементом, а вершина 
 — вторым, называется

дугой из  в 
 
. Заметим, что дуги 
 и 
 различны. Хотя графы и орграфы

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

Полный граф

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

Граф, не являющийся полным, можно преобразовать в полный с теми же вершинами,
добавив недостающие ребра. Вершины графа 
 и ребра, которые добавлены, тоже

образуют граф. Такой граф называют дополнением графа 
 и обозначают его 
.

Дополнением графа 
 называется граф 
 с теми же вершинами, что и граф 
, и с

теми и только теми ребрами, которые необходимо добавить к графу 
, чтобы

получился полный граф.

4

Является граф полным или нет, это его характеристика в целом.

Полный ориентированный граф

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

Рассмотрим соревнование, в котором каждая из команд играет с каждой из остальных
команд по одному разу. Такое соревнование называют круговым турниром или
турниром в один круг.

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

Каждому турниру соответствует полный ориентированный граф, в котором вершины
представляют команды, а каждое ориентированное ребро 
 выражает отношение

”  победила 
 “.

Двудольный граф

Допустим, что множество вершин графа можно разбить на два непересекающихся
подмножества 
 и 
, так, что каждое ребро в 
 соединяет какую-нибудь вершину из

 с какой-либо вершиной из 
, тогда 
 называем двудольным графом. Такие графы

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

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

вершиной из 
 ; если же это так и если при этом граф 
 простой, то он называется

полным двудольным графом и обычно обозначается 
, где 
 — число вершин

соответственно в 
 и 
.

Пример.

5

Заметим, что граф 
 имеет ровно 
 вершин и 
 ребер.

Степень вершины

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

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

этом вершины  и 
 называются инцидентными этому ребру, а ребро — инцидентным

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

инцидентных  ; степень вершины будем обозначать через 
. При вычислении

степени вершины  будем учитывать петлю в  два раза, а не один. Вершина степени 

 называется изолированной вершиной, вершина степени  называется висячей, или

концевой, вершиной. Граф, у которого все вершины имеют одну и ту же степень,
называется регулярным графом.

Два графа, 
 и 
, называются изоморфными, если существует взаимно однозначное

соответствие между множествами их вершин, обладающее тем свойством, что число
ребер, соединяющих любые две вершины в 
 равно числу ребер, соединяющих

соответствующие вершины в 
.

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

1. В графе 
 сумма степеней всех его вершин — число четное, равное удвоенному

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

2. Количество нечетных вершин любого графа четно.

3. Во всяком графе с  вершинами, где 
, всегда найдутся по меньшей мере две

вершины с одинаковыми степенями.

4. Если в графе с вершинами 
 в точности две вершины имеют одинаковую

степень, то в этом графе всегда найдется либо в точности одна вершина степени ,
либо в точности одна вершина степени 
.

6

Связность графа

Назовем граф связным,если его нельзя представить в виде объединения двух графов, и
несвязным — в противном случае.

Маршрутом в данном графе 
 называется конечная последовательность ребер вида

(обозначаемая также через 
 ). Очевидно следующее свойство

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

 называется начальной вершиной, а 
 конечной вершиной маршрута. Таким образом,

мы будем говорить о маршруте из 
 в 
. Заметим, что для любой вершины 

тривиальным маршрутом, вообще не содержащим ребер, является маршрут из 
 в 
.

Длиной маршрута называется число ребер в нем. Маршрут называется цепью, если все
его ребра различны, и простой цепью, если все вершины 
 различны, кроме,

может быть, 
. Замкнутая простая цепь, содержащая по крайней мере одно

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

два соседних ребра имеют общую вершину и никакое ребро не встречается более
одного раза) от вершины 
 до вершины 
 называется простым, если он не проходит

ни через одну из вершин графа более одного раза.

Граф 
 называется связным, если для любых двух его вершин  и 
 существует

простая цепь из  в 
. Любой граф можно разбить на непересекающиеся связные

графы, называемые компонентами ( связности ) графа 
. Таким образом, несвязный

граф имеет, по крайней мере, две компоненты. Две вершины эквивалентны (или
связаны ), если существует простая цепь из одной в другую.Связный граф состоит из
одной компоненты. Граф называется несвязным, если число его компонент больше
единицы.

Связный граф представляет собой простой цикл тогда и только тогда, когда каждая его
вершина имеет степень .

Если 
 — связный граф и степень каждой его вершины , тогда 
 —

простой цикл.

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

Если граф 
 — простой цикл, тогда степень каждой вершины равна двум.

Так как граф 
 — замкнутый простой путь, то из каждой его вершины можно

7

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

Покажем, что в простом цикле не может быть вершины, степень которой не равна
двум.

Если какая-то вершина в графе имеет степень меньше двух, то она не принадлежит
никакому простому циклу.

Если какая-то вершина имеет степень больше двух, то никакой простой цикл (по
определению) не может содержать все ребра, которым принадлежит эта вершина.

Задачи, приводящие к графам

Задача 1. Лист бумаги Плюшкин (Н.В.Гоголь “Мертвые души”) разрезает на три части.
Некоторые из полученных листов он также разрезает на три части. Несколько новых
листков он вновь разрезает на три более мелкие части и так далее. Сколько Плюшкин
получает листиков бумаги, если разрезает  листов?

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

Задача 2. Утверждают, что в одной компании из пяти человек каждый знаком с двумя
другими. Возможна ли такая компания?

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

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

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

Каждая вершина графа с девятью вершинами может иметь степень, равную 

. Предположим, что существует граф 
, все вершины которого

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

8

Действительно, если в графе есть вершина 
 степени , то в нем не найдется вершина 

 со степенью , так как эта вершина 
 должна быть соединена ребрами со всеми

остальными вершинами графа, в том числе с 
. Иначе говоря, в графе с девятью

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

Вывод. Во всяком графе с  вершинами, где 
, всегда найдутся по меньшей мере

две вершины с одинаковыми степенями.

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

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

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

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

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

.

Допустим, что все же найдется граф с девятью вершинами, в котором ровно две
вершины изолированные, а все остальные имеют разные степени. Тогда, если не
рассматривать эти две изолированные вершины, останется граф с семью вершинами,
степени которых не совпадут. Но такого графа не существует (см. задачу 3). Значит,
это предположение неверно.

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

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

Вернемся к задаче. Как и требовалось доказать, среди рассмотренных девяти игроков

9

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

Вывод. Если в графе с  вершинами 
 в точности две вершины имеют

одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина
степени , либо в точности одна вершина степени 
.

10