Исследовательская работа по математике "Теория графов " (7 класс)

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

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

Ваня сыграл шесть партий;

Толя сыграл пять партий;

Леша и Дима сыграли по три партии;

Семен и Илья сыграли по две партии;

Женя сыграл одну партию.

Найдите, с кем сыграл Леша.

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

Меня заинтересовали вопросы. Что такое граф? Нужен ли граф? Какие задачи можно решить при помощи графов? Где встречаются графы в повседневной жизни?

Цель: освоение приемов решения задач с помощью графов. Найти применение в решении различных головоломок, математических и логических задач и задач ЕГЭ.

• Изучить информацию по теории графов;

• Определить приемы использования теории графов в решении задач разного класса;

• Исследовать практические навыки учеников в применении элементов теории графов;

• Найти применение теории графов в жизни.

Актуальность и новизна:

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

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

Методы исследования:

Для достижения поставленных задач были использованы методы:

- анализ источников информации по проблеме.

- сбор и анализ различных типов задач.

- исследование различных способов решения.

- вывод, что решить данные задачи можно более просто, если использовать теорию графов.

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

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

Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями.

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

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

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год) , хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг .

Теория графов как математическая дисциплина стала активно развиваться со времен Эйлера (1707-1783 гг.), который в 1736 году решил задачу о Кёнигсбергских мостах.

Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз.

Можно ли побывать на всех четырех участках суши, пройдя по каждому мосту один раз и оказаться в той части суши, с которой началось движение? Эйлер отождествил с точкой (вершиной) графа каждую часть суши, а мост – с линией (ребром). Анализируя этот граф, Эйлер доказал, что сформулированная выше задача не имеет решения. Граф имеет четыре нечетные вершины, то такой граф начертить «одним росчерком» невозможно.

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

Используют графы и при построении генеалогических деревьев.

Виды графов

1. Граф-вершина. Элемент (точка) графа, обозначающий объект любой природы, входящий в множество объектов, описываемое графом. То же: узел, точка.

2. Граф-ребро. Линия, соединяющая пару смежных вершин графа.

3. Пустой граф. Пустым называется граф без ребер

4. Неориентированный граф . Если ребра не имеют ориентации , граф называется неориентированным .

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

6. Граф - дерево. Деревом называется всякий связный граф, не имеющий циклов

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

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

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

11. Несвязный граф . Две вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их. Граф называется несвязным, если хотя бы две вершины его не­связные.

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

Длиной пути называется число ребер этого пути.

Длиной цикла называется число ребер в этом цикле.

Степени вершин и подсчет числа ребер.

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

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

На рисунке изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А.На рисунке : Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

Сформулируем некоторые закономерности, присущие определенным графам.

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

Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

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

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

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

Эта закономерность справедлива не только для полного, но и для любого графа. Доказательство:

Действительно, каждое ребро графа связывает две вершины. Значит, если будем складывать число степеней всех вершин графа, то получим удвоенное число ребер 2R (R — число ребер графа), т. к. каждое ребро было подсчитано дважды, что и требовалось доказать.

Эйлеровы графы.

Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. Такими графы названы в честь учёного Леонарда Эйлера.

Закономерность 3 (вытекает из рассмотренной нами теоремы). Невозможно начертить граф с нечетным числом нечетных вершин. Закономерность 4.

Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине. Закономерность 5.

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

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

рис. (эйлеровы графы)

Решение задач с практическим применением понятия граф.

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

Задача№1. В нашем классе 5 человек изучает французский язык, остальные- английский. На уроке учитель опрашивает каждый урок одновременно 2 учеников (вопрос- ответ).Сколько пар можно составить , чтобы ученики в паре не повторялись? (9)

Задача №2 . 4 человека из нашего класса захотели поздравить друг друга с новым годом. Сделать это решили с помощью SMS-ок. Сколько всего SMS-ок было отправлено? (12)

Задача №3 . В нашем классе Александра, Никита и Валерия по медицинским показаниям могут занимать только средний ряд , 1-ю,2-ю или 3-ю парту. Чтобы помочь учителю решить спор, как рассадить учеников. Я составила граф. И ответила на вопрос , Сколькими способами они могут занять имеющиеся места? (6)

Задача №4. В нашем школе пять человек из 7 А и 7 Б классов по итогам школьной олимпиады стали призерами (Юля, Саша, Катя, Алексей, Влад). Для участия в муниципальной олимпиаде нужно было выбрать 2 человек из 5 .. Решили выбрать Одного из 7 А и один из 7Б . Сколькими способами это можно сделать? (6)

Задача №5. К учебному году мне купили школьную форму : брюки , юбка, 3 блузки ( белая, голубая, розовая) , две пары туфлей , жилетка. Сколько дней я могу комбинировать обувь и одежду, чтобы не повторить набор. Жилетка обязательна всегда. (12 дней)

Задача №6. Каждую неделю по пятницам 3-ий час физкультуры для 7А,7Б, 7В,8А.8Б проходит в бассейне и на катке в Ледовом дворце. Посещают сразу каток и бассейн одновременно три класса. Один идет на каток ,а два в бассейн .Как можно составить тройки.

Задача №7. Сколькими способами можно доехать из А в С, затем вернуться обратно, если нельзя проезжать дважды по одной и той же дороге?

5 · 3=15 способами можно выбрать путь из А в С.

2) 5 · 3 · 2 ·4 =120 способами можно доехать из А в С, затем вернуться обратно, если нельзя проезжать дважды по одной и той же дороге.

Я расчитала маршрут от школы до дома. И в этом мне помогла теория графов.

Задача №8 . От дома до школы мне можно добраться на маршрутке №6, 6Б, 6 А. Я решила посчитать, какой номер транспорта мне будет выгодней и сколько времени мне требуется, чтобы добраться от дома до школы.

Зная, последовательность остановок я составила граф и посчитала минуты. (32 мин)

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

Цепочка оповещения учеников 7 А класса .

Задача№11 .Задача на практическое применение графа-дерево.

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

Задача№10 . Я построила с помощью графа-дерева , генеалогическое дерево своей семьи.

Задачи –исследование.

Задача№11. Мне стало интересно кто с кем дружит в классе. Чтобы это выяснить, я задала вопрос.