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

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

Мешкова В.А. 1Копытько К.Ю. 1

---

1МОАУ "Лицей №6"

Мосина И.Г. 1Сулеева И.В. 1

---

1МОАУ "Лицей №6"

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

3.2 MB

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

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

Введение

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

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

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

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

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

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

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

– создать веб-квест для решения логических задач в программной среде 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 это Л (ложь). Вот два варианта нашей задачи в табличном виде: