1556245
столько раз учителя, ученики и родители
посетили официальный сайт проекта «Инфоурок»
за прошедшие 24 часа
Добавить материал и получить бесплатное
свидетельство о публикации
в СМИ №ФС77-60625 от 20.01.2015
Инфоурок Математика ПрезентацииПрезентация Теория графов конференция

Презентация Теория графов конференция

IV Международный дистанционный конкурс «Старт» Идёт приём заявок Для дошкольников и учеников 1-11 классов 16 предметов ОРГВЗНОС 25 Р. ПОДАТЬ ЗАЯВКУ
библиотека
материалов
ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ ПРИ РЕШЕНИИ ЗАДАЧ

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

1 слайд ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ ПРИ РЕШЕНИИ ЗАДАЧ
Описание слайда:

ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ ПРИ РЕШЕНИИ ЗАДАЧ

2 слайд «На одном далеком острове живут два племени: рыцарей (которые всегда говорят
Описание слайда:

«На одном далеком острове живут два племени: рыцарей (которые всегда говорят правду) и плутов (которые всегда лгут). Один мудрец-путешественник рассказал такую историю. «Приплыв на остров, я встретил двух местных жителей и захотел узнать, из какого они племени. Я спросил первого: «Вы оба рыцари?». Не помню, ответил он «да» или «нет», но по его ответу я не смог однозначно определить кто из них кто. Тогда я спросил у того же жителя: «Вы из одного племени?». Опять-таки, не помню, ответил он «да» или «нет», но после этого ответа я сразу догадался, кто из них кто». Кого же встретил мудрец?» ЗАДАЧА олимпиада - 2012

3 слайд Цель исследования: -рассмотреть возможности применения графового аппарата дл
Описание слайда:

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

4 слайд Актуальность исследования: Графы используют во всех отраслях нашей жизни. Зна
Описание слайда:

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

5 слайд Схема Московского метрополитена ПРИМЕРЫ ГРАФОВ Схема авиалиний Изображение ге
Описание слайда:

Схема Московского метрополитена ПРИМЕРЫ ГРАФОВ Схема авиалиний Изображение генеалогического древа Изображение созвездий

6 слайд Слово «граф» в математике означает картинку, где нарисовано несколько точек,
Описание слайда:

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

7 слайд В 1736 г Леонард Эйлер формулирует и предлагает решение задачи о семи кёнигсб
Описание слайда:

В 1736 г Леонард Эйлер формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. «Мне была предложена задача об острове, расположенном в городе Кёнигсберге и окружённом рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто – нибудь непрерывно обойти их, проходя только однажды через каждый мост…» (Из письма Л. Эйлера итальянскому математику и инженеру Маринони от 13 марта 1736 года) Леонард Эйлер (1707 – 1783) История возникновения теории графов

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

Решая задачу про Кенигсбергские мосты, Эйлер установил следующие свойства графа: 1. Если все вершины графа чётные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. 2. Граф с двумя нечётными вершинами тоже можно начертить одним росчерком. Движение нужно начинать от любой нечётной вершины, а заканчивать на другой нечётной вершине. 3. Граф с более чем двумя нечётными вершинами, невозможно начертить одним росчерком.

9 слайд Вильям Роуэн Гамильтон (1805 – 1865) Знаменитый ирландский математик, Создате
Описание слайда:

Вильям Роуэн Гамильтон (1805 – 1865) Знаменитый ирландский математик, Создатель детской головоломки. Замкнутый путь по ребрам графа , проходящий по одному разу через все вершины, называется гамильтоновым циклом.

10 слайд полный граф «домики- колодцы» Задача Льюиса Кэррола: Люди жили в трех домиках
Описание слайда:

полный граф «домики- колодцы» Задача Льюиса Кэррола: Люди жили в трех домиках, неподалеку от них находились три колодца: один с соленой водой, второй- со сладкой , третий – с пресной , и ходили к ним по тропинкам. Однажды эти люди перессорились и решили по-новому провести тропинки от своих домов к колодцам так, чтобы эти тропинки не пересекались. Как это сделать?

11 слайд Еще одна из задач Льюиса Кэрролла, автора книги «Алиса в стране чудес»
Описание слайда:

Еще одна из задач Льюиса Кэрролла, автора книги «Алиса в стране чудес»

12 слайд «Задача о бродячем торговце» или «Задача о коммивояжере» «Жадный» алгоритм –
Описание слайда:

«Задача о бродячем торговце» или «Задача о коммивояжере» «Жадный» алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. 1 3 2 4

13 слайд Определение. Число рёбер, выходящих из одной вершины, называют степенью этой
Описание слайда:

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

14 слайд 2. Определение. Если степень вершины чётная, то вершина называется чётной, ес
Описание слайда:

2. Определение. Если степень вершины чётная, то вершина называется чётной, если степень не чётная, то вершина нечётная. Лемма 3. Число нечётных вершин графа чётно. Доказательство. Если в графе есть n чётных и k нечётных вершин, то сумма степеней чётных вершин чётна. Сумма степеней нечётных вершин нечётна, если количество этих вершин нечётна. Но тогда общее число степеней вершин тоже нечётна, чего не может быть. Значит, k чётно.  

15 слайд Наиболее близки к графам – топология и комбинаторика.
Описание слайда:

Наиболее близки к графам – топология и комбинаторика.

16 слайд Задача 1. В 10-значном числе каждые две подряд идущие цифры образуют двузначн
Описание слайда:

Задача 1. В 10-значном числе каждые две подряд идущие цифры образуют двузначное число, которое делится на 13. Докажите, что среди этих цифр нет цифры 8. Решение. Существует 7 двузначных чисел, которые делятся на 13. Обозначим эти числа точками и применим определение графа. По условию каждые 2 подряд идущие цифры образуют двузначное число, которые делятся на 13, значит цифры, из которых состоит 10-значное число, повторяются. Соединим вершины графа рёбрами так, чтобы цифры, входящие в этот граф повторялись. 13 39 65 78 52 91 26

17 слайд Решение: А Б Г В Задача №2 Андрей, Борис, Виктор и Григорий играли в шахматы.
Описание слайда:

Решение: А Б Г В Задача №2 Андрей, Борис, Виктор и Григорий играли в шахматы. Каждый сыграл с каждым по одной партии. Сколько партий было сыграно? 6 партий

18 слайд Задача № 4. Поступающий на физмат должен сдать три вступительных экзамена по
Описание слайда:

Задача № 4. Поступающий на физмат должен сдать три вступительных экзамена по десятибалльной системе. Сколькими способами он может сдать экзамены, чтобы быть принятым в университет, если проходной балл в тот год составил 28 баллов? Решение. Для решения этой задачи, как и во многих других комбинаторных и вероятностных задачах, эффективным оказывается организация элементов анализируемого множества в виде дерева. От одной выделенной вершины проводятся ребра, соответствующие оценке на первом экзамене, а затем к их концам добавляются новые ребра, соответствующие возможным результатам второго экзамена, а затем и третьего. Таким образом, для поступления на физмат можно сдать вступительные экзамены 10 различными способами.

19 слайд Задача № 5. На одном далеком острове живут два племени: рыцарей (которые все
Описание слайда:

Задача № 5. На одном далеком острове живут два племени: рыцарей (которые всегда говорят правду) и плутов (которые всегда лгут). Один мудрец-путешественник рассказал такую историю. «Приплыв на остров, я встретил двух местных жителей и захотел узнать, из какого они племени. Я спросил первого: «Вы оба рыцари?». Не помню, ответил он «да» или «нет», но по его ответу я не смог однозначно определить кто из них кто. Тогда я спросил у того же жителя: «Вы из одного племени?». Опять-таки, не помню, ответил он «да» или «нет», но после этого ответа я сразу догадался, кто из них кто». Кого же встретил мудрец?» Решение: Р Р Р П П П Да Да Нет Да Да Да Да Да Да Нет Нет

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

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

Курс профессиональной переподготовки
Учитель математики
Найдите материал к любому уроку,
указав свой предмет (категорию), класс, учебник и тему:
также Вы можете выбрать тип материала:
Краткое описание документа:

Презентация создана для представления проектно-исследовательской работы "Теория графов". 

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

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

 

 

 

Общая информация
ВНИМАНИЮ УЧИТЕЛЕЙ: хотите организовать и вести кружок по ментальной арифметике в своей школе? Спрос на данную методику постоянно растёт, а Вам для её освоения достаточно будет пройти один курс повышения квалификации (72 часа) прямо в Вашем личном кабинете на сайте "Инфоурок".

Пройдя курс Вы получите:
- Удостоверение о повышении квалификации;
- Подробный план уроков (150 стр.);
- Задачник для обучающихся (83 стр.);
- Вводную тетрадь «Знакомство со счетами и правилами»;
- БЕСПЛАТНЫЙ доступ к CRM-системе, Личному кабинету для проведения занятий;
- Возможность дополнительного источника дохода (до 60.000 руб. в месяц)!

Пройдите дистанционный курс «Ментальная арифметика» на проекте "Инфоурок"!

Подать заявку
IV Международный дистанционный конкурс «Старт» Для дошкольников и учеников 1-11 классов Рекордно низкий оргвзнос 25 Р. 16 предметов ПОДАТЬ ЗАЯВКУ
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.