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

Задача 12. Марсиане очень любят танцевать танцы, в которых нужно браться

за руки. В танце «Дружба» может  участвовать не более 7 марсиан, у каждого из которых не более трех рук. Какое наибольшее число рук может быть у танцующих, если любая рука одного марсианина держит ровно одну руку другого марсианина?

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

Задача 13. Города страны соединены авиалиниями. Из столицы выходит 21  линия, из города Дальний — одна, а из каждого из остальных городов — по двенадцать линий. Докажите, что из столицы можно долететь до города Дальний (возможно, с пересадками).

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

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

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

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

Задача 15. В море живут осьминожки. У каждого из них или один, или два друга. Когда взошло солнце, те, у кого было двое друзей, посинели, а те, у кого один друг, — покраснели, и оказалось, что любые два друга — разноцветные. Однако друзья должны иметь одинаковый цвет, и поэтому 10 синих осьминожек перекрасились в красный цвет, а 12 красных — в синий. Сколько осьминожек живет в море?

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

Исследуем строение графа G.

Из условия вытекает, что степень  каждой вершины графа равна или 1, или 2. Значит, компонентами графа  могут быть только цепи или циклы. Однако после перекраски все вершины  каждого цикла станут синими, что  запрещено условиями задачи. Поэтому  циклы в графе G отсутствуют. Так как после перекраски все вершины цепей, кроме концевых, станут синими, то в G отсутствуют цепи, состоящие более, чем из двух ребер. Итак, компонентами графа G являются цепи, состоящие из двух ребер. Концевые вершины цепей красные, а центральные — синие. В каждой цепи две вершины красные, а одна синяя. Поэтому в графе есть 6 цепей, в которых вершины перекрасятся в синий цвет, и 10 цепей, в которых вершины перекрасятся в красный цвет, всего 16 цепей. Поэтому в графе G будет 48 вершин, а в море 48 осьминожек.

Задача 16. За столом сидит 5 мальчиков и 7 девочек, а на столе в вазе лежат   конфеты. Некоторые из детей знакомы. Каждая девочка дала по конфете из вазы знакомому мальчику, а затем каждый мальчик дал по конфете из вазы незнакомой девочке. После этого в вазе не осталось конфет. Сколько конфет было в вазе?

Решение. Поставим в соответствие детям вершины графа. Соединим две вершины зеленым ребром, если соответствующие мальчик и девочка знакомы, и красным, если незнакомы. Получим полный двудольный граф K_5,7, ребра которого раскрашены в два цвета. В графе 5 • 7 = 35 ребер. Каждому ребру графа соответствует ровно одна конфета, так как если ребро зеленое, то конфету получает мальчик, если красное — девочка. Следовательно, в вазе было 35 конфет.

Задача 17. В классе 12 мальчиков и 16 девочек. Каждая девочка дружит   ровно с 3 мальчиками. Количество девочек, с которыми дружат мальчики, одинаково. Со сколькими девочками дружит каждый мальчик?

Решение. Пусть каждый мальчик дружит ровно с к девочками. Рассмотрим двудольный граф, описывающий дружбу мальчиков и девочек. Сумма степеней вершин доли, соответствующей девочкам, равна 16 • 3 = 48, а сумма степеней вершин доли, соответствующих мальчикам, равна 12к. Из теоремы о сумме степеней вершин долей двудольного графа следует, что 16 • 3 = 12k. Отсюда k=4 , и каждый мальчик дружит с четырьмя девочками.

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

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

Задача 19. Андрей пошел с отцом в тир. Уговор был такой: Андрей делает пять выстрелов и за каждое попадание получает право еще на два выстрела. Андрей выстрелил 25 раз. Сколько раз он попал?

Решение. Стрельбу Андрея можно описать деревом, которое называется корневым деревом (см. рис.14). В этом дереве все вершины, кроме верхней, соответствуют выстрелам. Если Андрей попал, то степень соответствующей вершины равна трем, если промазал — единице.

Рис. 15

Степень верхней вершины равна пяти. Дерево имеет 26 вершин и 25 ребер (по теореме 7). Пусть n — число попаданий Андрея. Тогда граф содержит n вершин степени 3, (25 - n) вершин степени 1 и одну вершину степени 5. Воспользуемся теоремой 1:

Решив это уравнение, получим n. Андрей попал 10 раз.

Задача 20. Шесть островов на реке в парке соединены мостами (рис.15). Можно ли, начав прогулку на одном из островов, пройти по каждому из мостиков ровно один раз и вернуться на тот же остров? В случае отрицательного ответа определите, сколько мостиков и между какими островами нужно построить, чтобы такая прогулка стала возможной.

Рис. 16

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

Рис. 17

Рассмотрим построенный граф G. В этом графе вершины 2 и 4 имеют нечетную степень, следовательно, граф G не является эйлеровым. Это означает, что желаемую прогулку по мостикам совершить нельзя.

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

Задача 21. В парке (см. задачу 20) построили мостик, соединяющий острова 2 и 4. Найдите маршрут прогулки, который начинается и оканчивается в одном и том же месте и проходит каждый мостик ровно один раз.

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

Для поиска цикла воспользуемся  способом доказательства теоремы Эйлера. Поиск эйлерова цикла начнем в вершине ПБ. Выйдя из этой вершины, для продолжения цепи будем каждый раз выбирать еще не использованное ребро. Предположим, что мы получили цикл С₁ = (ПБ, 1, 4, ЛБ, 5, 2, ПБ) (см рис.17).

Рис. 18

Удалим ребра цикла С₁ из графа. В оставшемся графе построим цикл С₂ — (1, 3, ЛБ, 6, 5,4, 1). Объединим циклы С₁ и С₂ в цикл С = (ПБ, 1, 3, ЛБ, 6, 5, 4, 2, 1, 4, ЛБ, 5, 2, ПБ) по правилу, предложенному в теореме Эйлера (в качестве вершины v₂ используется вершина 1).

Задача 22. Имеются три дома и три колодца. Каждый хозяин пользуется любым из трех колодцев. В некоторый момент обитатели домов поссорились и решили проложить свои дорожки до колодцев так, чтобы дорожки не пересекались. Возможно ли это?

Решение. Решение задачи о трех домах и трех колодцах сводится к ответу на вопрос: является ли планарным граф К_3,3 (рис. 18)?

Рис. 19

Попробуем нарисовать граф К_3,3 на плоскости так, как этого требует определение планарности. На любом рисунке графа должен обязательно присутствовать цикл С = (1,4,2,5,3,6, 1), который делит плоскость на две части: внутри и вне цикла (рис. 19).

Рис. 20

Нам осталось еще нарисовать ребра (3,4), (1, 5), (6, 2). Для изображения ребра (3,4) есть две возможности: внутри цикла и вне цикла (рис.20).

Рис. 21

Тогда ребро (1,5) в первом случае можно нарисовать только вне  цикла, а во втором — только внутри (рис. 21).

Рис. 22

Последнее ребро (6,2) невозможно нарисовать так, чтобы оно не имело  общих точек с ранее нарисованными  ребрами ни в одном из этих случаев.

Мы доказали, что граф К_3,3 не является планарным. Это означает, что невозможно провести дорожки от домов до колодцев нужным образом.

Задача 23. Мэрия решила построить в каждом квартале города, имеющего 155 перекрестков и 260 отрезков улиц между перекрестками, универсам. Сколько будет построено универсамов?

Решение. Карту города можно считать плоским графом G, в котором перекрестки будут вершинами, а отрезки улиц — ребрами.

Поскольку кварталы города соответствуют внутренним граням плоского графа G, то найдем число граней по формуле Эйлера. Граф G имеет 155 вершин и 260 ребер. Число граней в нем:

f = m - n + 2 = 260 - 155 + 2 = 107.

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

Заключение

Данная работа не претендует на полноту исследования темы «Основы теории графов». Не смотря на это, работа будет интересна не только школьникам и студентам педагогических вузов в качестве отправной точки при изучении элементов теории графов, но и учителям математики.

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

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

Применение графов помогает думать, объяснять, наглядно представлять, поэтому их использование имеет естественную тенденцию к развитию.

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

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

 

 

 

Литература

 

1. Березина Л. Ю. Графы и их применение: Пособие для учителей. - М.:Просвещение, 1979. – 143 с.
2. Мельников О. И. Теория графов в занимательных задачах. Изд. 3-е, испр. и доп. — М.: Книжный дом «ЛИБРОКОМ», 2009. — 232 с.
3. Мендель В. В. Графы и их применение. - журнал "МИФ-2", №1, 2003 г.