Выбранный для просмотра документ Решение логических задач с помощью графов.docx
Скачать материал "Проект Решение логических задач с помощью графов"
Рабочие листы
к вашим урокам
Скачать
Выбранный для просмотра документ Решение логических задач с помощью графов.pptx
Скачать материал "Проект Решение логических задач с помощью графов"
Рабочие листы
к вашим урокам
Скачать
1 слайд
Решение логических задач с помощью графов
Учебный проект по математике
учеников 7 «Б» класса
2 слайд
Что такое граф в математике.
Графом в математике называется конечная совокупность точек, именуемых вершинами; некоторые из них соединены друг с другом линиями, называемыми ребрами графа.
3 слайд
Пример из медицины
II
III
IV
I
Известно, что у разных людей кровь отличается по группе.
Существуют четыре группы крови. Оказывается, что при переливании крови от одного человека к другому не все группы совместимы.
Граф показывает возможные варианты переливания крови. Группы крови – это вершины графов с соответствующими номерами, а стрелки указывают на возможность переливания одной группы крови человеку с другой группой крови.
Из графа видно, что кровь 1-й группы можно переливать любому человеку, а человек с 1-й группой крови воспринимает кровь только своей группы.
Видно также, что человеку с 4-й группой крови можно переливать любую, но его собственную кровь можно переливать только в ту же группу.
4 слайд
Пример из астрономии
В темную, безлунную и безоблачную ночь на небе видно множество звезд. Кажется, трудно разобраться в этой величественной картине звездного неба, о которой вдохновенно писал наш великий соотечественник М. В. Ломоносов (1711—1765):
«Открылась бездна звезд полна,
Звездам числа нет, бездне — дна».
Но как же можно ориентироваться по звездам, если их видно на небе великое множество? Казалось бы, легко запутаться в этом обилии звезд. Вот для этого и нужно было, прежде всего, сгруппировать яркие звезды (которых на небе не так уже много) в фигуры, хорошо запоминающиеся своими контурами.
5 слайд
Известные созвездия
6 слайд
Генеалогическое дерево
7 слайд
Московское метро
8 слайд
Впервые основы теории графов появились в работе Леонарда Эйлера, где он описывал решения головоломок и математических развлекательных задач.
Широкое развитие теория графов получила с 50-х гг. ХХ в. в связи со становлением кибернетики и развитием вычислительной техники.
9 слайд
Если поставить проволочный додекаэдр на плоскость, а затем поднести источник света близко к центру его верхней грани, то проекции-тени ребер на плоскость составляет граф. Аналогичным образом можно получить плоские графы для остальных 4 правильных многогранников.
Графы изоморфные и плоские
10 слайд
Мы провели такой опыт с многогранниками, которые изготовили самостоятельно.
11 слайд
А всегда ли граф можно изобразить на плоскости так, чтобы его рёбра не пересекались? Оказывается, нет. Графы, для которых это возможно, называются плоскими.
Для плоских графов справедлива формула Эйлера:
В–Р+Г=2.
Проверим эту зависимость для сделанных нами многогранников: икосаэдра и додекаэдра.
Для икосаэдра: В = 12; Р = 25; Г = 15; 12 – 25 + 15 = 2.
Для додекаэдра: В = 20; Р = 30; Г = 12; 20 – 30 + 12 = 2.
12 слайд
«В трех избушках жили трое друзей. Около их домиков находилось три колодца: один с соленой водой, второй – со сладкой, третий – с пресной. Но однажды друзья поссорились, да так, что и видеть друг друга не хотели. И решили они по-новому проложить тропинки от домов к колодцам, чтобы их пути не пересекались. Как это сделать?»
Рассмотрим два графа, которые «не укладываются» на плоскость без пересечения рёбер. Первый из них – граф с пятью вершинами, каждые две из которых соединены ребром. Такой граф называется полным.
Второй граф, с шестью вершинами и девятью рёбрами, носит название «домики – колодцы». Оно произошло от старинной задачи – головоломки.
13 слайд
14 слайд
Задача 1
Задача туриста.
(Автор: бгатцев алексей)
Составь туристический маршрут , посетив города: Варшава, Берлин, Париж, Лондон, начиная свой путь из Москвы.
Выбери самый короткий путь, если расстояние :
от Москвы до Варшавы – 1100 км,
от Москвы до Берлина – 1600 км,
от Москвы до Парижа – 2500 км,
от Москвы до Лондона – 2500км,
от Варшавы до Берлина – 500км,
от Варшавы до Парижа – 1300км,
от Варшавы до Лондона – 1500км ,
от Берлина до Парижа – 900км,
от Берлина до Лондона – 900км,
от Парижа до Лондона – 300км.
Сколько вариантов маршрутов может быть?
15 слайд
Решение
В
Москва
Варшава
Берлин
Париж
Лондон
Б
П
Л
В
П
Л
В
Б
Л
В
Б
П
Варшава
П
Л
Б
Л
Б
П
П
Л
В
Л
В
П
Б
Л
В
Л
Б
Б
П
В
П
В
Б
Л
П
Л
Б
П
Б
Л
П
Л
В
П
В
Л
Б
Л
В
Б
В
П
Б
П
В
Б
В
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
М
16 слайд
Решение
17 слайд
решение
18 слайд
РЕШЕНИЕ
Ответ: самый короткий путь Москва-
Берлин-Варшава-Париж-Лондон-Москва
Его длина 4200 км и 24 варианта маршрутов.
19 слайд
Задача 2
О рейсах самолетов
(Автор: Гончаревич Настя)
В связи с плохой погодой задерживаются четыре рейса самолетов – в Варшаву, Лондон, Париж и Берлин. Командиры самолетов высказали пожелания, чтобы рейс в Варшаву был первым или вторым, В Лондон – вторым или третьим, в Париж – третьим или четвертым, а в Берлин – первым или четвертым.
Можно ли удовлетворить пожеланиям летчиков? Если да, то перечислите возможные варианты вылетов.
Варшава
Берлин
Париж
Лондон
20 слайд
Решение
Москва
Лондон
Париж
Берлин
Варшава
Ответ: возможно 2 варианта.
1)первый рейс – в Варшаву, второй – в Лондон, третий – в Париж, четвертый – в Берлин.
2)первый рейс – в Берлин, второй – в Варшаву, третий – в Лондон, четвертый – в Париж.
21 слайд
Задача 3
«Расписание уроков»
(Автор: Азибекян Арен)
Для учащихся 7 “б” класса нужно составить расписание уроков на понедельник. Должны быть такие предметы: 2 урока математики, по 1 уроку русского языка, истории, биологии и географии. Учитель математики высказал пожелание, чтобы ее уроки были 1 и 3. Учителя русского языка и истории согласны заниматься с учащимися на 2 или 4 уроках. Учителя биологии и географии – на 5 или 6.
Сколько вариантов расписания можно составить?
22 слайд
Варианты для каждого урока
2
1
3
4
5
6
Математика
Русский язык
История
Математика
Русский язык
История
Биология
География
Биология
География
23 слайд
Можно составить 16 вариантов расписания. Вот некоторые из них:
1. Математика
Русский язык
Математика
История
Биология
География
1. Математика
История
Математика
Русский язык
Биология
География
1. Математика
Русский язык
Математика
История
География
Биология
24 слайд
Задача 4
«Школьное меню»
(Автор: Демидова Ксения )
В школьной столовой на первое можно заказать борщ, щи, рыбный или гороховый суп , на второе – ёжика , рыбу или котлету , а на третье - сок , чай или компот .
Сколько вариантов обеда можно получить из указанных блюд ?
25 слайд
Решение
Борщ
Щи
Рыбный суп
Гороховый суп
Ёжик
Рыба
Котлета
Меню
Сок
Чай
Компот
26 слайд
Всего 36 вариантов меню.
Щи
Котлета
Сок
Борщ
Рыба
Чай
Рыбный Суп
Ёжик
Компот
Борщ
Ёжик
Компот
27 слайд
1
2
3
4
5
6
7
Спас
Радиорынок
Школа
1062
Макдональдс
К/т Люксор
Культурный центр
Бассейн «Жемчужина»
Задача о Митино
На карте нашего района Митино обозначены пункты, которые чаще всего посещаются учениками нашей школы.
Предположим, что принято решение о посадке деревьев и кустарников вдоль дорог, соединяющих указанные объекты. Стоимость озеленения каждого участка зависит от его длины. Требуется найти самый дешевый вариант реализации плана озеленения.
Используем, так называемый «жадный алгоритм».
Задача 5
28 слайд
1
2
3
4
5
6
7
Спас
Радиорынок
Школа
1062
Макдональдс
К/т Люксор
Культурный центр
Бассейн «Жемчужина»
Решение
Учтем, что стоимость озеленения пропорциональна длине пути между двумя пунктами. Расстояния между объектами укажем в см (измерено по карте).
5-6 5-4 5-3 3-2 2-1 6-7 – этапы озеленения
Таким образом, можно будет обойти все обозначенные на карте объекты, каждый раз проходя по аллеям.
29 слайд
Два игрока играют в следующую игру.
Перед ними лежат 2 кучки камней,
в 1-й из которых 4, а во 2-й – 3 камня.
У каждого игрока неограниченно много камней.
Игроки ходят по очереди.
Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то кучке, или добавляет 3 камня в какую-то кучку.
Выигрывает игрок, после хода которого в одной из кучек становится не менее 24 камней.
1) Кто выигрывает при безошибочной игре: игрок, делающий 1-й ход, или игрок, делающий 2-й ход?
2) Каким Должен быть 1-й ход выигрывающего игрока?
ЕГЭ
30 слайд
Для
решения
задачи
1
4;3
12;3
4;6
7;3
4;9
36;3
7;6
7;18
7;6
4;27
21;6
7;18
7;54
21;6
63;6
63;6
7;54
2
3
4
Исходные числа.
Все ходы, которые может
сделать первый игрок.
Все безошибочные ходы второго игрока. При 1и3
вариантах игрок выигрывает,
а при 2 и 4 игрок прибавляет 3 к меньшему числу.
Все ходы которые может сделать первый игрок.
Все безошибочные ходы второго игрока, они же выигрывающие.
Ответ: выигрывает второй игрок.
составим
граф
31 слайд
Цепочка из трех бусин формируется по следующему правилу.
На 3-м месте в цепочке стоит одна из бусин А, В, Г. На 2-м месте – одна из бусин А, Б, В. На 1-м месте – одна из бусин Б, В, Г, не стоящая в цепочке на втором или третьем месте.
Сколько существует различных цепочек, соответствующих этому правилу.
ЕГЭ
32 слайд
3 место
В
А
В
Г
Б
А
В
А
Б
В
А
Б
В
Б
Г
В
Г
Б
Г
Б
Г
Б
Г
Г
Б
В
В
Б
Подчитаем все варианты цепочек: их 16.
Ответ: 16 вариантов цепочек.
1 место
2 место
Для
решения
задачи
составим
граф
33 слайд
«Транспортная задача»
(ЕГЭ: 11 класс)
Велосипедист собирается проехать из пункта A в пункт E, в который ведут 3 маршрута: через B, через C, через D. Расстояния в километрах показаны на схеме. Известно, что если ехать через B, то средняя скорость будет ровна 16 км/ч, если ехать через D, то средняя скорость будет равна 18 км/ч, а если ехать через C, то средняя скорость будет равна 20 км/ч. Исходя из этих данных, велосипедист выбрал маршрут так, чтобы доехать до E за наименьшее время.
Сколько минут он планирует пробыть в пути?
34 слайд
Граф, соответствующий условию задачи.
В
D
C
Е
А
15
25
19
17
34
11
35 слайд
Решение
(15 + 25) : 16 = 2,5 (ч) – время в пути A-B-E
(19 + 17) : 18 = 2 (ч) – время в пути A-D-E
(11 + 34) : 20 = 2,25 (ч) – время в пути A-С-E
2 < 2,25 < 2,5
2 (ч) = 120 (мин)
Ответ : 120 минут он планирует пробыть в пути .
36 слайд
Олимпиада «Осенняя разминка» для 7-х классов
2009-2010 учебный год
Три профессора (Иванов, Петров и Сидоров) преподают различные предметы
(химию, биологию, историю) в университетах Москвы, Минска и Киева.
Известно что:
Иванов никогда не был в Киеве, а Петров - в Минске;
Киевлянин старше профессора истории;
Петров играет в шахматы лучше, чем биолог;
Минчанин преподает химию.
Вопрос: где и что преподает Сидоров?
37 слайд
Химия
Биология
История
Москва
Киев
Минск
Москва
Киев
Минск
Москва
Киев
Минск
Химия
История
Москва
Киев
Минск
Москва
Киев
Минск
Москва
Киев
Минск
Биология
Киев
Минск
Москва
Киев
Минск
Киев
Минск
Москва
Биология
Химия
Москва
История
Иванов
Петров
Сидоров
Графы, с помощью которых ищется решение задачи.
38 слайд
Т.к. Иванов никогда не был в Киеве, а Петров в Минске Иванов не из Киева, а Петров не из Минска.
Петров играет в шахматы лучше, чем биолог Петров не биолог.
Минчанин преподает химию. Петров не преподает химию. Петров Историк.
Иванов не историк и Сидоров не историк.
Киевлянин старше профессора истории Петров не может быть киевлянином. Петров – москвич. Киевлянином может быть только Сидоров.
Сидоров не может быть москвичом или минчанином Иванов - минчанин.
Минчанин преподает химию Иванов – химик. Иванов не может быть биологом, а Сидоров – химиком Сидоров – биолог.
Ответ: Сидоров – биолог и живет в Киеве.
Решение
39 слайд
Задача про озера
В стране «Озерной» - 7 озер,
Каналы их соединяют.
А между ними – острова,
И сколько их – никто не знает.
Мы на вопрос дадим ответ,
Учтем: всего каналов – 10.
А сколько островов там есть?
Ответь, как следует все взвесив.
40 слайд
КОНЕЦ
Рабочие листы
к вашим урокам
Скачать
Рабочие листы
к вашим урокам
Скачать
6 651 868 материалов в базе
«Алгебра», Макарычев Ю.Н., Миндюк Н.Г., Нешков К.И. и др. / Под ред. Теляковского С.А.
Больше материалов по этому УМКНастоящий материал опубликован пользователем Лазарева Людмила Леонидовна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материалВаша скидка на курсы
40%Курс профессиональной переподготовки
500/1000 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Курс повышения квалификации
36 ч. — 144 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Мини-курс
10 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.