Применение теории графов для решения задач

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

Доказательство:

Покажем вначале, что любое  дерево обладает указанным свойством. Применим метод «стирания». Так как  в дереве (смотри теорему 6) всегда имеются «висячие» вершины, мы сотрем одну такую вершину вместе с выходящим из нее ребром. В результате мы вновь получим дерево, у которого на одно ребро и на одну вершину меньше. Будем продолжать эту процедуру до тех пор, пока граф не превратится в одно единственное ребро, которым соединены две вершины. Для такого графа наша формула очевидна. Заметим также, что процедура стирания на каждом шаге не изменяла разность (и p и q на каждом шаге уменьшались ровно на единицу), поэтому исходная разность также равнялась единице.

Теперь объясним идею доказательства того, что из свойства следует, что граф является деревом. Используем метод «от противного». То есть, будем считать, что в графе имеются циклы.  Рассмотрим один из них. Удалим любое ребро, принадлежащее данному циклу, при этом граф останется связным. Будем удалять ребра из графа до тех пор, пока в нем будет хотя бы один цикл. (Пусть таким образом мы удалили ребер.) Когда в графе не останется ни одного цикла, он превратится в дерево, для которого выполняется формула , из которой следует, что . Таким образом, мы доказали, что для графов, имеющих циклы, указанная в условии теоремы формула не выполняется.

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

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

Рис. 9

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

Теорема 8. Для всякого связного плоского графа верно равенство

n - m + f = 2        (*)

где n — число вершин, m — число ребер, f — число граней графа.

Доказательство. Рассмотрим остовное дерево Т графа G (подграф графа G, содержащий все вершины графа, называется остовным. Если остовный подграф является деревом, то он называется остовным деревом.). Очевидно, что граф Т имеет n вершин и одну грань (внешнюю). Поскольку Т — дерево, то число ребер Т равно (n— 1) (по теореме 7). Поэтому для графа Т доказываемая формула верна.

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

Теорема доказана. 

Формула (*) называется формулой Эйлера.

 

 

 

Применение  теории графов для решения задач.

Задача 1. Шахматный турнир проводится по круговой системе. Это означает, что каждая пара игроков встречается между собой ровно один раз. В турнире участвуют семь школьников. Известно, что Ваня сыграл шесть партий, Толя — пять, Леша и Дима — по три, Семен и Илья — по две, Женя — одну. С кем сыграл Леша?

Решение.Пусть G — граф встреч игроков, в котором вершина 1 соответствует Ване, вершина 2 — Толе, вершина 3 — Леше, вершина 4 — Диме, вершина 5 — Семену, вершина 6 — Илье и вершина 7 — Жене.

Поскольку степень вершины 1 равна  шести, то эта вершина соединена со всеми вершинами графа G, а так как вершина 7 имеет степень один, то она смежна только с вершиной 7. Рассмотрим подграф Н₁, порожденный множеством вершин {2,3,4,5,6}. Этот подграф получается из графа G удалением вершин 1 и 7 и всех ребер, выходящих из этих вершин. Поэтому в графе Н₁, который имеет 5 вершин, степени вершин будут:

d(2) = 4, d(3) = d(4) = 2, d(5) = d(6) = 1.

В графе Н₁ вершина 2 будет смежной со всеми вершинами, а вершины 5 и 6 — только с вершиной 2. Рассмотрим граф Н₂, порожденный множеством вершин {3,4}. Этот граф получается из графа Н₁ после удаления вершин 2, 5, 6 и всех ребер, выходящих из этих вершин. В графе H₂ степени вершин 3 и 4 равны единице. Это означает, что граф H₂ имеет вид как на рис. 9.

Рис. 10

Возвратив удаленные вершины 2,5,6, получим  граф Н₁ (рис.10).

Рис. 11

Возвратив теперь удаленные вершины 1 и 7, получим требуемый граф G (рис.11).

Рис. 12

Этот граф описывает встречи  школьников. Поэтому Леша, которому соответствует вершина 3, встретился с Ваней, Толей и Димой, которым соответствуют вершины 1, 2 и 4. По этому графу можно также определить, с кем встречались остальные школьники.

Задача 2. В шахматном турнире, в котором каждый участник должен был — встретиться с каждым, один шахматист заболел и не доиграл свои партии. Всего в турнире было проведено 24 встречи. Сколько шахматистов участвовало в турнире, и сколько партий сыграл выбывший участник?

Решение. Если в турнире участвовало 8 человек, то они должны были бы сыграть (8 • 7)/2 = 28 партий в случае, когда каждый участник сыграл все партии. Если в турнире участвовало 7 человек, то в этом случае они должны были бы сыграть (7 • 6)/2 = 21 партию. Поэтому в турнире участвовало 8 человек, а выбывший провел три встречи.

Задача 3. В шахматном турнире, в котором каждый участник встречался — с каждым, три шахматиста заболели и выбыли из турнира до того, как прошла его половина. Всего в турнире было проведено 130 встреч. Сколько шахматистов участвовало в турнире?

Решение. Если в турнире участвовало 16 шахматистов, то число сыгранных ими партий не должно превосходить (16-15)/2 = 120. Поэтому в турнире играло больше 16 человек. Рассмотрим следующие случаи.

а) Турнир начало 17 участников. Тогда 14 из них, закончивших турнир, провели между собой (14 • 13)/2 = 91 встречу, а выбывшие провели вместе 39 встреч, следовательно, кто-то из них провел не менее 13 встреч, т.е. выбыл во второй половине турнира.

б) Турнир начало 18 участников. Тогда 15 из них, закончивших турнир, провели между собой (15 • 14)/2 = 105 встреч, а выбывшие провели вместе 25 встреч. Поскольку половина турнира составляет 8 туров, то выбывшие участники не могли вместе провести более 24 встреч.

в) Турнир начало 19 участников. Тогда 16 из них, закончивших турнир, провели между собой (16- 15)/2 = 120 встреч, а выбывшие провели вместе 10 встреч. Каждый из них мог выбыть в первой половине турнира.

г) Турнир начало 20 участников. Тогда 17 из них, закончивших турнир, провели между собой (17- 16)/2 = 136 встреч, т.е. больше, чем все участники нашего турнира.

Следовательно, в турнире участвовало 19 человек.

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

Решение. Рассмотрим граф встреч команд G. По условию степень каждой вершины графа равна 8. Нужно доказать, что в графе существуют три вершины, порождающие пустой граф О₃.

Рассмотрим произвольную вершину v. Она несмежна с множеством вершин V, содержащим 11 вершин. Среди этих вершин обязательно найдутся две вершины и и w, несмежные между собой, так как в противном случае степень каждой вершины из V была бы не меньше 10. Вершины v, и и w определяют нужную тройку команд.

Задача 5. В компании, состоящей из пяти человек, среди любых трех человек найдутся двое знакомых и двое незнакомых друг с другом.

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

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

Покажем, что степень каждой вершины  графа равна двум. Предположим, что  существует вершина v, степень которой не меньше трех. Пусть вершина v будет смежной с вершинами v₁, v₂ и v₃. Рассмотрим подграф, порожденный этими тремя вершинами. В этом подграфе должно быть хотя бы одно ребро. Пусть это будет ребро (v₁, v₂). Но тогда граф, порожденный вершинами v₁, v₂ и v₃ будет полным, что противоречит условиям задачи.

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

Рис. 13

Легко показать, что существует ровно  один граф с пятью вершинами, степень каждой вершины которого равна двум (см. рис. 12).

Этому графу соответствует расположение людей за столом. D

Задача 6. Города страны соединены авиалиниями. Известно, что как бы

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

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

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

Вначале отнесем к множеству V вершину v, а к множеству U остальные вершины графа. Из условия вытекает, что в графе существует ребро (v, v₁).

Теперь отнесем к множеству V вершины v и v₁, а к множеству U остальные вершины. В графе существует или ребро (v, v₂), или ребро (v₁, v₂), где вершина v₂ принадлежит множеству U. Затем к множеству V отнесем вершины v , v₁, v₂.

Будем продолжать такие построения до тех пор, пока в множестве V не окажется вершина и.

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

Задача 7. Летом Иван отдыхал в молодежном лагере «Восход», где вместе   с ним находилось 53 школьника. После окончания отдыха некоторые пары обменялись адресами, причем у каждого из отдыхающих оказалось не менее 26 адресов. Через некоторое время Ивану понадобился адрес Николая, с которым он адресом не обменивался. Докажите, что Иван может узнать адрес Николая, т. е. существует цепочка из школьников, которая начинается Иваном и оканчивается Николаем и в которой каждая пара соседей обменялась адресами.

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

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

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

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

Решение. Рассмотрим граф G, состоящий из шести вершин, каждая из которых соответствует человеку. Если два человека знакомы, то соединим соответствующие им вершины красным ребром, если два человека не знакомы — синим. Мы получили полный граф К₆, ребра которого окрашены в красный или синий цвета. Нужно доказать, что в G существует треугольник, вершинами которого являются вершины графа, состоящий только из красных ребер или состоящий только из синих ребер.

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

Рис. 14

Если одна из пар вершин (2,3), (2,4), (3,4) соединена красным ребром, то в графе будет красный треугольник. В противном случае вершины 2, 3, 4 образуют синий треугольник.

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

Задача 9. В Диснейленде на озере семь островов, из каждого из них выходит один, три или пять мостов. Докажите, что хотя бы один из мостов ведет на берег.

Решение. Построим мультиграф G мостов, в котором острова будут соответствовать вершинам, а мосты между ними — ребрам.

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

Задача 10. Может ли в государстве, в котором из каждого города выходит   ровно три дороги, быть ровно 100 дорог между городами?

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

Задача 11. В парке 9 озер. Каждое озеро соединено с другими озерами   не менее чем 3 каналами. Какое наименьшее количество каналов может быть в парке?

Решение. Построим граф G, в котором озера будут соответствовать вершинам, а каналы — ребрам. По условию задачи степень каждой вершины графа G не меньше 3. По теореме 1 число ребер (каналов) равно сумме степеней вершин, деленной на 2. Минимальное число ребер получается, если степень одной вершины будет равна 4, а остальных вершин — 3. Поэтому в парке (4 • 1 + 3 • 8)/2 = 14 каналов.