Инфоурок / Математика / Презентации / Презентация Теория графов конференция

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

Напоминаем, что в соответствии с профстандартом педагога (утверждён Приказом Минтруда России), если у Вас нет соответствующего преподаваемому предмету образования, то Вам необходимо пройти профессиональную переподготовку по профилю педагогической деятельности. Сделать это Вы можете дистанционно на сайте проекта "Инфоурок" и получить диплом с присвоением квалификации уже через 2 месяца!

Только сейчас действует СКИДКА 50% для всех педагогов на все 111 курсов профессиональной переподготовки! Доступна рассрочка с первым взносом всего 10%, при этом цена курса не увеличивается из-за использования рассрочки!

ВЫБРАТЬ КУРС И ПОДАТЬ ЗАЯВКУ
библиотека
материалов
ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ ПРИ РЕШЕНИИ ЗАДАЧ
«На одном далеком острове живут два племени: рыцарей (которые всегда говорят...
Цель исследования: -рассмотреть возможности применения графового аппарата дл...
Актуальность исследования: Графы используют во всех отраслях нашей жизни. Зна...
Схема Московского метрополитена ПРИМЕРЫ ГРАФОВ Схема авиалиний Изображение ге...
Слово «граф» в математике означает картинку, где нарисовано несколько точек,...
В 1736 г Леонард Эйлер формулирует и предлагает решение задачи о семи кёнигсб...
Решая задачу про Кенигсбергские мосты, Эйлер установил следующие свойства гра...
Вильям Роуэн Гамильтон (1805 – 1865) Знаменитый ирландский математик, Создате...
полный граф «домики- колодцы» Задача Льюиса Кэррола: Люди жили в трех домиках...
Еще одна из задач Льюиса Кэрролла, автора книги «Алиса в стране чудес»
«Задача о бродячем торговце» или «Задача о коммивояжере» «Жадный» алгоритм –...
Определение. Число рёбер, выходящих из одной вершины, называют степенью этой...
2. Определение. Если степень вершины чётная, то вершина называется чётной, ес...
Наиболее близки к графам – топология и комбинаторика.
Задача 1. В 10-значном числе каждые две подряд идущие цифры образуют двузначн...
Решение: А Б Г В Задача №2 Андрей, Борис, Виктор и Григорий играли в шахматы....
Задача № 4. Поступающий на физмат должен сдать три вступительных экзамена по...
Задача № 5. На одном далеком острове живут два племени: рыцарей (которые все...
С помощью графов можно гораздо легче решать логические задачи, составлять ген...
20 1

УЖЕ ЧЕРЕЗ 10 МИНУТ ВЫ МОЖЕТЕ ПОЛУЧИТЬ ДИПЛОМ

от проекта "Инфоурок" с указанием данных образовательной лицензии, что важно при прохождении аттестации.


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


Список всех тестов можно посмотреть тут - https://infourok.ru/tests

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

№ слайда 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 С помощью графов можно гораздо легче решать логические задачи, составлять ген
Описание слайда:

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

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

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

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

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

 

 

 

Общая информация

Номер материала: 375468

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