Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Математика / Другие методич. материалы / Исследовательская работа по теме "Решение олимпиадных задач с помощью графов"
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 26 апреля.

Подать заявку на курс
  • Математика

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

Выбранный для просмотра документ Доклад.docx

библиотека
материалов

Здравствуйте. Меня зовут Гришаев Павел. Я ученик школы № 2, 6 А класса. Тема нашей работы «Решение олимпиадных задач с помощью графов»

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

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

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

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

1. Проанализировать математическую и методическую литературу по теме «Графы»;

2. Рассмотреть основные типы задач, решаемых с помощью графа.

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

4. Создать электронный задачник «Решение олимпиадных задач с помощью графов».

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

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

Методы исследования: поисковый метод, исследовательский метод, практический метод

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

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

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


сканирование0060

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

сканирование0061


Такую фигуру стали называть графом.

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

Вершины, из которых выходит нечетное число ребер, называют нечетными вершинами, а вершины, из которых выходит четное количество ребер, - четными.

Свойства графа.

Решая задачу про кенигсбергские мосты, Эйлер установил свойства графа:

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

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

3.Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.

4.Число нечетных вершин графа всегда четное.

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

Выделяют несколько типов задач решаемых данным методом графов:

  1. Задачи на вычерчивание фигур одним росчерком.

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

  3. Задачи о мостах.

  4. Задачи о "правильном" раскрашивании карт.

  5. Задачи о колодцах.

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

Нами были рассмотрены первые два типа задач.

Задачи на вычерчивание фигур одним росчерком.

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

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

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

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

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

ЗАДАЧА № 5 Купленные в подарок игрушки (пистолет, сумочку, куклу и машину) уложили в четыре коробки, по одной игрушке в каждую. Требуется узнать, что положено в каждую коробку, если известно следующее: машинка и пистолет не в красной коробке; коробка с сумочкой находится между синей коробкой и коробкой с куклой; в зеленой коробке не сумочка и не машинка; желтая и зеленая коробки находятся около коробки с пистолетом.



















V.Заключение.

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

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

В ходе работы:

  • Мы проанализировали математическую и методическую литературу по теме «Графы».

  • рассмотрели типы задач, решаемых с помощью графов

  • привели примеры решения задач, решаемых с помощью графов;

  • создали электронный задачник «Решение олимпиадных задач, с помощью графов».

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




.

Выбранный для просмотра документ Основная часть.docx

библиотека
материалов

hello_html_3c905cf2.gifhello_html_3c905cf2.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_3c905cf2.gifhello_html_3c905cf2.gifhello_html_3c905cf2.gifhello_html_3c905cf2.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_3c905cf2.gifhello_html_m2a7690f7.gifhello_html_3c905cf2.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_3c905cf2.gifhello_html_m2a7690f7.gifhello_html_3c905cf2.gifhello_html_3c905cf2.gifhello_html_3c905cf2.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifВВЕДЕНИЕ

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

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

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

Цель работы: изучение метода графов и применение его при решении олимпиадных задач.

Задачи:

  1. Проанализировать математическую и методическую литературу по теме «Графы».

  2. Рассмотреть основные типы задач, решаемых с помощью графов.

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

  4. Создать электронный задачник «Решение олимпиадных задач с помощью графов».

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

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

Методы исследования: поисковый метод, исследовательский метод, практический метод.

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

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


ГЛАВА 1 ИСТОРИЧЕСКИЕ И ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ О ГРАФЕ

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

Первая работа по теории графов принадлежит Леонарду Эйлеру. Она появилась в 1736 году в публикациях Петербургской Академии Наук и начиналась с рассмотрения задачи о кенигсбергских мостах.

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


сканирование0060

Рисунок. 1. Кенигсбергские мосты.

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

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


сканирование0061

Рисунок. 2. Граф.

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



    1. Теоретические сведения о графе

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

Вершины, из которых выходит нечетное число ребер, называют нечетными вершинами, а вершины, из которых выходит четное количество ребер - четными.

На рисунке 2,точки A,B,C,D - вершины графа, AD, CD, BD, CA, AB – ребра графа. Из вершин B,C,D выходят по 3 ребра (нечетные вершины), а из вершины A – 5 ребер (нечетная вершина).

Решая задачу про кенигсбергские мосты, Эйлер установил свойства графа:

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

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

  3. Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.

  4. Число нечетных вершин графа всегда четное.

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

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


ГЛАВА 2 ТИПЫ ЗАДАЧ, РЕШАЕМЫХ С ПОМОЩЬЮ ГРАФОВ

Выделяют несколько типов задач решаемых с помощью графа:

  1. Задачи на вычерчивание фигур одним росчерком.

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

  3. Задачи о "правильном" раскрашивании карт.

  4. Задачи о мостах.

  5. Задачи о колодцах.

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

Рассмотрим два первых типа задач и способы их решения.


2.1. Задачи на вычерчивание фигур одним росчерком

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

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

сканирование0007

Рисунок. 3.Эйлеровы графы и графы.

Предлагаю начертить одним росчерком следующие фигуры (рис. 4).

сканирование0006

Рисунок. 4.Эйлеровы графы.


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

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

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

Задача 1. Любимые мультфильмы.

Жила-была одна дружная семья: мама, папа и сын. Они все любили делать вместе. Но вот мультфильмы любили разные: «Ну, погоди!», «Покемоны», «Том и Джерри». Определите, какой мультфильм любит каждый из них, если мама, папа и любитель мультфильма «Покемоны» никогда не унывают, а папа и любитель мультфильма «Том и Джерри» делают зарядку по утрам?

Решение.

Из условия задачи выделим две группы. Первая группа - люди: мама, папа, сын; вторая группа - мультфильмы «Ну, погоди!», «Покемоны», «Том и Джерри». Обозначим элементы этих двух групп точками - вершины графа (рисунок. 5):

http://logika.vobrazovanie.ru/image/11.PNG

Рисунок. 5. Вершины графа.

Если точке из одной группы соответствует точка из другой группы, будем соединять эти точки сплошной линией, если не соответствует – то штриховой.
Заметим, что по условию задачи у человека только один любимый мультфильм.
Учитывая данные задачи, получаем следующую схему (рисунок. 6):

http://logika.vobrazovanie.ru/image/12.PNG

Рисунок. 6. Схема решения задачи

Из условия задачи следует, что нужно найти единственно возможное соответствие между элементами двух групп.

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

Поэтому граф на рисунке будет выглядеть следующим образом (рисунок. 7):

http://logika.vobrazovanie.ru/image/13.PNG

Рис. 7. Граф

Теперь мы установили, что папа любит мультфильм «Ну, погоди!», сын – «Покемоны». В обеих группах остается только по одной точке, следовательно, мама любит мультфильм «Том и Джерри». Задача решена.


ГЛАВА 3 РЕШЕНИЕ ОЛИМПИАДНЫХ ЗАДАЧ, С ПОМОЩЬЮ ГРАФОВ. ЛОГИЧЕСКИЕ ЗАДАЧИ


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


Решение:

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

Андрей

Виктор







Дмитрий

Елена

Галина

Борис





Рисунок. 8. Граф.

Посчитав количество ребер, ответим на вопрос, сколько игр сыгранно к настоящему моменту. Ответ: 7 игр.

Борис

Елена

Андрей

Построим граф, не проведенных игр (рисунок. 9).







Галина

Дмитрий

Виктор





Рисунок. 9. Граф

На этом рисунке граф имеет 8 ребер, следовательно, осталось провести 8 игр.

Задача 3. В школьном драматическом кружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Началось все с Ляпкина–Тяпкина.

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

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

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

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

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

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

Решение:Построим граф для ситуации, описанной в задаче (рисунок. 10).







Рисунок. 10. Граф.

Граф с 10 вершинами и 10 ребрами. Надо выбрать 5 ребер, не имеющих общих вершин: Дима – Осип, Вова – Земляника, Гена – Ляпкин-Тяпкин. Остается два случая: Алик – Хлестаков, Боря – Городничий или Алик – Городничий, Боря – Хлестаков. Как показывает граф других решений нет.

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

Решение (рисунок. 11):









Рисунок. 11. Граф

Задача 5.Купленные в подарок игрушки (пистолет, сумочку, куклу и машину) уложили в четыре коробки, по одной игрушке в каждую. Требуется узнать, что положено в каждую коробку, если известно следующее: машинка и пистолет не в красной коробке; коробка с сумочкой находится между синей коробкой и коробкой с куклой; в зеленой коробке не сумочка и не машинка; желтая и зеленая коробки находятся около коробки с пистолетом.

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











Рисунок. 12. Граф

Становится очевидным, что пистолет лежит в синей коробке, соединяем соответствующие вершины стрелкой. Теперь становится очевидным то, что машина находится в желтой коробке. Сумочка лежит в красной коробке, а кукла в зеленой (рисунок. 13).

















Рисунок. 13. Граф

Ответ: пистолет – в синей, сумочка – в красной, кукла – в зеленой, машинка – в желтой коробках.

Задача 6.Четыре одноклассника – Володя, Толя, Оля и Сережа выбраны классным собранием для работы в шефском, культурно-массовом, спортивном и учебном секторах школы. Определите, кого из ребят, в какой из названных секторов выбрали, если известно, что:

  1. Володя и член культсектора живут в одном доме, и они вместе с Олей втроем ездят в школу на автобусе;

  2. На классном собрании, было решено, в спортсектор избрать мальчика;

  3. Член учебного сектора и Сережа вместе ходят на теннисный корт;

  4. Член спортсектора и Володя – большие друзья;

  5. Оля сидит за одной партой с членом учебного сектора.

Решение:Составим граф из групп - ребят и групп –секторов (рисунок 14).













Рисунок 14. Граф.

Ответ: Оля – шефский сектор, Володя – учебный сектор, Толя – культмассовый, Сережа – спортивный сектор.

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

Решение:Составим граф (рисунок 15).











Рисунок 15. Граф.

Ответ: №1 – Г; №2 – А или №2 – Б; №3 – Д, №4 – В; №5 – Б или №5 – А.

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

Решение:

Точки А, Б, В, Г, Д называются вершинами графа, а отрезки линий, соединяющие эти точки — ребрами графа.В задаче необходимо подсчитать число ребер графа, изображенного на рисунке. Это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10 (рис. 15).hello_html_m12ea8e77.png















Рис. 15. Граф







ЗАКЛЮЧЕНИЕ

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

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

В результате работы мы:

  • провели анализ математической и методической литературы по проблеме исследования с целью выделения основных теоретических фактов для решения олимпиадных задач;

  • рассмотрели типы задач, решаемых с помощью графов;

  • привели примеры решения задач, решаемых с помощью графов;

  • создали электронный задачник «Решение олимпиадных задач, с помощью графов».

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

Сейчас я остановился на третьем типе задач «Задачи о «правильном» раскрашивании карт».











СПИСОК ЛИТЕРАТУРЫ


  1. Балаян Э. Н. Готовимся к олимпиаде по математике: 5- 6 классы / Э. Н. Балаян. – Ростов н/Д: Феникс, 2010 – 180 с.

  2. Барболин М. Головоломки и графы // научно-популярный физико-математический журнал «Квант» - 1994. - № 6 – 33 с.

  3. Березина Л. Ю. Графы и их применение: Пособие для учителей / Л. Ю. Березина. – М.: Просвещение, 2001 – 143 с.

  4. Горбачев В. Г. Сборник олимпиадных задач по математике / В. Г. Горбачев. – М., 2004 – 56 с.

  5. Мельников О. И. Теория графов в занимательных задачах. Изд. 3-е. / О. И. Мельников – М.:КомКнига, 2009. – 232 с.

  6. Оре О. Графы и их применение: Пер. с англ. / О. Оре. – М.:Наука, 1980. – 176 с.

  7. ЦОР [Электронный ресурс] – Режим доступа: http://school-collection.edu.ru/catalog/rubr/696f5fc4-7f5c-b610-713f-014b7f9c0bc8/45946/.

  8. Фосс В. Элементы теории графов // научно-популярный физико-математический журнал «Квант» - 1973. - № 8 – 17 с.




1


Выбранный для просмотра документ Презнтация к докладу Графы.pptx

библиотека
материалов
Решение олимпиадных задач с помощью графов Выполнил: Гришаев Павел, 6 А, шк....
Цель: изучение метода графов и применение его при решении олимпиадных задач....
Предмет: олимпиадные задачи. Объект: применение метода графов при решении ол...
Основные ожидаемые результаты Решить олимпиадные задачи с помощью графов Созд...
Кенигсбергские мосты
Граф Граф - это геометрическая фигура, состоящая из точек (вершины графа) и л...
Свойства графа Если все вершины графа четные, то можно одним росчерком (т.е....
Типы задач Задачи на вычерчивание фигур одним росчерком. Логические задачи. З...
Задачи на вычерчивание фигур одним росчерком
Логические задачи Купленные в подарок игрушки (пистолет, сумочку, куклу и маш...
Заключение 	 Проанализировали математическую и методическую литературу по тем...
Спасибо за внимание!
12 1

"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs

Описание презентации по отдельным слайдам:

№ слайда 1 Решение олимпиадных задач с помощью графов Выполнил: Гришаев Павел, 6 А, шк.
Описание слайда:

Решение олимпиадных задач с помощью графов Выполнил: Гришаев Павел, 6 А, шк. № 2 Руководитель: Баева И. В., учитель математики

№ слайда 2 Цель: изучение метода графов и применение его при решении олимпиадных задач.
Описание слайда:

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

№ слайда 3 Предмет: олимпиадные задачи. Объект: применение метода графов при решении ол
Описание слайда:

Предмет: олимпиадные задачи. Объект: применение метода графов при решении олимпиадных задач.

№ слайда 4 Основные ожидаемые результаты Решить олимпиадные задачи с помощью графов Созд
Описание слайда:

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

№ слайда 5 Кенигсбергские мосты
Описание слайда:

Кенигсбергские мосты

№ слайда 6 Граф Граф - это геометрическая фигура, состоящая из точек (вершины графа) и л
Описание слайда:

Граф Граф - это геометрическая фигура, состоящая из точек (вершины графа) и линий, их соединяющих (ребра графа). A, B, C, D – вершины графа CD, CA, AD, DB – ребра графа

№ слайда 7 Свойства графа Если все вершины графа четные, то можно одним росчерком (т.е.
Описание слайда:

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

№ слайда 8 Типы задач Задачи на вычерчивание фигур одним росчерком. Логические задачи. З
Описание слайда:

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

№ слайда 9 Задачи на вычерчивание фигур одним росчерком
Описание слайда:

Задачи на вычерчивание фигур одним росчерком

№ слайда 10 Логические задачи Купленные в подарок игрушки (пистолет, сумочку, куклу и маш
Описание слайда:

Логические задачи Купленные в подарок игрушки (пистолет, сумочку, куклу и машину) уложили в четыре коробки, по одной игрушке в каждую. Требуется узнать, что положено в каждую коробку, если известно следующее: машинка и пистолет не в красной коробке; коробка с сумочкой находится между синей коробкой и коробкой с куклой; в зеленой коробке не сумочка и не машинка; желтая и зеленая коробки находятся около коробки с пистолетом.  

№ слайда 11 Заключение 	 Проанализировали математическую и методическую литературу по тем
Описание слайда:

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

№ слайда 12 Спасибо за внимание!
Описание слайда:

Спасибо за внимание!

Выбранный для просмотра документ Электронный задачник.pptx

библиотека
материалов
Задача «Об играх» В первенстве класса по настольному теннису 6 участников: Ан...
Задача «Распределение ролей» В школьном драматическом кружке решили ставить г...
Задача «Подарки» Купленные в подарок игрушки (пистолет, сумочку, куклу и маши...
Решение Выделяем группу объектов (участники) – вершины графа (группа выделена...
Решение Выделяем отношения между объектами (проведенные игры выделены цветом:...
Решение Устанавливаем отношения, читая условия задачи – изображаем граф. Андр...
Решение Андрей Виктор Дмитрий Елена Галина Устанавливаем не проведенные игры,...
Решение Выделяем группу объектов (участники) – вершины графа (группа выделена...
Решение Выделяем вторую группу объектов – роли. В школьном драматическом круж...
Решение Устанавливаем отношения, читая условия задачи – изображаем граф. Дима...
Решение Выделяем группу объектов (игрушки и коробки) – вершины графа (группа...
Решение 2. Устанавливаем отношения, читая условия задачи – изображаем граф. П...
Решение Выделяем группу объектов (ученики и сектора) – вершины графа (группа...
Решение 2. Устанавливаем отношения, читая условия задачи – изображаем граф. В...
17 1

"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs

Описание презентации по отдельным слайдам:

№ слайда 1 Задача «Об играх» В первенстве класса по настольному теннису 6 участников: Ан
Описание слайда:

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

№ слайда 2 Задача «Распределение ролей» В школьном драматическом кружке решили ставить г
Описание слайда:

Задача «Распределение ролей» В школьном драматическом кружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Началось все с Ляпкина–Тяпкина. - Ляпкиным–Тяпкиным буду я! – решительно заявил Дима. – С раннего детства я мечтал воплотить этот образ на сцене. - Ну хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена. - ...А мне Осипа, - не уступил в великодушие Дима. - Хочу быть Земляникой или Городничим, - сказал Вова. - Нет, Городничим буду я, - хором закричали Алик и Боря. – Или Хлестаковым, - добавили они одновременно. Удастся ли распределить роли так, чтобы исполнители были довольны?

№ слайда 3 Задача «Подарки» Купленные в подарок игрушки (пистолет, сумочку, куклу и маши
Описание слайда:

Задача «Подарки» Купленные в подарок игрушки (пистолет, сумочку, куклу и машину) уложили в четыре коробки, по одной игрушке в каждую. Требуется узнать, что положено в каждую коробку, если известно следующее: машинка и пистолет не в красной коробке; коробка с сумочкой находится между синей коробкой и коробкой с куклой; в зеленой коробке не сумочка и не машинка; желтая и зеленая коробки находятся около коробки с пистолетом.

№ слайда 4 Решение Выделяем группу объектов (участники) – вершины графа (группа выделена
Описание слайда:

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

№ слайда 5 Решение Выделяем отношения между объектами (проведенные игры выделены цветом:
Описание слайда:

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

№ слайда 6 Решение Устанавливаем отношения, читая условия задачи – изображаем граф. Андр
Описание слайда:

Решение Устанавливаем отношения, читая условия задачи – изображаем граф. Андрей Борис Галина Елена Виктор Дмитрий Подсчитываем количество ребер. Количество ребер = 7. Получаем, что на данный момент проведено 7 игр.

№ слайда 7 Решение Андрей Виктор Дмитрий Елена Галина Устанавливаем не проведенные игры,
Описание слайда:

Решение Андрей Виктор Дмитрий Елена Галина Устанавливаем не проведенные игры, данные отношения – ребра будем показывать штриховой линией, т. к. эти отношения неконкретные. Количество ребер = 8. Борис Значит еще осталось провести 8 игр.

№ слайда 8 Решение Выделяем группу объектов (участники) – вершины графа (группа выделена
Описание слайда:

Решение Выделяем группу объектов (участники) – вершины графа (группа выделена красным цветом). В школьном драматическом кружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Началось все с Ляпкина–Тяпкина. - Ляпкиным–Тяпкиным буду я! – решительно заявил Дима. – С раннего детства я мечтал воплотить этот образ на сцене. - Ну хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена. - ...А мне Осипа, - не уступил в великодушие Дима. - Хочу быть Земляникой или Городничим, - сказал Вова. - Нет, Городничим буду я, - хором закричали Алик и Боря. – Или Хлестаковым, - добавили они одновременно. Удастся ли распределить роли так, чтобы исполнители были довольны?

№ слайда 9 Решение Выделяем вторую группу объектов – роли. В школьном драматическом круж
Описание слайда:

Решение Выделяем вторую группу объектов – роли. В школьном драматическом кружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Началось все с Ляпкина–Тяпкина. - Ляпкиным–Тяпкиным буду я! – решительно заявил Дима. – С раннего детства я мечтал воплотить этот образ на сцене. - Ну хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена. - ...А мне Осипа, - не уступил в великодушие Дима. - Хочу быть Земляникой или Городничим, - сказал Вова. - Нет, Городничим буду я, - хором закричали Алик и Боря. – Или Хлестаковым, - добавили они одновременно. Удастся ли распределить роли так, чтобы исполнители были довольны?

№ слайда 10 Решение Устанавливаем отношения, читая условия задачи – изображаем граф. Дима
Описание слайда:

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

№ слайда 11 Решение Выделяем группу объектов (игрушки и коробки) – вершины графа (группа
Описание слайда:

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

№ слайда 12 Решение 2. Устанавливаем отношения, читая условия задачи – изображаем граф. П
Описание слайда:

Решение 2. Устанавливаем отношения, читая условия задачи – изображаем граф. Пистолет Сумочка Кукла Машина Красная Синяя Зеленая Желтая Ответ: пистолет – в синей, сумочка – в красной, кукла – в зеленой, машинка – в желтой коробках.

№ слайда 13 Решение Выделяем группу объектов (ученики и сектора) – вершины графа (группа
Описание слайда:

Решение Выделяем группу объектов (ученики и сектора) – вершины графа (группа выделена красным цветом и фиолетовым). Четыре одноклассника – Володя, Толя, Оля и Сережа выбраны классным собранием для работы в шефском, культурно-массовом, спортивном и учебном секторах школы. Определите, кого из ребят, в какой из названных секторов выбрали, если известно, что: Володя и член культсектора живут в одном доме, и они вместе с Олей втроем ездят в школу на автобусе; На классном собрании, было решено, в спортсектор избрать мальчика; Член учебного сектора и Сережа вместе ходят на теннисный корт; Член спортсектора и Володя – большие друзья; Оля сидит за одной партой с членом учебного сектора.

№ слайда 14 Решение 2. Устанавливаем отношения, читая условия задачи – изображаем граф. В
Описание слайда:

Решение 2. Устанавливаем отношения, читая условия задачи – изображаем граф. Володя Толя Оля Сережа Шефский Культурный Спортивный Учебный Ответ: Оля – шефский сектор, Володя – учебный сектор, Толя – культмассовый, Сережа – спортивный сектор.

№ слайда 15
Описание слайда:

№ слайда 16
Описание слайда:

№ слайда 17
Описание слайда:

Выбранный для просмотра документ оглавление.docx

библиотека
материалов

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ 3

ГЛАВА 1 ИСТОРИЧЕСКИЕ И ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ О ГРАФЕ 4

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

1.2. Теоретические сведения о графе 5

ГЛАВА 2 ТИПЫ ЗАДАЧ, РЕШАЕМЫХ С ПОМОЩЬЮ ГРАФА 5

2. 1. Задачи на вычерчивание фигур одним росчерком 6

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

ГЛАВА 3 РЕШЕНИЕ ОЛИМПИАДНЫХ ЗАДАЧ, С ПОМОЩЬЮ ГРАФА. ЛОГИЧЕСКИЕ ЗАДАЧИ 8

ЗАКЛЮЧЕНИЕ 14

СПИСОК ЛИТЕРАТУРЫ 15

ПРИЛОЖЕНИЕ (диск) 16









Краткое описание документа:

Цель работы: изучение метода графов и применение его при решении олимпиадных задач.

Задачи:

1.      Проанализировать математическую и методическую литературу по теме «Графы».

2.      Рассмотреть основные типы задач, решаемых с помощью графов.

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

4.      Создать электронный задачник «Решение олимпиадных задач с помощью графов».

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

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

Методы исследования: поисковый метод, исследовательский метод, практический метод.

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

 

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

Автор
Дата добавления 13.01.2015
Раздел Математика
Подраздел Другие методич. материалы
Просмотров2066
Номер материала 294265
Получить свидетельство о публикации

Идёт приём заявок на международный конкурс по математике "Весенний марафон" для учеников 1-11 классов и дошкольников

Уникальность конкурса в преимуществах для учителей и учеников:

1. Задания подходят для учеников с любым уровнем знаний;
2. Бесплатные наградные документы для учителей;
3. Невероятно низкий орг.взнос - всего 38 рублей;
4. Публикация рейтинга классов по итогам конкурса;
и многое другое...

Подайте заявку сейчас - https://urokimatematiki.ru


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ


"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs

Похожие материалы

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