Графы? Это серьёзно!

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

Графы? Это серьёзно!

Мешкова В.А. 1Копытько К.Ю. 1
1МОАУ "Лицей №6"
Мосина И.Г. 1Сулеева И.В. 1
1МОАУ "Лицей №6"
Автор работы награжден дипломом победителя II степени
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

Введение

Ежедневно люди сталкиваются с множеством задач, которые требуют незамедлительного решения. Эти задачи встречаются не только на уроках в школе, но и в реальной жизни. С первыми всё ясно, не знаешь, как решить - открыл учебник, прочитал параграф и вопросов по поводу решения не осталось. А как быть с задачами, которые ставит перед нами жизнь? Согласитесь, здесь не всё так просто. Зачастую приходится применять не только бытовые навыки, но и логическое мышление. Одним из самых актуальных методов решения логических головоломок в настоящее время является теория графов и круги Эйлера. Широкая область применения теории графов и кругов Эйлера определяет актуальность выбранной темы исследования.

Объектом нашего исследования является процесс решения задач с помощью кругов Эйлера и теории графов.

Предмет исследования – круги Эйлера, теория графов.

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

– провести теоретический анализ литературы по теме исследования, определить понятия «Круги Эйлера», «Графы»;

– изучить историю возникновения кругов Эйлера и теории графов;

– рассмотреть алгоритм решения логических задач с помощью кругов Эйлера и теории графов;

создать веб-квест для решения логических задач в программной среде Microsoft Expression Web 4.

1. Теоретические аспекты понятия «Круги Эйлера»

1.1 Понятие «Круги Эйлера»

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

Автор метода - ученый Леонард Эйлер (1707-1783). Он считается немецким, швейцарским и даже российским математиком, механиком и физиком. Дело в том, что он много лет проработал в Петербургской академии наук и внес существенный вклад в развитие российской науки. А впервые Леонард Эйлер их использовал в письмах к немецкой принцессе. Он писал тогда, что «круги очень подходят для того, чтобы облегчить наши размышления». При решении задач Эйлер использовал идею изображения множеств с помощью кругов, и они получили название «круги Эйлера». С помощью этих кругов Эйлер изобразил и множество всех действительных чисел

(рис. 1).

N - множество натуральных чисел,

Z - множество целых чисел,

Q - множество рациональных чисел,

R - множество всех действительных чисел.

рис. 1

1.2 Решение задач с помощью кругов Эйлера

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

Задача №1. Сколько натуральных чисел из первого десятка не делится ни на 2, ни на 3?

рис. 2

Решение: для решения задачи удобно воспользоваться кругами Эйлера. В нашем случае три круга: большой круг – это множество чисел от 1 до 10, внутри большого – два меньших круга, пресекающихся друг с другом. Пусть множество чисел, кратных 2 – это множество А, а множество чисел, кратных 3 – множество В (рис. 2). Рассуждаем. На 2 делится каждое второе число. Значит, таких чисел будет 10:2=5. На 3 делится 3 числа (10:3). На 2 и 3 делятся те числа, которые делятся на 6. Такое число только одно. Поэтому множество А состоит из 5-1=4 чисел, множество В – 3-1=2 чисел. Отсюда следует, что в первом десятке содержится 10-(4+1+2) = 3 числа.

Задача №2. В классе 32 человека. Из них 14 играют в баскетбол, 24 - в пионербол, 16 - в волейбол. Увлекаются двумя видами спорта - баскетболом и пионерболом - шестеро, баскетболом и волейболом - четверо, пионерболом и волейболом - четверо. Трое ничем не занимаются. Сколько ребят увлекается всеми видами игры?

Решение: воспользуемся кругами Эйлера

1)32-3=29 (ч.) – играют хотя бы в одну игру.

рис. 3

2)14-6-4-Х=4-Х (ч.) – играют только в баскетбол.

3)24-6-4-Х=14-Х (ч.) – играют только в пионербол.

4)16-4-4-Х=8-Х (ч.) – играют только в волейбол.

5)4-Х+14-Х+8-Х+5+6+4=29 (ч.)

41-3Х=29

Х=4(ч.)

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

Задача №3. Ребята, которые хотят обмениваться различного рода журналами, собралось 10 человек. Среди них выписывают К - 6 человек, Т – 5 человек, Ю – 5 человек, К и Т – 3 человека, Т и Ю - 2 человека, К и Ю – 3 человека, а один человек не выписывает ни одного журнала, но читает все эти журналы в библиотеке. Надо узнать, сколько человек выписывают все три журнала, сколько – два, а сколько – только один журнал.

Решение: пусть большой круг, состоящий из 10 человек, – это множество всех ребят, обменивающихся журналами. Внутри большого круга нарисуем три меньших круга: К, Т, Ю, которые изображают ребят, подписавшихся на соответствующие журналы. Известно, что один человек не выписывает ни одного журнала. Значит, в области, расположенной вне кругов К, Т, Ю, запишем 1. В остальных ячейках получившегося рисунка запишем буквы a¸ b, c, x¸ y¸ z¸ t, которые будут обозначать число ребят, подписавшихся на соответствующие журналы.

Рис.4

Так как членов кружка было 10, то можно записать еще одно уравнение

Складывая уравнения первой системы, получим (2).

Складывая уравнения второй системы, получим (3).

Подставляя во (2) уравнение (1) и (3), получим

Отсюда t = 1, b = 2, c = 1, a =2. Значит, a + b + c = 5.

Вычисляя далее, получаем: x =1, y = 1, z = 1, т. е. x+y+z =3.

Итак, 3 – это число ребят, подписавшихся только на один журнал, 5 – это число ребят, подписавшихся на два журнала, а 1 – число ребят, подписавшихся на все три журнала.

2. Теоретические аспекты теории графов

2.1 История возникновения теории графов

Теория графов появилась благодаря одной занимательной задаче, которую решил Леонард Эйлер. История гласит, что в 1736 году этот блестящий математик остановился в Кёнигсберге (в настоящее время — Калининград). В эту эпоху четыре участка суши: правый, левый берег и два острова соединяло семь мостов (рис.5).

Горожане, гуляя по городу, пытались составить маршрут, чтобы он проходил по каждому мосту ровно один раз. Это им не удавалось, а Эйлер в переписке с итальянским математиком Мариони, доказал, что это принципиально невозможно. На упрощённой схеме части города (графе) мостам соответствуют линии (рёбра графа), а частям города - точки соединения линий (вершины графа).

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

рис.5

2.2 Понятие «Граф»

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

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

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

Рассмотрим следующую задачу.

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

Решение: допустим, это возможно. Рассмотрим граф, вершины которого соответствуют телефонам, а ребра – соединяющим их проводам. В этом графе 15 вершин, степень каждой из которых равна 5. Для подсчета количества ребер в этом графе сложим степени всех его вершин. При таком подсчете каждое ребро учтено дважды. Поэтому число ребер графа должно быть равно 15 · 5 / 2. Но это число нецелое. Значит, такого графа не существует и соединить телефоны невозможно.

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

Теорема. Число нечетных вершин любого графа четно.

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

2.3 Способы представления графа

Рассмотрим все три способа представления графа на одной задаче: «Жили-были четыре крольчонка: Бим, Бом, Бум, Бах, они все очень крепко дружили между собой». Это словесное описание графа, из этого описания нам понятно, что четыре крольчонка - это четыре вершины графа, а фраза что «они (крольчата) очень крепко дружили между собой» обозначает, что нужно соединить каждую вершину с тремя остальными вершинами ребрами.

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

рис. 6

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

Иногда в литературе встречается что вместо 1 и 0 пишут «истина» и «ложь», т.е. 1 это И (истина), а 0 это Л (ложь). Вот два варианта нашей задачи в табличном виде:

 

Бим

Бом

Бум

Бах

Бим

0

1

1

1

Бом

1

0

1

1

Бум

1

1

0

1

Бах

1

1

1

0

 

Бим

Бом

Бум

Бах

Бим

Л

И

И

И

Бом

И

Л

И

И

Бум

И

И

Л

И

Бах

И

И

И

Л

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

2.4 Виды графов

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

Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо

рис. 8

рис. 9

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

Графы, в которых не построены все возможные ребра, называются неполными графами.

рис.10

Графы, в которых построены все возможные ребра, называются полными графами

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

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

рис. 11

Неориентированный граф - это граф, в котором нет направления линий.

рис. 12

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

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

рис. 13

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

рис. 14

Закономерность 1.

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

Закономерность 2.

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

Закономерность 3. 

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

рис. 15

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

рис. 16

2.4 Решение логических задач с помощью теории графов

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

Задача №1. В классе 28 человек. Каждая девочка дружит с 4 мальчиками, а каждый мальчик – с 3 девочками. Сколько в классе мальчиков и девочек?

Р ешение: в графе, для этой задачи вершины, соответствующие мальчикам, выкрасим синим цветом, а вершины, соответствующие девочкам – красным. Каждое ребро графа соединяет ровно две вершины: одну синюю и одну красную. Пусть всего x красных и y синих вершин (x+y=28 – уравнение №1). Выразим количество ребер в графе. С одной стороны, оно равно 3x, с другой – 4y. Получим уравнение №2: 3x=4y. Решая систему из двух уравнений, легко найти, что x=16, а y=12. рис. 17

Задача №2. В первенстве класса по настольному теннису 6 участников: Андрей, Борис Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной, Еленой; Борис – с Андреем, Галиной; Виктор – с Галиной, Дмитрием, Еленой; Галина – с Андреем, Виктором и Борисом. Сколько игр проведено к настоящему моменту и сколько еще осталось?

рис. 18

Решение: построим граф. Сыгранные игры отметим синими линиями, красными дополним до полного графа. Получим, что сыграно 7 игр, а осталось – 8. Можно проверить: в графе 6 вершин, тогда всего ребер 6*5/2=15.

З адача №3. 4 человека из класса захотели поздравить друг друга с новым годом. И сделать это решили с помощью SMS. Сколько всего SMS было отправлено? Решение: необходимо построить граф, в котором вершины обозначают количество человек, а рёбра - отправленные SMS (рис. 19). Ответ: 12 SMS

рис. 19

3. Создание и реализация веб-квеста в программной среде Calameo

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

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

Приложение 1

Приложение 2

Заключение

Работа над темой исследования помогла нам понять, увлекает ли нас поиск ответов на необычные математические вопросы. В ходе исследования заключалась в изучении специализированной литературы и обобщении полученной информации, а также проведении собственных исследований при решении задач. Нами были рассмотрены общие подходы при решении некоторых логических и комбинаторных задач с помощью кругов Эйлера и теории графов. Поставленные цель и задачи исследования были решены в результате изучения теоретических аспектов понятия «Круги Эйлера» и теории графов.Мы выяснили, что графы являются существенным элементом математических моделей в самых разнообразных областях науки и практики. Они помогают наглядно представить взаимоотношения между объектами или событиями в сложных системах. Легко найти примеры графов в самых разных областях науки и практики. Сеть дорог, трубопроводов, электрическая цепь, структурная формула химического соединения, блок-схема программы. Исследуемый нами материал был реализован в создании веб-квеста в форме приключения «Заколдованный замок» в программной среде Microsoft Expression Web 4. Наш веб-квест может быть полезен для учащихся и учителей при подготовке к олимпиадам, ГИА и ЕГЭ по математике и информатике.

Результаты обратной связи и социологического опроса с обучающимися 8 и 9 классов показали, что им было легче освоить сложную тему в игровой познавательной форме веб-квеста.

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

  1. Зыков А.А. Основы теории графов. - М.:Наука, 1987, 384 с.

  2. Камерон П., ван Линт Дж. Теория графов, теория кодирования и блок-схемы - М.:Наука, 1980, 140 стр.

  3. Кристофидес Н. Теория графов. Алгоритмический подход. Пер. с анг. - М.:Мир, 1978, 432 с.

  4. Оре О. Графы и их применение: Пер. с англ. 1965. 176 с.

  5. Уилсон Р. Введение в теорию графов. Пер. с анг. 1977. 208 с.

  6. http://coollib.com/b/330732/read 

  7. https://infourok.ru/prakticheskoe_primenenie_teorii_grafov-367166.htm 

  8. http://nsportal.ru/ap/library/drugoe/2014/11/17/primenenie-grafov-v-razlichnykh-oblastyakh-zhizni

  9. https://www.tutoronline.ru/blog/krugi-jejlera 

  10. http://pandia.ru/text/78/007/83511.php

  11. http://valera-galina.blogspot.ru/2012/01/6.html

  12. http://nsportal.ru/vu/fakultet-inostrannykh-yazykov/obrazovatelnaya-tehnologiya-veb-kvest/chto-takoe-obrazovatelnyy-veb 

  13. http://katerina-bushueva.ru/publ/ikt_v_obrazovanii/ikt_v_obrazovanii/internet_uroki_i_web_kvesty/4-1-0-8 

  14. http://project.457spb.ru/DswMedia/kvesttexnologiya.pdf 

  15. https://vshot.ru/ssau/files/mir/web.pdf 

  16. http://portal.tpu.ru/f_ic/files/school/materials/ppt/9.pdf

Просмотров работы: 22