Рабочие листы
к вашим урокам
Скачать
1 слайд
ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ
ПРИ РЕШЕНИИ ЗАДАЧ
2 слайд
«На одном далеком острове живут два племени: рыцарей (которые всегда говорят правду) и плутов (которые всегда лгут). Один мудрец-путешественник рассказал такую историю. «Приплыв на остров, я встретил двух местных жителей и захотел узнать, из какого они племени. Я спросил первого: «Вы оба рыцари?». Не помню, ответил он «да» или «нет», но по его ответу я не смог однозначно определить кто из них кто. Тогда я спросил у того же жителя: «Вы из одного племени?». Опять-таки, не помню, ответил он «да» или «нет», но после этого ответа я сразу догадался, кто из них кто». Кого же встретил мудрец?»
ЗАДАЧА
олимпиада - 2012
3 слайд
Цель исследования:
-рассмотреть возможности применения графового аппарата для решения логических и комбинаторных задач.
Задачи исследования:
рассмотреть решение задач при помощи графов;
научиться переводить задачи на язык графов;
сравнить традиционные методы решения задач с методами теории графов.
4 слайд
Актуальность исследования:
Графы используют во всех отраслях нашей жизни. Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом (например, сетевой график строительства, графики доставки почты), построении путей транспортировки и доставки, решении задач. Графы используют в связи с развитием теории вероятностей, математической логики и информационных технологий.
Гипотеза:
Использование теории графов делает решение многих логических и комбинаторных задач менее трудоемким.
5 слайд
Схема Московского
метрополитена
ПРИМЕРЫ ГРАФОВ
Схема авиалиний
Изображение генеалогического древа
Изображение созвездий
6 слайд
Слово «граф» в математике означает картинку,
где нарисовано несколько точек, некоторые из которых соединены линиями.
При изображении графа не имеет значения расположение вершин на плоскости, кривизна и длина ребер.
Вершины графов обозначаются буквами или натуральными числами.
Ребра графа – пары чисел.
7 слайд
В 1736 г Леонард Эйлер формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.
«Мне была предложена задача об острове, расположенном в городе Кёнигсберге и окружённом рекой,
через которую перекинуто 7 мостов. Спрашивается, может ли
кто – нибудь непрерывно обойти их, проходя только однажды
через каждый мост…»
(Из письма Л. Эйлера итальянскому математику и инженеру
Маринони от 13 марта 1736 года)
Леонард Эйлер
(1707 – 1783)
История возникновения теории графов
8 слайд
Решая задачу про Кенигсбергские мосты,
Эйлер установил следующие свойства графа:
1. Если все вершины графа чётные, то можно одним росчерком
(т.е. не отрывая карандаша от бумаги и не проводя дважды
по одной и той же линии) начертить граф.
2. Граф с двумя нечётными вершинами тоже можно начертить
одним росчерком. Движение нужно начинать от любой
нечётной вершины, а заканчивать на другой нечётной вершине.
3. Граф с более чем двумя нечётными вершинами, невозможно
начертить одним росчерком.
9 слайд
Вильям Роуэн Гамильтон
(1805 – 1865)
Знаменитый ирландский математик,
Создатель детской головоломки.
Замкнутый путь по ребрам графа , проходящий по одному разу через все вершины, называется гамильтоновым циклом.
10 слайд
полный граф
«домики- колодцы»
Задача Льюиса Кэррола:
Люди жили в трех домиках, неподалеку от них находились три колодца: один с соленой водой, второй- со сладкой , третий – с пресной , и ходили к ним по тропинкам. Однажды эти люди перессорились и решили по-новому провести тропинки от своих домов к колодцам так, чтобы эти тропинки не пересекались. Как это сделать?
11 слайд
Еще одна из задач Льюиса Кэрролла,
автора книги «Алиса в стране чудес»
12 слайд
«Задача о бродячем торговце»
или
«Задача о коммивояжере»
«Жадный» алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами.
1
3
2
4
13 слайд
Определение. Число рёбер, выходящих из одной вершины,
называют степенью этой вершины.
Лемма 1. Число рёбер в графе ровно в 2 раза меньше, чем сумма
степеней вершин.
Доказательство. Любое ребро графа связывают 2 вершины. Значит,
если будем складывать число степеней всех вершин графа, то получим
удвоенное число рёбер, т.к. каждое ребро было подсчитано дважды.
Лемма 2. Сумма степеней вершин графа чётна.
Доказательство. По лемме1 число рёбер в графе в 2 раза меньше
суммы степеней вершин, значит сумма степеней вершин
чётна (делится на 2).
14 слайд
2. Определение. Если степень вершины чётная, то вершина называется чётной, если степень не чётная, то вершина нечётная.
Лемма 3. Число нечётных вершин графа чётно.
Доказательство. Если в графе есть n чётных и k нечётных вершин, то сумма степеней чётных вершин чётна. Сумма степеней нечётных вершин нечётна, если количество этих вершин нечётна. Но тогда общее число степеней вершин тоже нечётна, чего не может быть. Значит, k чётно.
15 слайд
Наиболее близки к графам – топология и комбинаторика.
16 слайд
Задача 1. В 10-значном числе каждые две подряд идущие цифры
образуют двузначное число, которое делится на 13. Докажите,
что среди этих цифр нет цифры 8.
Решение. Существует 7 двузначных чисел, которые делятся на 13.
Обозначим эти числа точками и применим определение графа.
По условию каждые 2 подряд идущие цифры образуют двузначное число, которые делятся на 13, значит цифры, из которых состоит 10-значное число, повторяются. Соединим вершины графа рёбрами так, чтобы цифры, входящие в этот граф повторялись.
13
39
65
78
52
91
26
17 слайд
Решение:
А
Б
Г
В
Задача №2
Андрей, Борис, Виктор и Григорий играли в шахматы. Каждый сыграл с каждым по одной партии. Сколько партий было сыграно?
6 партий
18 слайд
Задача № 4. Поступающий на физмат должен сдать три вступительных экзамена по десятибалльной системе. Сколькими способами он может сдать экзамены, чтобы быть принятым в университет, если проходной балл в тот год составил 28 баллов?
Решение.
Для решения этой задачи, как и во многих других комбинаторных и вероятностных задачах, эффективным оказывается организация элементов анализируемого множества в виде дерева. От одной выделенной вершины проводятся ребра, соответствующие оценке на первом экзамене, а затем к их концам добавляются новые ребра, соответствующие возможным результатам второго экзамена, а затем и третьего. Таким образом, для поступления на физмат можно сдать вступительные экзамены 10 различными способами.
19 слайд
Задача № 5. На одном далеком острове живут два племени: рыцарей (которые всегда говорят правду) и плутов (которые всегда лгут). Один мудрец-путешественник рассказал такую историю. «Приплыв на остров, я встретил двух местных жителей и захотел узнать, из какого они племени. Я спросил первого: «Вы оба рыцари?». Не помню, ответил он «да» или «нет», но по его ответу я не смог однозначно определить кто из них кто. Тогда я спросил у того же жителя: «Вы из одного племени?». Опять-таки, не помню, ответил он «да» или «нет», но после этого ответа я сразу догадался, кто из них кто». Кого же встретил мудрец?»
Решение:
Р
Р
Р
П
П
П
Да Да Нет Да Да Да
Да Да Да Нет Нет
20 слайд
С помощью графов можно гораздо легче решать логические задачи, составлять генеалогические древа, решать задачи, связанные с теорией игр, задачи предлагаемые на олимпиадах.
На языке теории графов формируются и решаются не только математические, но и технические задачи, задачи из области экономики, социологии, менеджмента и других областей.
Рабочие листы
к вашим урокам
Скачать
Презентация создана для представления проектно-исследовательской работы "Теория графов".
В настоящей работе рассмотрены математические графы, области их применения, представлены решения логических и комбинаторных задач с помощью графов.
По своему содержанию, логике изложения, полученным результатам и их соответствию поставленной цели работа носит исследовательский характер. Она является актуальной, интересной, содержание превышает уровень учебной программы по математике,освещает малоизвестные факты и события. В презентации показано, как с одной стороны, графы помогают проследить все логические возможности изучаемой ситуации, с другой, благодаря своей обозримости, помогают тут же, в ходе решения задачи, классифицировать логические возможности, отбрасывать неподходящие случаи, не доводя до полного перебора всех случаев.
6 665 090 материалов в базе
Настоящий материал опубликован пользователем Корыпаева Антонина Юрьевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс повышения квалификации
72 ч. — 180 ч.
Курс повышения квалификации
36 ч. — 144 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Мини-курс
10 ч.
Мини-курс
5 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.