Применение графов при решении задач в начальной школе

Обновлено: 03.07.2024

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

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

Вложение	Размер
grafy_i_ikh_primenenie_pri_reshenii_zadach.rar	358.73 КБ

Предварительный просмотр:

Қостанай ауданы әкімдігің

Заречный орта мектебі

ГУ «Отдел образования акимата

Заречная средняя школа

Графы и их применение при решении задач.

Естественно – математическое направление

(Политехническая секция в классах с казахским и русским языках обучения)

Выполнила: Мурзабекова Мадина

Руководитель: Дубогрей Светлана Ивановна

с. Заречное, апрель 2010г.

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

3. Примеры применения теории графов

4. Основные понятия теории графов

а) понятие графа

б) подсчет числа ребер

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

г) связные графы

е) плоские графы

ж) ориентированные графы

5. Примеры решения задач с помощью графов

6. Практическое применение графов

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

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

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

Леонард Эйлер – российский, немецкий и швейцарский математик, внесший огромный вклад в развитие математики. С его именем связана история появления графов. Часто упоминается его задача о Кенигсбергских мостах.

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

3. Примеры применения теории графов наглядно видны на рисунках, представленных в прилагаемой призентации.

4. Основные понятия теории графов

а) понятие графа

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

Понятие графа проще всего выяснить на примере.

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

Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу).
Сколько всего рукопожатий было сделано?

б) подсчет числа ребер

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

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

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

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

В государстве 50 городов, и из каждого выходит 8 дорог. Сколько всего дорог в государстве?

50 · 8 / 2 = 200 дорог. При решении задач очень полезна следующая теорема.

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

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

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

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

Можно ли нарисовать граф, изображенный на рисунках (а) и (б), не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?

а) Можно б) Нельзя.

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

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

Схема мостов города изображена на рисунке. Можно ли совершить прогулку, пройдя по каждому мосту один раз?

Решение. Нельзя, у соответствующего графа есть 4 нечетные вершины.

Хулиган Вася решил прогуляться по парку и его окрестностям так, чтобы при этом перелезть через каждый забор ровно один раз. Сможет ли он это сделать?

г) связные графы

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

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

В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.

Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам.

Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.

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

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

е) плоские графы

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

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

Правильный нарисованный плоский граф разбивает плоскость на куски. Если обозначить число кусков через F, число вершин через V, число ребер через E, то получаем V = 4, Е = 6, F = 4.

Для правильно нарисованного связного плоского графа имеет место равенство

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

ж) ориентированные графы

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

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

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

5. Примеры решения задач с помощью графов

Из города А в город В ведут три дороги, а из города В в город С - четыре дороги. Сколькими способами можно проехать из А в С через В?

Возьмем одну дорогу, ведущую из А в В. Ее можно продолжить до С четырьмя различными способами. То же самое можно сделать с каждой из двух других дорог, ведущих из А в В. Всего из А в С через В можно проехать 3 · 4 = 12 способами.

Сегодня учитель объявил отметки за контрольную работу. Члены математического кружка Витя, Коля, Петя, Наташа, Ира, Марина и др. решили наглядно показать, какую отметку кто получил. Как это сделать?

В данной задаче есть два множества. Нам следует установить зависимость между элементами этих множеств.

Такой чертеж называют графом:

Решение задачи можно показать и в виде таблицы.

Задачу можно решать с помощью рассуждений: а) так как Белокуров разговаривает с брюнетом, значит, Белокуров не брюнет. б) кроме того, Белокуров не блондин, так как цвет его волос не совпадает с фамилией, остается Белокуров - рыжий. в) Чернов и Рыжов не рыжие. г) так как Чернов не рыжий и не брюнет, значит, он блондин. д) Рыжов – брюнет.

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

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

Решение. 1-й способ: так как у Наташи туфли зеленые, а Вали не белые, а значит, и не зеленые, то у Вали туфли синие, поэтому у Ани туфли белые, но у нее и платье того же цвета, т.е. белое. У Наташи туфли зеленые, а платье другого цвета и не белое, значит, у наташи платье синее, поэтому у Вали платье зеленое. 2-й способ: пользуясь графами, получим рис.:

- Ляпкиным-Тяпкиным буду я! – решительно заявил Гена.

- Нет, я буду Ляпкиным-Тяпкиным, - возразил Дима. – С раннего детства мечтал воплотить этот образ на сцене.

- Ну, хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова, - проявил добродушие Гена.

- А мне – Осипа, - не уступил ему в великодушии Дима.

- Хочу быть Земляникой или Городничим, - сказал Вова.

- Нет. Городничим буду я, хором закричали Алик и Боря. – Или Хлестаковым, - добавили они одновременно.

Удастся ли распределить роли так, чтобы исполнители были довольны?

Решение. Построим граф:

Изобразим актеров кружками верхнего ряда: А – Алик, Б – Боря, В – Вова, Г – Гена, Д – Дима и роли, которые они собираются сыграть – кружками второго ряда. 1 - Ляпкин-Тяпкин, 2 – Хлестаков, 3 – Осип, 4 - Земляника, 5 – Городничий. От каждого участника проведены отрезки, т.е. ребра, к ролям, которые он хотел бы сыграть. У нас получается граф с десятью вершинами и десятью ребрами.

Нужно из десяти выбрать пять ребер, не имеющих общих вершин.

В вершины 3 и 4 ведет по одному ребру, это значит, что Осипа (вершина 3) должен играть Дима, Землянику – Вова. Вершина 1 – соединена с ребрами Г и Д. Ребро 1 – Д отпадает так как Дима уже занят, остается ребро 1 – Г, Ляпкина-Тяпкина долен играть Гена. Соединим вершины А и Б с вершинами 2 и 5. Это можно сделать двумя способами: А – 5, и Б – 2, либо А – 2 и Б – 5. В первом случае Алик будет играть Городничего, а Боря – Хлестакова, либо наоборот.

Решение. Представим всех ребят в классе в виде вершин графа. Получим 25 вершин. Соединим вершины, обозначающие друзей, ребрами. Тогда из каждой вершины будет выходить по семь ребер. Сумма степеней вершин графа будет равна 25x7=175. Это нечетное число. А нам известно, что сумма степеней вершин графа должна быть четна. Получили противоречие.

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

Решение. Рассмотрим город А. Он соединен дорогами с не менее чем семью городами В 1 , В 2 , …, В 7 , … Всего получилось не меньше 8 городов. Предположим, что есть город С, не связанный ни с А ни с В 1 , В 2 , …, В 7 , … Значит он связан только с теми городами, которые остались вне этого списка. Но таких городов меньше 7, что противоречит условию.

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

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

Задача 4. Докажите, что среди учеников любого класса найдутся двое, имеющие одинаковое число знакомых в этом классе (если, конечно, в этом классе не менее двух учеников).

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

9. Расположите на плоскости 6 точек и соедините их непересекающимися линиями так, чтобы из каждой точки выходили четыре линии.

Решение. Смотри рисунок .

10. В марсианском метро 100 станций. От любой станции до любой другой можно проехать. Забастовочный комитет хочет закрыть проезд через одну из станций так, чтобы между всеми остальными станциями был возможен проезд. Докажите, что такая станция найдётся.

Решение. План марсианского метро является связным графом. Возможны два варианта:

2 случай. Граф имеет циклы. Тогда нужно перекрыть одну из станций, принадлежащих этому циклу.

11. Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только с двумя другими. Возможна ли такая компания?

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

На участие в розыгрыше кубка поданы заявки от 16 команд. Схема проведения игр изображается графом на рисунке .

Какую информацию можно получить с помощью этого дерева? Непосредственно с него считываются:

1) число всех участников розыгрыша кубка (число закрашенных вершин);

3) число команд, участвующих

в 1/8 финала, в 1/4 финала, в 1/2 финала (число вершин соответственно в четвертом сверху ярусе, в третьем сверху ярусе, во втором сверху ярусе);

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

Составим схему-граф маршрутов:

Мы видим, что от З до М добраться нельзя.

14. В пяти корзинах лежали яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; в корзинах А, Б, В имеются яблоки пятого сорта, в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д – третьего. Пронумеруйте каждую корзину так, чтобы в корзине № 1 были яблоки первого сорта (хотя бы одно); в корзине № 2 - второго и т.д.

Свидетельство и скидка на обучение каждому участнику

Зарегистрироваться 15–17 марта 2022 г.

МБОУ Новосёлковская СШ

Использование графовых моделей при решении задач.

Доклад подготовила

учитель высшей категории:

Чернышова Наталья Владимировна .

15. 12 .2015 г.

Свое выступление я хотела бы начать словами :

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

Граф- от греческого – пишу, черчу, рисую.

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

В последнее время в практике обучения решению текстовых задач учителя и учащиеся стали широко использовать термины: построим модель задачи, использование моделирования, наряду с терминами: запишем кратко условие задачи, использование наглядности. Однако в процессе опроса установлено, что многим не ясно, в чём отличие этих терминов, а чаще всего эти термины просто отождествляются. Следует отметить, что принцип моделирования не противопоставляется принципу наглядности, а является его высшей ступенью, его развитием и обобщением. В психолого – педагогической и методической литературе под моделированием понимается построение модели с целью их изучения или получения новых знаний о объектах. Под моделью понимается мысленно или специально созданная структура, которая отражает в упрощенной или наглядной форме все основные связи и соотношения м/у элементами задачи; т.е. отражает содержание конкретной задачи.

Один из таких приемов – разбор задачи; рассуждения от данных к вопросу, от вопроса к данным или смешанного вида. Наиболее показательны в этом отношении, научить детей самостоятельно пользоваться аналитическим и синтетическим способом рассуждений. При этом уметь сопровождать эти рассуждения графической схемой. Этот способ не имеет намерения быть автоматическим. Он даёт схему самого процесса мысли, одинаково последовательного для всех случаев мышления.

Графическая модель – одна из наиболее удачных опор для построения мысленной модели задачи:

легко воспринимается зрительно;

полностью отражает внутренние связи и количественные отношения;

используются не читающими детьми;

вызывает положительные эмоции;

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

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

Когда начинать? Зависит от того , насколько дети подготовлены к этому. Основной критерий готовности: способность чётко и аккуратно выполнять графические построения (ставить точки, строить отрезки, соединять точки линиями от руки).

Решение задач с помощью графов можно выделить 3 этапа:

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

Для этого необходимо уметь:

- ввести условное обозначение объектов и связей м/н.;

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

2.Первый этап – задачи с небольшим числом объектов с связей м/н.

3.Второй этап – дальнейшее обучение решению задач с помощью графов, но идёт увеличение количества объектов, связей м/у объектами.

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

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

Главное правило построения модели состоит в том, что она должна отражать только существенные свойства объекта и структуру связей и отношений. Для математической модели задачи главным будет то, что она отражает количественные отношения предложенной в ней ситуации. А главные связи это связи м/у данным и искомым.

Трудность перехода от словесной модели к образу состоит в том, что ученику надо абстрагироваться. Сделать это ученику 6-7 лет очень трудно т.к. в этом возрасте преобладает наглядно-образное мышление, которое непосредственно зависит от восприятия. Таких детей очень мало, поэтому учителю приходиться пользоваться сначала наглядностью – это 1 этап.

Предметная модель – дети практически решают задачи.

Положите 5 зайцев.2 зайца убежали(убираем). Сколько зайцев осталось?

Как записать? 5-2=3

Второй этап – знаково – символические модели:

Иконические-это разного рода рисунки, схемы, чертежи;

Знаковые – это разного рода числовые выражения, уравнения, неравенства.

Дети посадили у школы 5 лип и 3 берёзы. Сколько всего деревьев посадили

дети в школьном саду?( рис.1)

Памятка – алгоритм.

Рассуждай так:

1.Мне известно….

2.Надо узнать….

3.Рисую и объясняю…

4.Подумаю, что надо сделать…

5.Объясняю решение…

7.Отвечаю на вопрос задачи…

Затем происходит частичноё свертывание оъяснения.

Было15 яблок. Съели 5 яблок утром и 4 вечером. Сколько осталось яблок?

Было – 15 яб.

Съели – 5 яб. и 4 яб.

Вопрос один, а задача в 2 действия. Данную задачу удобно решать используя графическую модель. Главное достоинство схемы – точное отображение смысла операции сложения (объединение) и вычитания (удаление части).

К данной задаче можно составить следующие схемы: (рис. 2 )

Данная задача допускает составление разных схем, а значит разных способов решения задачи.(15-5-4=6 15-(5+4)=6 1)15-5=10 2)10-4=6)

Третий этап – абстрактная графическая схема – отрезок.

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

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

Задачи на нахождение целого по неизвестным частям

Задачи на нахождение неизвестной части по известному целому и другой части.

1.Задачи на нахождение суммы.

2.Задачи на нахождение неизвестного уменьшаемого.

3.Задачи на увеличение на несколько единиц.

1.Задачи на нахождение остатка.

2.Задачи на нахождение неизвестного слагаемого.

3.Задачи на нахождение неизвестного вычитаемого

4.Задачи на уменьшение на несколько единиц

5.Задачи на разностное сравнение.

При использовании чертежа учащимися, как правило не испытывают затруднений при объяснении, т. к. за каждым словом стоит образ – отрезок, а ещё раньше – предметное действие. Опыт показывает, что дети без особых трудностей, естественно переходят к решению задач в 2 действия.

Все составные задачи 1 класса по виду схематического рисунка можно разделить на 5 групп:

1. У Кати на полке 7 книг, а в портфеле на 5 книг меньше. Сколько всего

книг у Кати?

2.На елку повесили 7 красных шаров, а синих на 3 больше. Сколько всего

шаров на ёлке?

3.Саша принёс 6 морковок, а Оля 4 морковки. 8 морковок они отдали

кроликам. Сколько морковок осталось?

4. Во дворе убирали снег 9 ребят, к ним подошли ещё 3 мальчика, а потом

ещё 2 девочки. Сколько всего ребят стали убирать снег?

5.В куске было 15м ткани. Одному отрезали 5м ткани, а другому 4м.

Сколько м ткани осталось в куске? ( рис.4)

Есть задачи которые нельзя решить арифметически.

В классе играли в шахматы 4 человека: Маша, Саша, Игорь и Наташа..

Какие были пары игроков, если все они сыграли друг с другом по одному

Игроки это точки, а отношения сыграли – отрезки. Точки лучше расставлять по кругу.(рис.5) Способ перебора помогает безошибочно и быстро определить пары.

(Маша-Саша, Маша-Игорь, Маша- Наташа, Саша-Игорь, Саша-Наташа)

Пять человек обменялись рукопожатиями Сколько было рукопожатий?

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

Для Вани, Толи и Миши есть 3 пирога: с рисом ,капустой и с яблоками.

Миша не любит пирог с яблоками и не ест пирог с капустой. Ваня не

любит пирог с капустой. Кто что ест?

Две группы объектов.(рис.7)

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

Умение выполнять различные модели даёт учащимся возможность выбирать ту, которая представляется им наиболее приемлемой для той или иной задачи. Выбор и построение моделей задач во многом зависит от знаний и умения учащегося.

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

Виды работ над задачами:

Составить задачу : по картинке, по чертежу, по схематическому рисунку, по краткой записи, по решению.

Составить к данному условию вопрос или к вопросу условие.

Изменить вопрос (или условие ) так, чтобы задача решалась другим действием.

Читаются задачи , а дети показывают только ответ (или записывают).

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

Решение задач в сравнении.

Решение задач с недостающими или лишними данными.

Классификация задач ( разделить задачи на группы по какому-то признаку или просто найти похожие задачи).

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

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

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

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

Объект исследования: сфера деятельности человека на предмет применения метода графов.

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

познакомиться с историей возникновения графов;

изучить различные виды графов и их элементы;

рассмотреть примеры применения графов в современном мире;

рассмотреть решение задач при помощи графов;

сравнить традиционные методы решения задач с методами теории графов.

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

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

ГЛАВА 1. ИСТОРИЧЕСКИЕ АСПЕКТЫ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ

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

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года.

Старинная карта Кёнигсберга

1 — Лавочный, 2 — Зелёный, 3 — Рабочий, 4 — Кузнечный, 5 — Деревянный,6 — Высокий, 7 — Медовый

С прашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке (рис. 2,3) , где вершины графа соответствуют определённому району города, а ребра – мостам через реку,
на котором A обозначает остров, а B , C и D – части континента, отделенные друг от друга рукавами реки.

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

Основные определения и теоремы теории графов

Графом в математике называется конечная совокупность точек, именуемых вершинами; некоторые из них соединены друг с другом линиями, называемыми ребрами графа (рис. 4) .

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

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

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

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

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

рис. 5 рис. 6 рис. 7

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

Г раф называется несвязным, если первое условие не выполняется (рис.9) .

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

Г раф, в котором две любые вершины соединены ровно одним простым путём, является деревом (рис.10). Чаще всего они встречаются при составлении родословных. Трехмерной моделью графа-дерева служит, например, настоящее дерево с его замысловато разветвленной кроной; река и ее притоки также образуют дерево, но уже плоское – на поверхности земли.

Свойства деревьев :

1. Чтобы простой связный граф был деревом, необходимо и достаточно, чтобы число вершин было больше числа ребер на один. 2. Чтобы граф был деревом, необходимо и достаточно, чтобы любые две вершины его соединялись единственным маршрутом.
3. Граф будет деревом тогда и только тогда, когда добавление любого нового ребра приводит к появлению ровно одного цикла.

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

Плоские графы обладают многими интересными свойствами. Так, Эйлер обнаружил простую связь между количеством вершин (В), количеством ребер (Р) и количеством частей (Г), на которые граф разделяет плоскость:

В качестве примера можно рассмотреть следующую задач у:

Каналы их соединяют.

А между ними – острова,

И сколько их – никто не знает. [13, 276]

Решение. Рассмотрим граф, в котором вершины соответствуют островам, а рёбра — каналам. Полученный граф будет плоским и связным, значит, для него выполняется формула Эйлера: В — Р + Г = 2. Для нашего графа В = 7, Р = 10. Подставляя в формулу, получаем 7 — 10 + Г = 2. Отсюда следует, что Г = 5, то есть, рёбра графа разбивают плоскость на 5 частей. Островам соответствуют все грани, кроме внешней (она бесконечно большая во все стороны и острову соответствовать не может), значит, их 4 .

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

Большой интерес вызывают графы, которые можно нарисовать, не отрывая карандаша от бумаги. Их называют эйлеровыми в честь учёного Леонарда Эйлера (рис.12) .

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

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

Н а рисунке 13: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

В графе сумма степеней всех его вершин — число четное, равное удвоенному числу ребер графа, так как каждое ребро

участвует в этой сумме ровно два раза. Этот результат, известный еще двести лет назад Эйлеру, часто называют леммой о рукопожатиях . Из нее следует, что если несколько человек обменялись рукопожатиями, то общее число пожатых рук обязательно четно, ибо в каждом рукопожатии участвуют две руки (при этом каждая рука считается столько раз, сколько она участвовала в рукопожатиях). Число нечетных вершин любого графа четно. Во всяком графе с вершинами, где, всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями. [20, 146]

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

В Приложении 3 подготовлен материал с эйлеровыми графами для решения в группе.

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

О Кенигсбергских мостах. Город Кенигсберг расположен на берегах реки Прегель и двух островах. Различные части города были соединены семью мостами. По воскресеньям горожане совершали прогулки по городу.

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

Мосты через реку Прегель расположены как на рисунке.
(приложение 2 рис.1).

Рассмотрим граф, соответствующий схеме мостов

Проблема семи мостов Кёнигсберга.
Суть: можно ли пройти по 7 мостам города Кёнигсберга, не ступив на каждый более одного раза.

Решение: было найдено русско-немецким математиком Леонардом Эйлером(1736 год).

1) Число нечётных вершин графа должно быть чётно (теорема 2).
2) Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
3) Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
4) Граф кёнигсбергских мостов имел четыре нечётные вершины, следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

Решение: Нарисуем схему: планетам будут соответствовать точки, а соединяющим их маршруты – не пересекающиеся между собой линии.

с Земли до Марса добраться нельзя.

Логические задачи.

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

Решение: одна из возможных схем приведена на рисунке.

(приложение 2 рис.2)

На соревнование уйдет 7 часов.

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

Решение: Разобьем монеты на три группы по три монеты. Положим монеты двух групп на разные чашки весов.

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

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

Решение этой задачи легко изобразить в виде графа-дерева, похожего на алгоритм. (приложение 2, рис.3)

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

Решение:
Нарисуем пять точек и обозначим их буквами А, Б, В, Г, Д.

Это первые буквы имён.

Соединим те точки, которые соответствуют именам созвонившихся ребят.

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

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

В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. Требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю.

Решение:

Ситуацию в каждый момент можно описать тремя числами (приложение рис.16).

одно в 7 ходов, другое в 8 ходов.

Имеется шахматная доска 3x3, в верхних двух углах стоят два чёрных коня, в нижних – два белых (рисунок ниже). За 16 ходов поставьте белых коней на место чёрных, а чёрных на место белых и докажите, что за меньшее число ходов это сделать невозможно.

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

Тогда, передвигая коней в графе, каждый раз перемещая всех коней, как показано на рисунках 1-4, мы получим за 16 ходов белых коней на месте чёрных, а чёрных на месте белых (рис.5). (приложение 2, рис.6)

Примеры задач, решаемых методом графов в приложении 3.

Читайте также: