V Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

ГРАФЫ И ИХ ПРИМЕНЕНИЕ ДЛЯ РЕШЕНИЯ РАЗЛИЧНЫХ ЗАДАЧ

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Мартюшева А.Р. 1

---

1МАОУ "Лицей" г.Реутов

Гришко Г.А. 1

---

1МАОУ "Лицей" г.Реутов

Работа в формате PDF

18.4 MB

Автор работы награжден дипломом победителя II степени

Диплом школьникаСвидетельство руководителя

Введение

Теория графов является одним из самых наглядных инструментов математики.

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

Для достижения поставленной цели были определены следующие задачи:

Создать математические модели, описывающие реальные жизненные ситуации с помощью математического языка;

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

Решить транспортную задачу, сравнить результаты выбора оптимального маршрута, полученные методом последовательного перебора вариантов с результатами «жадного выбора»;

Раскрасить карту Московской области «правильно»;

Провести эксперимент с раскраской карты Московской области по изменению алгоритма выбора вершин (обратное раскрашивание по возрастанию степени);

Сравнить данные, полученные в ходе эксперимента с данными при нормальной последовательности перебора вершин;

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

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

Сформулировать выводы по результатам работы.

Практическая значимость проекта.Умение применять разнообразные методы, находить общее в решении нескольких задач, понимать закономерности - все это помогает в разработке принципов решения новых задач, в создании конкретных алгоритмов.

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

Практическое применение теории графов для решения конкретных задач.

Глава 1. Транспортная задача

Решение транспортных задач позволяет определить наиболее рациональный маршрут.

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

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

Номера вариантов и названия маршрутов сведены в таблицу 1.1

Рисунок 1.1. Общая Схема всех вариантов маршрутов

Таблица 1.1. Названия и номера маршрутов

Далее «переводим» Схему маршрутов на язык теории графов. Переход от Схемы маршрутов к математической модели приведен в Приложении 1.

Для определения наилучшего пути присваиваем каждой дуге вес (рисунок 1.2).

Рисунок 1.2. Присваивание веса каждой дуге

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

Таблица 1.2. Сводная таблица результатов расчетов

по поиску оптимального маршрута

Следующий шаг – выбор наиболее оптимального маршрута.

Если выбирать оптимальный вариант по времени, то самый выгодный 1 вариант на машине через МКАД за 30 минут. Но, по стоимости проезда, он самый дорогой – 100 рублей.

При выборе варианта оптимального по стоимости проезда, выгодным является 5 вариант - финансовых затрат 0 р.! Но добираться придется 40 минут.

Существуют различные алгоритмы [1,4,6] по поиску оптимального маршрута.

Применим жадный алгоритм [4] к решению нашей задачи. Такой алгоритм делает на каждом шаге локально оптимальный выбор, допуская, что итоговое решение также окажется оптимальным.

Движение из первой вершины Д начинаем по направлению к вершине Мн: выбираем ребро, имеющее минимальный вес - 1 минута, 0 рублей. На первом шаге мы поступили рационально. Но есть существенный недостаток жадного алгоритма - он не «заглядывает» вперед даже на 1 шаг. Переместившись в вершину Мн, мы видим, что в дальнейшем выбора вариантов нет, и мы вынуждены идти по начатому пути. И уже на 2ом шаге «идем» по достаточно «тяжелым» ребрам. Как видно из Сводной таблицы результатов, этот путь далеко не оптимальный (по времени самый долгий – 50минут).

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

Глава 2. Раскраска карты Московской области

Одна из наиболее интересных задач теории графов – это задача о раскрасках вершин графа [1, 2]. Классической задачей, с помощью которой можно продемонстрировать суть проблемы, является задача о раскраске политической карты. В исследовании применен алгоритм раскраски вершин графа к карте московского региона.

Из открытых интернет-источников [3] я взяла карту Московской области, с нанесенными границами между районами. Каждый район необходимо раскрасить в определенный цвет так, чтобы граничащие с ним районы были окрашены в различные цвета, и их легко было отличить друг от друга. Районы, не граничащие между собой, могут быть окрашены в один и тот же цвет. Есть предположение, что каждая карта может быть раскрашена «правильно» при помощи четырех красок [5] . Количество используемых цветов должно быть минимальным.

2.1 Раскрашивание графа методом последовательного перебора вершин по невозрастанию степени [6]. Работа состоит из нескольких этапов.

На первом подготовительном этапе, представляем карту Московской области в виде неориентированного плоского графа: каждый район – вершина графа, граница между двумя соседними районами – это ребро между двумя соседними вершинами (рисунок 2.1).

Таблица 2.1. Таблица соответствия между административными названиями и «математическими»

Рисунок 2.1. Представление карты Московской области в виде неориентированного плоского графа

На географической карте указаны административные названия районов, на графе необходимо указать «математические» названия районов-вершин графа – числа. Номера вершинам присваиваем в произвольном порядке, начиная с самой левой верхней вершины и заканчивая правой нижней, и составляем Таблицу соответствия между административными названиями и «математическими» (таблица 2.1).

На втором этапе считаем степени всех вершин и упорядочиваем их, начиная с наибольшей – по принципу «невозрастания» степени (рисунок 2.2 и таблица 2.2).

Таблица 2.2. Упорядочивание вершин по принципу «невозрастания» степени

Рисунок 2.2. Подсчет степеней всех вершин

Далее составляем таблицу цветов (таблица 2.3), в которой будем фиксировать процесс закрашивания. Вершины упорядочены по степени от большей к меньшей. При раскрашивании, в первую очередь, будем брать вершины с максимальной степенью.

Таблица 2.3. Таблица цветов

Третий этап работы. Приступаем к раскраске графа и заполнению таблицы.

Раскрашивать граф будем последовательным методом по степеням вершин - прямым перебором возможных вариантов по следующей схеме [4,6] .

1 шаг. Берем первую вершину с максимальной степенью, закрашиваем её в цвет №1 (n1 - красный) и заносим в Таблицу цветов. Просматриваем следующую по степени вершину из Таблицы цветов. Если она несмежная с вершинами цветом №1, то окрашиваем её в цвет №1, иначе пропускаем. Таким образом, перебираем по порядку все вершины графа.

2 шаг. Берем следующий цвет (№2- желтый) и просмотр списка начинаем заново сверху вниз. Окрашиваем в цвет №2 любую неокрашенную вершину, которая не соединена ребром с другой, уже окрашенной в цвет №2.

3 шаг. По окончании очередного шага проверяем – остались ли незакрашенные вершины. Если не остались, то карта закрашена. Если есть незакрашенные вершины, то возвращаемся на 2 шаг и аналогично действуем с цветами №3, №4 и т.д., пока не будут окрашены все вершины.

Пошаговые результаты раскрашивания графа и заполнения Таблицы цветов представлены на рисунках в Приложении 3 и 4.

Мне удалось раскрасить граф при помощи 4х красок «правильно» - все соседние вершины разного цвета. Так как граф «наложен» на реальную карту Московской области, то теперь легко можно раскрасить и саму карту (рисунок 2.3).

Рисунок 2.3. Раскрашенная «правильно» карта

Московской области (по невозрастанию степени вершин)

2.2 Эксперимент по изменению алгоритма выбора вершин.

После раскрашивания графа методом последовательного перебора вершин от наибольшей степени к наименьшей, мне стало интересно: «Что получится, если поменять алгоритм выбора вершин?» Я решила проэкспериментировать - изменить последовательность выбора: вершины брать не по убыванию степени, как следует по алгоритму, а наоборот - по возрастанию степени.

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

Во-вторых, в Таблице цветов вершины теперь перечисляем в обратном порядке – по возрастанию степени.

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

В-четвертых, для сравнения данных, полученных при эксперименте (обратное раскрашивание) с данными при нормальной последовательности перебора вершин, составляем Сравнительную таблицу 2.4.

Таблица 2.4. Сопоставление данных, полученных в ходе

эксперимента (обратное раскрашивание) с данными при

переборе вершин по невозрастанию степени

Как проходил эксперимент, можно увидеть пошагово на рисунках, в Таблице цветов и Сравнительной таблице в Приложении 5.

Как видно из таблиц и рисунков, после использования всех четырех цветов, у нас остались нераскрашенные вершины –7,25 и 26 (рисунок 2.4)! Для их раскраски требуется дополнительно пятый цвет! Продолжив раскрашивать пятым по счету цветом по заданному алгоритму, мы сталкиваемся еще с одной проблемой: 26 и 25 вершины являются смежными и последнюю вершину (25) закрасить пятым цветом невозможно! Для её раскраски требуется дополнительно шестой цвет!!!

Из Сравнительной таблицы видно, что после использования первых трех цветов, количество незакрашенных вершин осталось примерно одинаковым при обоих способах раскраски – 6 и 7. Только при алгоритме невозрастания степени нам хватило одного цвета, чтобы закончить раскраску. А при «обратном» способе невозможно закончить раскраску одним синим цветом.

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

На практике к задачам раскрашивания сводятся такие проблемы как составление расписания занятий в учебном заведении.

Рисунок 2.4. Карта, раскрашенная

по возрастанию степени вершин

Глава 3. Составление фрагмента школьного расписания

3.1 Составление учебного расписания, используя теорию графов.

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

Для целей исследования был выбран 2 «Г» класс нашего Лицея, учтены возможности учителей и ограничения по количеству уроков в день.

Фрагмент расписания необходимо составить с учетом следующих условий и ограничений:

1) учитель ИЗО Тллв*** может дать только первый урок в понедельник;

2) учителя Английского имеют следующие возможности: Кптв***(А-1) может дать и первый урок во вторник, и четвертый в четверг; Кгрмн***(А-2) свободна – и первый урок во вторник, и четвертый в четверг, и пятый в среду. Но если учесть, что А1 не может дать пятый урок в среду, то общая возможность для двух учителей ОДНОВРЕМЕННО – это первый урок во вторник и четвертый в четверг;

3) учитель физкультуры Лптв*** готов в понедельник – первый, во вторник - третий, четверг - пятый и седьмой уроки. Учитывая, что во втором классе не бывает седьмых уроков, то остается только: понедельник – первый, вторник - третий, четверг - пятый;

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

Изобразим данную ситуацию в виде рисунков (Приложение 6). У нас будет 2 множества:

1 множество - «Учителя». Элементами множества являются учителя (ИЗО,А-1,А-2,ФИЗ);

2 множество - «Дни недели». Подмножества – дни недели по порядку (понедельник, вторник, среда, четверг, пятница):

подмножество 2.1 - «Понедельник». Элементы множества – уроки по порядку (1,2,3,4,5);

подмножество 2.2 - «Вторник». Элементы множества – уроки по порядку (1,2,3,4,5);

подмножество 2.3 - «Среда». Элементы множества – уроки по порядку (1,2,3,4,5);

подмножество 2.4 - «Четверг». Элементы множества – уроки по порядку (1,2,3,4,5);

подмножество 2.5 - «Пятница». Элементы множества – уроки по порядку (1,2,3,4,5).

Соответствие элементов из множества «Учителя» элементам множества «Дни недели» представлено на рисунке 3.1. Элементы множеств будут являться вершинами, связи между элементами – ребрами (дугами). Таким образом, наглядный рисунок стал графом – с вершинами и ребрами, соединяющими эти вершины.

Далее считаем степени вершин из множества «Учителя» и упорядочиваем их, степени проставляем рядом с вершинами (рисунок 3.2).

При раскрашивании карты вершины упорядочивали от большей степени к меньшей, и раскрашивали, в первую очередь, вершины с максимальной степенью. При составлении расписания действуем с точностью наоборот - в первую очередь берем вершины с минимальной степенью и именно с них начинаем составлять соответствие, потому что вершины с минимальной степенью являются самыми «узкими» местами в расписании.

Вершина ИЗО допускает всего один вариант соответствия – Понедельник1. Связываем эти две вершины: «ИЗО-Понедельник1». Следовательно связь вершины ФИЗ с Понедельник1 отпадает.

Следующее узкое место – вершины А-1 и А-2. По степеням они идут по возрастающей за ИЗО. Проблема состоит в том, что обе эти вершины должны быть одновременно и одинаково связаны с вершинами из множества «Дни недели». Поэтому связь «А-2 – Среда5» не интересует и пропадает. После чего степени вершин А-1 иА-2 становятся одинаковыми, связи с элементами множества «Дни недели» тоже становятся одинаковыми и обе эти вершины условно можно считать как единое целое (А). Устанавливаем соответствие «А-Вторник1», «А–Четверг4».

И остается последняя вершина ФИЗ. Для нее связи очевидны, т.к. вариантов выбора больше не осталось. Устанавливаем соответствие «ФИЗ-Вторник3», «ФИЗ–Четверг5».

Остальные уроки по всем дням недели ведет Классный руководитель – Мх***.

П окажем наглядно и поэтапно, что общего между составлением фрагмента учебного расписания с помощью графов и раскрашиванием карты (рисунки 3.3 – 3.7). Как только возникает связь между конкретным учителем и номером урока в расписании – эта связь и есть «территория».

Рисунок 3.5. Связь между конкретным учителем и номером урока в расписании – «территория»

Переводя с математического языка названия вершин на названия предметов и Фамилии Имена Отчества учителей, получаем фрагмент расписания (рисунок 3.7), по виду сравнимый с картой.

Рисунок 3.7. Готовый фрагмент общешкольного расписания

3.2 Сходства и различия задач составления расписания и раскрашивания карт.

Сравнивая между собой задачи составления расписания и раскрашивания карт, можно сделать выводы:

Общее между задачами:

- обе задачи должны быть представлены в виде математической модели - графа;

- необходимо подсчитать степени вершин;

- понять аналогию: на карте каждая территория красится в свой цвет, и при составлении расписания тоже существуют свои «территории» - это связь между конкретным учителем и номером урока в расписании.

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

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

Список использованных источников и литературы:

Статьи в журнале, сборнике трудов конференции:

Моторина Е. А. Занятие «Раскраски графов» факультативного курса «Элементы теории графов и ее приложения», Молодой ученый, 2015г. №23.

Юдина Н. А. Метод проектов в обучении элементам теории графов // Молодой ученый. — 2015. — №14. — С. 547-551.

Электронные ресурсы:

Яндекс.Карты (Россия, Московская область, yandex.ru/maps)

http://rain.ifmo.ru/cat/view.php/theory/algorithm-analysis/greedy-2004 – Дискретная математика: алгоритмы.

http://www.razlib.ru/matematika/ - Проблема четырех красок.

https://intellect.ml/raskraska-grafov-algoritm-raskraski-grafa-prakticheskoe-primenenie-raskraski-grafov-4145

ПРИЛОЖЕНИЕ 1

Переход от Схемы маршрутов к математической модели

ПРИЛОЖЕНИЕ 2

Раскраска карты Московской области. Пошаговые результаты раскрашивания последовательным методом по невозрастанию степеней вершин.

1ый шаг - 1ый цвет 2ой шаг - 2ой цвет

3ий шаг - 3ий цвет 4ый шаг - 4ый цвет

«Правильно» раскрашенная карта Московской области при помощи 4х красок.

ПРИЛОЖЕНИЕ 3

Раскраска карты Московской области. Пошаговые результаты раскрашивания при эксперименте по изменению алгоритма выбора вершин (по возрастанию степени).

1ый шаг - 1ый цвет 2ой шаг - 2ой цвет

3ий и 4ый шаги - 3ий и 4ый цвета. Нераскрашенные вершины – 7,25 и 26.

Карта Московской области, раскрашенная по возрастанию степени вершин