|
В этой главе речь пойдет о замечательных математических объектах. Эти объекты (как правило, различные картинки) очень часто возникают в математических задачах и оказываются чрезвычайно полезными при решении многих, внешне не похожих друг на друга задач. В математике даже есть специальный раздел, который так и называется «Теория графов». Мы не будем давать строгого определения графа как математического объекта. Для нас вполне достаточно ограничиться несколькими определениями и теоремами и показать, как эти определения и теоремы работают при решении конкретных задач.
Определение. Под графом мы будем понимать картинку, адекватно описывающую задачу. При этом элементы множеств, как правило, показываются точками. Желательно, чтобы при решении точки не лежали на одной или паре прямых. Точки при этом называются вершинами графа, а линии, соединяющие эти точки, — ребрами.
Отметим, что точки могут соединяться произвольными (не обязательно прямыми) линиями. Поясним понятие графа на примере нескольких задач.  Пример 1. Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля — Меркурий, Плутон — Венера, Земля — Плутон, Плутон - Меркурий, Меркурий - Венера, Уран - Нептун, Нептун - Сатурн, Сатурн — Юпитер, Юпитер — Марс и Марс — Уран. Можно ли добраться (возможны пересадки) с Земли до Марса?
Решение.
Нарисуем схему: планетам будут соответствовать точки, а соединяющим их маршрутам - непересекающиеся между собой линии. 
Сделав набросок рисунка маршрутов, мы нарисовали граф, соответствующий условию задачи. Видно, что все планеты Солнечной системы разделились на две не связанных между собой группы. Земля принадлежит одной группе, а Марс - второй. Долететь с Земли до Марса нельзя. Пример 2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией тогда и только тогда, когда двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли из города 1 добраться в город 9? Решение.
Покажем возможные маршруты, нарисовав граф  И в этой задаче 1 и 9 попали в две разных части графа. Ясно, что в правой части графа сгруппировались города-цифры нацело делящиеся на 3, а в левой части графа ребра соединяют две цифры: одну — делящуюся на 3 с остатком 1, а другую — делящуюся на 3 с остатком 2. Примечание. Отметим, что один и тот же граф можно нарисовать по-разному. Если учащиеся одного класса нарисуют графы к одной задаче, то мы можем получить столько графов, сколько учащихся их рисовали. Нарисованные по-разному графы (если они нарисованы без ошибок) принято называть изоморфными. Любой читатель может нарисовать бесконечное множество изоморфных графов. Пример 3. Сколькими способами, двигаясь по указанным отрезкам, можно кратчайшим путем переместиться из точки А в точку В?
 Решение.
Это классическая задача на минимальный путь и возможное количество путей. Начнем с того, что вычеркнем все отрезки, лежащие вне прямоугольника с вершинами А и В. Ясно, что они не могут давать минимальный путь: 
Теперь последовательно будем убирать симметричные пути: 
Пройдем из точки А по периметру через верхний правый угол (рис. 1), потом пройдем через левый нижний угол (рис. 2) — два пути уже получены. Обратимся к рисунку 2: пройдя через точки А и С, далее мы можем попасть в точку В двумя способами (см. рис. 3). Задача имеет симметрию. Теперь из точки В пройдем через точку D (см. рис. 3) в точку А. Ясно, что это можно сделать еще двумя способами. Пройдя из А через G и Е, мы получим еще два варианта пути. И оставшиеся два варианта представлены на рисунке 5.
Ответ: десятью способами. Примечание. Это задача на отыскание оптимального (симметричного) решения задачи. Рассмотрим еще одну задачу, которая хорошо решается при оптимально выполненном чертеже. Искусство выполнения чертежей в задачах с графами требует отдельного разговора. Пример 4. Доска имеет форму креста, который получается, если из квадратной доски 4x4 выкинуть угловые клетки. Можно ли ходом шахматного коня обойти эту доску и вернуться на исходное поле, побывав на всех полях ровно по одному разу? 
Решение.
Для простоты решения пронумеруем все клетки креста:  Далее для решения задачи построим граф, вершинами которого будут точки с номерами клеток, а ребрами — возможные ходы шахматного коня с клетки на клетку.
 Для построения графа обратим внимание на то, что из клеток 4, 5, 8 и 9 шахматный конь может сделать по два хода (эти точки-клетки мы поместим в центральной части графа), а из всех остальных - по три хода (эти точки-клетки мы расположим на периметре).
Наша задача состоит в том, чтобы показать все возможные ходы шахматного коня, а потом на полученном графе убрать лишние ребра, мешающие выполнению условий задачи (например, конь должен в каждой точке креста побывать только один раз, путь должен начинаться и оканчиваться в одной и той же клетке креста.
Получен полный граф всех возможных ходов шахматного коня.
Давайте проанализируем полученный результат:
1) На рисунке обязательно должны остаться ребра 1-9, 9—3, 5—И, 5—7, 4—12, 4-10, 8—2, 8-6 (конь приходит в клетку и уходит из нее).
2) Убрав ребра 10—11, 2-3, 6—12, 1-7, мы получим решение задачи.
 Определение. Количество ребер, выходящих из данной вершины, называется степенью вершины.
На приведенном в качестве примера графе вершина А имеет первую степень, вершина Б — третью, а остальные вершины имеют вторую степень. Вершина изолированная (из которой не выходит ни одно ребро) имеет нулевую степень.
Пример 5. В деревне есть 15 телефонов, а АТС отсутствует. Можно ли телефоны соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?  Решение.
Предположим, что это возможно. Рассмотрим граф, вершины которого соответствуют телефонам, а ребра — соединяющим их проводам. В этом графе 15 вершин, степень каждой из которой равна пяти. Подсчитаем количество ребер в этом графе. Для этого сначала просуммируем степени всех его вершин. Ясно, что при таком подсчете каждое ребро учтено дважды (оно ведь соединяет две вершины!). Поэтому число ребер графа должно быть равно 15*5/2
Но это число нецелое! Следовательно такого графа не существует, а значит, и соединить телефоны требуемым образом невозможно. Правило. Для подсчета числа ребер графа необходимо просуммировать степени вершин и полученный результат разделить на два. Следствие. Сумма степеней всех вершин графа должна быть четной (иначе ее нельзя было бы разделить на 2 нацело). Определение. Вершина графа, имеющая нечетную степень называется нечетной, а имеющая четную степень — четной. Теорема. Число нечетных вершин любого графа — четно.
Для доказательства этой теоремы остается заметить, что сумма нескольких целых чисел четна тогда и только тогда, когда количество нечетных слагаемых четно. Примечание. Теорема о четности числа нечетных вершин - одно из центральных мест теории графов. Очень важно до конца разобраться в ее доказательстве (см. раздел «Четность») и научиться применять при решении задач. Пример 6. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 - по 4 друга, а 10 - по 5 друзей. Примечание. Если Петя друг Васи, то Вася - друг Пети. Решение.
Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3; 11 — степень 4; 10 - степень 5. Однако у такого графа 19 нечетных вершин, что противоречит теореме. Пример 7. В стране Семерка 15 городов, каждый из которых соединен дорогами не менее, чем с 7 другими. Докажите, что из любого города можно добраться до любого другого (возможно, проезжая через другие города). Решение.
Рассмотрим два произвольных города и предположим, что они не соединены путем, то есть такой последовательностью дорог (с этим мы уже сталкивались в примере 3), в которой начало очередной дороги совпадает с концом предыдущей. Каждый из двух городов по условию задачи соединен не менее, чем с 7 другими; при этом все упомянутые города различны - ведь если какие-то два из них совпадают, то есть путь, соединяющий исходные города.  Таким образом, мы указали 16 городов. Противоречие с условием задачи.
Определение. Граф называется связным, если две его вершины могут быть соединены путем, т. е. последовательностью ребер, каждое следующее из которых начинается в конце предыдущего. Определение. Несвязный граф состоит из нескольких «кусков». Эти «куски» называются компонентами связности графа. Каждая компонента несвязного графа является, конечно, связным графом. Примечание. В примерах 1 и 2 мы имели дело с графами несвязными; во всех остальных примерах рассматривались графы связные. Определение. Замкнутый путь, то есть такой, начало и конец которого совпадают, называется циклом.
Примечание. В примере 4 мы уже с циклом сталкивались. Более того, мы можем утверждать, что и граф примера 7, в котором рассматриваются дороги страны Семерка, связен.
Теорема. Граф с n вершинами, степень каждой из которых не менее (n-1)/2 — связен. Примечание. Понятие связности чрезвычайно важно и постоянно будет использоваться в процессе дальнейшего изучения теории графов. В следующем примере основным моментом в решении задачи является содержательным соображением и часто оказывается полезным при решении задач. Пример 8. В Тридевятом царстве лишь один вид транспорта — ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний — одна, а из всех остальных городов по 20. Докажите, что из столицы можно долететь в Дальний (возможно с пересадками). Доказательство.
Рассмотрим компоненту связности графа ковро- линий, содержащую столицу. Нам нужно доказать, что она содержит также и город Дальний. Предположим противное. Тогда в этой компоненте связности из одной вершины (столицы) выходит 21 ребро, а из всех остальных вершин — 20 ребер. Таким образом в этом графе (компоненте связности) ровно одна нечетная вершина. Мы пришли к противоречию!
|
