Графы
Исследовательская работа ученика 6 класса.
Скачать:
Предварительный просмотр:
Муниципальное образовательное учреждение Пеновская средняя общеобразовательная школа имени Е.И. Чайкиной
УЧЕБНО-ИССЛЕДОВАТЕЛЬСКАЯ РАБОТА
ПО МАТЕМАТИКЕ
Г Р А Ф Ы.
работу выполнил: обучающийся 6А класса МОУ Пеновская СОШ имени Е.И. Чайкиной Крылов Павел. Руководитель: учитель математики МОУ Пеновская СОШ Рябочкина С.В |
пос. Пено, 2010
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ………………………………………………………………….3
ОСНОВНАЯ ЧАСТЬ:
ИСТОРИЯ ВОЗНИКНОВЕНИЯ ГРАФОВ………………………………..4
ТАК ЧТО ЖЕ ТАКОЕ ГРАФЫ?..………………………………………….4
ПРИМЕР ПРИМЕНЕНИЯ ГРАФОВ………………………………………6
РЕШЕНИЕ ЗАДАЧИ НА ПЕРЕЛИВАНИЕ……………………………….7
ЗАКЛЮЧЕНИЕ…………………………………………………………….10
СПИСОК ЛИТЕРАТУРЫ………………………………………………….11
ВВЕДЕНИЕ.
Ещё в начальной школе мы не раз встречались с задачами, в которых нужно было рассматривать различные комбинации и сочетания. Например, используя цифры 3;5;8;2 составить всевозможные двузначные числа. Мы решали эту задачу с помощью перебора различных вариантов (35;38;32;82;58;и т.д.). А на занятиях математического кружка нам показали, как можно выполнить это задание с помощью графов.
Первая строка – это первая цифра в числе, вторая строка – это вторая цифра в числе.
33 35 38 32 53 55 58 52 83 85 88 82 23 25 28 22
Решая задачу с помощью графа мы не пропустим не одного числа, а решая её с помощью перебора какие-нибудь числа можно пропустить.
Также решая задачу с помощью графа легко определить, сколько таких двузначных чисел получиться.
Когда у нас в школе проходила неделя математики, то во время соревнований между шестыми классами, была дана следующая задача:
Сколько двузначных чисел можно составить из цифр 1;2;3?
Наша команда быстрее всех нашла правильный ответ, на этот вопрос, используя графы.
Мне понравилась тема графы, и я решил поподробнее её рассмотреть и исследовать.
История возникновения графов.
По одной из версий впервые графы были изобретены в Англии и Германии одновременно в конце xv начале xvI века. В Англии они использовались для решений математических задач, а в Германии они использовались совсем по другому назначению, как мера оплаты. На фермы накладывались графы, но оплачивать их надо было не деньгами, а тем, что производили этих фермах.
По другой версии графы возникли в России в XVlll веке. Использовались они только для решений математических задач. Крупнейший математик восемнадцатого века Леонард Эйлер стал заниматься графами. Он первый с помощью графов описывал решение головоломок и математических развлекательных задач. Широкое развитие теория графов получила с 50-х г. XX века в связи с развитием кибернетики и вычислительной техникой.
Так что же такое графы?
Графы это геометрические фигуры, состоящие из точек, которые называют вершинами, и соединяющих их отрезков, которые называются рёбрами графа. При этом с помощью вершин изображают элементы некоторого множества (предметов, людей, числовых и буквенных кодов и т.п.), а с помощью рёбер определенные связи между этими предметами.
Для удобства иллюстрации условия задачи с помощью графа его вершины-точки могут быть заменены кружками или прямоугольниками, а рёбра-отрезки - любыми линиями. Примеры различных графов приведены на рисунке.
Генеалогическое древо также является примером графа.
При взгляде на географическую карту сразу бросается в глаза сеть железных и автомобильных дорог. Это типичный граф: кружки обозначают станции - вершины, а соединяющие их пути – рёбра.
Пример применения графа.
Граф изображает схему дорог между селами М; А; Б; В; Г; Здесь каждые две вершины соединены между собой ребром. Такой граф называется полным. Числа на рисунке обозначают расстояния между селами по этим дорогам. Пусть в селе М находится почта и почтальон, который должен развести в остальные сёла письма. Существует много разных маршрутов. Как выбрать наикратчайший?
Проще всего проанализировать все варианты. Сделать это можно только с помощью нового графа, на котором будут видны все возможные маршруты.
Вершина М вверху - начало маршрутов. Из неё можно начать путь четырьмя разными способами: в А, в Б, в В или в Г. После посещения одного из сёл остается три возможных продолжения маршрута, потом две, потом дорога в последнее село и снова в М.Всего 4*3*2*1=24 способа. Все они представлены на рисунке ниже.
Расставим вдоль рёбер графа цифры, обозначающие расстояния между селами, а в конце каждого маршрута напишем сумму этих расстояний по маршруту. Из полученных 24-х чисел наименьшими являются два числа по 28 км., соответствующие маршруты М-В-Б-А-Г-М и М-Г-А-Б-В-М.
Заметим, что это один и тот же путь только пройден по-разному.
Решение задачи на переливание.
При посещении математического кружка, мне очень понравились задачи на «переливания». Например, нам нужно решить следующую задачу: Сосуд ёмкостью 8 литров наполнен водой, имеется ещё два пустых сосуда ёмкостью 5 и 3 литра. Как с помощью этих сосудов отметить ровно один литр воды?
Эту задачу можно решать несколькими способами.
1.С помощью рассуждений.
- Перельём воду из 8 литрового сосуда в 3-х литровый.
- Затем из 3-х литрового перельём в 5-ти литровый сосуд.
- Из 8-ми литрового сосуда, в котором осталось 5 литров воды, снова перельём воду в 3-х литровый.
- Из 3-х литрового сосуда добавим в 5-ти литровый сосуд, в котором уже есть 3 литра воды, ещё 2 литра.
- Таким образом в 3-х литровом сосуде осталось 1 литр воды.
2. С помощью схематического рисунка.
- С помощью таблицы.
8 л. | 8 | 5 | 5 | 2 | 2 |
3 л. | - | 3 | - | 3 | 1 |
5 л. | - | - | 3 | 3 | 5 |
Я решил рассмотреть решение этой задачи с помощью графа.
Вершины графа-это три числа, которые показывают, в каких сосудах сколько литров воды находится.
Первое число – количество воды в 8-ми литровом сосуде, второе число – в 5-ти литровом, третье число – в 3-х литровом.
По решению видно, что задача решается двумя способами, но самый короткий в четыре шага.
Заключение.
Интересные задачи, весёлые головоломки всё это графы. Хороший способ провести время и занять друзей. Изучая тему графы я не тратил время зря, а наоборот с пользой.
При решении задач с помощью графов, мы имеем возможность предусмотреть все возможные варианты решения задачи и выбрать наиболее рациональный.
Список литературы.
- Григорьева Г.И. Подготовка школьников к олимпиадам по математике: 5-6 классы. М.: Издательство «Глобус», 2009. – 152с.
- Энциклопедический словарь юного математика / Сост. Савин А.П. – М. : Педагогика, 1985. – 352с.
- Ткачёва М. В., Фёдорова Н.Е. Элементы статистики и вероятность: учебное пособие для 7 – 9 классов общеобразовательных учреждений 3 – е изд. – М.: Просвещение 2006. - 112с.
- Шарыгин И. Ф., Шевкин А.В. Математика: Задачи на смекалку: Учебное пособие для 5 – 6 кл. общеобразовательных учреждений. – 2-е изд., дораб. – М.: Просвещение, 1996. – 80 с.
8
5
3
2
3
5
8
2
3
5
8
2
3
5
8
2
2
5
8
3
А
В
С
Д
А
А
В
Е
Д
С
Иван
Борис
Татьяна
Иван
Ольга
Сергей
Галина
М
А
Б
В
Г
7
7
6
9
5
11
13
6
10
4
м
А
Б
В
Г
В
Г
А
В
Г
А
Б
Г
А
Б
В
В
Г
Б
Г
Б
В
В
Г
А
Г
А
В
Б
Г
А
Г
А
Б
Б
В
А
В
А
Б
Г
В
Г
Б
В
Б
Г
В
Г
А
В
А
Г
Г
А
Б
А
В
Б
В
А
Б
А
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
Б
Б
30 42 44 50 37 37 41 37 36 37 45 50 41 45 28 37 37 42 28 36 41 44 41 30
7 10 6 4
7 11 5 7 6 13 11 6 9 5 13 9
6 13 6 9 13 9 11 5 11 9 5 9 7 5 7 13 5 13 7 11 7 6 11 6
9 9 13 13 6 6 9 9 5 5 11 11 13 13 5 5 7 7 6 6 11 11 7 7
4 6 4 10 6 10 4 6 4 7 6 7 4 10 4 7 10 7 6 10 6 7 10 7
8; 0; 0;
3; 5; 0
5; 0; 3
3; 2; 3
6; 2; 0
6; 0; 2
1; 5; 2
0; 5; 3
5; 3; 0
2; 3; 3
2; 5; 1
8; 0; 0;
3; 5; 0
5; 0; 3
3; 2; 3
6; 2; 0
6; 0; 2
1; 5; 2
0; 5; 3
5; 3; 0
2; 3; 3
2; 5; 1
Предварительный просмотр:
Подписи к слайдам:
Хитрость Дидоны
Н. Гумилёв. Жираф
Одна беседа. Лев Кассиль
Мост из бумаги для Киры и Вики
Солдатская шинель