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

Министерство образования Республики Башкортостан

Отдел образования Администрации

муниципального района Зилаирский район

Муниципальное общеобразовательное бюджетное учреждение

«Средняя общеобразовательная школа с.Ивано-Кувалат»

Конкурс исследовательских работ

в рамках Малой академии наук школьников

Республики Башкортостан по номинации «Математика»

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

Выполнил:

Ученик 7 класса

Усманов Максим

Руководитель:

Овчинникова Ольга Николаевна

с. Ивано-Кувалат

2014г

План

Введение         3

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

2. Решение задач с помощью графов          4

3. Применение графов          7

Заключение         7

Список литературы         8

Введение

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

       Граф – это не только дворянский титул.

       Слово «граф» древнего происхождения и является составной частью многих слов: биография – жизнеописание, география – землеописание, графит – стержень для письма и так далее. Все эти слова имеют один корень: «граф», который происходит от греческого слова grapho – писать.

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

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

       Число ребер, выходящих из вершины, называется степенью вершины, и обозначается d(u). Вершина называется нечетной, если ее степень – число нечетное. Вершина называется четной, если ее степень – число четное.

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

       Ребро может начинаться и заканчиваться в одной вершине. Это ребро называется петлей.

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

Рис. 1. Полный граф.

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

Рис. 2. Граф с одной изолированной вершиной.

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

       Следствие. В любом графе число вершин нечетной степени четное.

2. Решение задач с помощью графов

       Графы широко применяются при решении задач. Рассмотрим некоторые из них.

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

       Решение. Поставим в соответствие каждому игроку точку плоскости – вершину графа. Если два игрока встретились между собой, то соединим соответствующие вершины линией – ребром графа. Таким образом, мы построили граф встреч игроков. Пусть в этом графе вершина 1 соответствует Ване, вершина 2 – Толе, вершина 3 – Леше, вершина 4 – Диме, вершина 5 – Семену, вершина 6 – Илье и вершина 7 – Жене.

       Поскольку Ваня провел 6 встреч, то степень вершины 1 равна 6, и эта вершина соединена со всеми вершинами графа. Степень вершины 2 должна быть равна 5, так как Толя провел 5 встреч. Из вершины 2 уже выходит одно ребро. Оставшиеся 4 ребра проведем из 2 в вершины 3, 4, 5 и 6, поскольку вершина 7, степень которой равна 1 (Женя провел одну встречу), соединена уже ребром с вершиной 1.

       Теперь вершины 3, 4, 5 и 6 имеют степени 2. Вершины 5 и 6, соответствующие Семену и Илье, должны иметь такие степени, так как эти участники провели по две встречи. Вершины 3 и 4 соединим ребром, поскольку они должны иметь степени 3, так как Леша и Дима провели по 3 встречи.

       Таким образом, на рисунке 3 мы изобразим граф, описывающий встречи участников.

Рис. 3. Граф, описывающий встречи участников.

       Поэтому Леша, которому соответствует вершина 3, встретился с Ваней, Толей и Димой, которым соответствуют вершины 1, 2 и 4.

       Ответ: Леша сыграл с Ваней, Толей и Димой.

       Задача 2. Для отправки поздравления есть конверты трех видов, на которые клеится одна из двух марок и в которые вкладывается одна из четырех открыток. Сколько существует способов сделать поздравление по почте?

       Решение. Занумеруем конверты, марки и открытки. Выбор одного конверта из трех возможных можно изобразить следующим графом (рис. 4).

Рис. 4. Выбор одного конверта из трех возможных.

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

Рис. 5. Граф выбора конверта с маркой.

       Получилось 6 вариантов выбора конверта с маркой. В каждый из таких конвертов с маркой можно вложить одну из 4 открыток (рис. 6).

Рис. 6. Граф почтового поздравления.

       Нижние вершины графа задают варианты рассылки поздравлений.

       Ответ: 24.

       Задача 3. В деревне 10 домов, и из каждого выходит по 7 тропинок, идущих к другим домам. Сколько всего тропинок приходит между домами?

       Решение. Пусть дома - вершины графа, тропинки - рёбра. По условию из каждого дома (вершины) выходит 7 тропинок (рёбер), тогда степень каждой вершины 7, сумма степеней вершин 7·10=70, а число рёбер 70 : 2= 35. Таким образом между домами проходит 35 тропинок.

       Ответ: 35 тропинок.

3. Применение графов

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

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

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

       Историк прослеживает родословные связи по генеалогическому дереву.

       Военачальник наносит на карту сеть коммуникаций, по которым из тыла к передовым частям доставляется подкрепление.

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

Заключение

       В своей работе я изучил основные понятия теории графов, рассмотрел применение графов при решении задач и в жизни. Мы часто используем понятие  графа, порой не замечая этого. Карты метрополитена, дорог, железнодорожных путей, маршрутов самолетов и даже схема интернета – все это примеры использования графов.

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

Список литературы

1. Мельников О.И.  Незнайка в стране графов. – М.: КомКнига, 2007.
2. Шарыгин И.Ф., Шевкин А.В.  Математика: задачи на смекалку. – М.: Просвещение, 2001.
3. Березина Л.Ю. Графы и их применение. – М.: Просвещение, 1979.