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

Титульник 

Оглавление

 

Введение 3

Элементы  теории графов. 5

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

Заключение 29

Литература 30

 

 

Введение

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

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

Первая работа по теории графов, принадлежащая  известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Эйлер решал очень известную головоломку о мостах Кёнигсберга. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем.

Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.

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

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

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

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

 

 

 

 

Элементы теории графов.

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

Вершины графа изображаются в виде точек на плоскости. Если две вершины образуют ребро, то соответствующую пару точек соединяют линией. Вершины графа обозначают латинскими буквами A, B, C, D или цифрами. Иногда граф в целом можно обозначать одной заглавной буквой.

Рис. 1

Например, на рис. 1 изображен граф G, заданный множеством вершин

F = {1,2,3,4,5} и множеством ребер Е = {(1,2), (2,3), (4, 2), (4,3)}.

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

Вершины, которые соединены ребром, называются его концами. Если вершина является концом ребра, то будем говорить, что ребро выходит из вершины. Число ребер, выходящих из вершины v, называется степенью вершины v и обозначается d(v). Для графа, изображенного на рис. 1, d(1) = 1, d(2) = 3, d(3) = 2, d(4) = 2, d(5) = 0. Вершина степени 0 называется изолированной, вершина степени 1 — висячей.

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

Рис. 2

Сформулируем в виде теорем простейшие свойства степени.

Теорема 1. Сумма степеней всех вершин графа G равна удвоенному количеству его ребер (это утверждение верно и для простых графов, и для мультиграфов).

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

Пусть граф G имеет п вершин и т ребер. Сложив степени вершин графа G d(1), d(2),..., d(n), мы получим сумму, в которую каждое ребро входит дважды, поскольку каждое ребро вносит по единице в степень ровно двух вершин. Поэтому d(l) + d(2) + ... + d(n) = 2m.

Следствие. Число вершин нечетной степени в графе четное.

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

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

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

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

Докажем это утверждение от противного. Допустим, что существует граф Н, степени  всех n вершин которого различны.

В промежутке от 0 до n - 1 существует ровно n целых чисел: 0,1,2,..., n - 2, n - 1. С другой стороны, степени n вершин графа тоже расположены в этом промежутке. Поэтому должны существовать такие вершины v₁, v₂,..., v_n, что d(v₁) = 0, d(v₂) = 1, ..., d(v_n) = n - 1.

Рассмотрим вершины v₁ и v_n. Степень вершины v₁ равна нулю, это значит, что вершина v₁ не соединена ребром ни с одной другой вершиной. Степень вершины v_n равна п - 1, это значит, что эта вершина соединена ребрами со всеми остальными вершинами, в том числе и с вершиной v₁, что противоречит предыдущему. Следовательно, существование графа Н, у которого все вершины имеют различную степень, невозможно. Это означает, что простом графе найдется не менее двух вершин с одинаковыми степенями.

Теорема 3. В простом графе с n вершинами число ребер не больше .

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

Всего n вершин, каждая из них может быть соединена не более чем с (n-1) остальными вершинами. Таким образом, получаем (n-1)n ребер, но каждое из них посчитано ровно два раза, так как соединяет две вершины. Поэтому делим полученное выражение пополам. Теорема доказана.

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

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

Граф Н называется подграфом графа G, если вершины и ребра Н принадлежат G. Подграф Н графа G называется подграфом, порожденным множеством вершин {v₁, v₂,..., v_p}, если он содержит вершины v₁, v₂,..., v_p и все ребра графа G, соединяющие эти вершины.

Рис. 3

Подграф Н графа G называется подграфом, порожденным множеством ребер {e₁, e₂,..., е_s}, если он содержит ребра e₁, e₂,..., е_s и все вершины графа G, являющиеся концами этих ребер.

На рис.3 изображен граф G и два его подграфа Н₁ и Н₂, причем подграф Н₂ порожден множеством вершин {1, 2, 4, 5} или множеством ребер {(1, 2), (1, 4), (2,4), (2, 5), (4, 5)}.

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

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

Рис. 4

Маршрутом в графе называется такая последовательность чередующихся вершин v_i и ребер e_j графа (v₀, e₀, v_l, e_1, v₂,... ,e_k-1, v_k), что каждое ребро соединяет вершины последовательности, между которыми оно находится, т.е. ребро e_i соединяет вершины v_i и v_i+1.

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

Цепь в графе можно  задавать перечислением только вершин или только ребер.

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

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

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

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

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

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

Рис. 5

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

Полный двудольный граф K_p,q имеет ребер.

Теорема о сумме  степеней вершин двудольного графа. Суммы степеней вершин долей двудольного графа равны.

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

 Пусть v₁,v₂, …v_k — вершины одной доли, а u₁, u₂,...,u_p — вершины другой доли. Тогда из одной доли выходит d(v₁) + d(v₂) + …+d(v_k) ребер,а из другой — d(u₁) + d(u₂) + ... + d(u_p) ребер. Равенство сумм следует из того, что это одни и те же ребра. Теорема доказана. 

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

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

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

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

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

Объединим циклы Р₁ и Р₂ следующим образом: пройдем часть Р₁ от вершины v₁ до вершины v₂, затем пройдем цикл Р₂, затем — оставшуюся часть Р₁ от v₂ до v₁ (см. рис. 6).

Рис. 6

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

Цепь в графе, содержащая каждое его ребро, называется эйлеровой цепью.

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

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

 Очевидно, что никакая вершина нечетной степени не может принадлежать эйлеровой цепи, если только она не является его концом.

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

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

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

Деревом называется связный граф, не содержащий  циклов. Несвязный граф, не имеющий циклов, называют лесом. Пример дерева приведен на рис. 7.

Рис. 7

Теорема 6. В любом дереве есть хотя бы одна висячая вершина.

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

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

Рис. 8

Это означает существование  цикла в дереве G, что противоречит определению дерева. Следовательно, в любом дереве есть висячая вершина.

Теорема 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 каналов.