Рабочие листы
к вашим урокам
Скачать
1 слайд
26.12.2020
Шабанова Е.С., гимназия №39 Меркенского района
Использование графов
в решении логических
задач
2 слайд
ГРАФЫ
Графами называются геометрические фигуры, состоящие из точек (вершин графа) и линий (ребер графа), соединяющих эти точки. При этом с помощью вершин изображаются элементы некоторого множества, а с помощью рёбер –определенные связи между этими элементами.
3 слайд
Метод графов – один из способов решения логических задач.
По условию задачи составляется схема, состоящая из линий (ребер) и точек (вершин).
Пример 1. Айдар, Борис, Владимир и Григорий играли в шахматы. Каждый сыграл с каждым по одной партии. Сколько партий было сыграно?
Для решения задачи составим граф с 4 вершинами А, Б, В, Г, обозначенными первыми буквами имен участников игры в шахматы. Тогда количество рёбер этого графа дает ответ. Для наглядности каждое ребро выделено разным цветом.
ОТВЕТ: Было сыграно 6 партий.
А
Б
Г
В
4 слайд
Используя метод графов, решите задачу самостоятельно.
Пять приятелей при встрече пожали друг другу руки. Сколько всего было сделано рукопожатий?
1
2
3
4
5
5 слайд
Прием моделирования с помощью графов.
Ситуации, в которых требуется найти соответствие между элементами различных множеств, можно моделировать с помощью графов. В этом случае элементы различных множеств будем обозначать точками, а соответствия между ними –отрезками. Пунктирные линии будут обозначать отсутствие соотношений, указанных в задаче.
6 слайд
Три товарища –Иван, Дмитрий и Степан преподают различные предметы (химию, биологию и физику) в школах Москвы Тулы и Новгорода.
О них известно следующее :
Иван работает не в Москве, а Дмитрий не в Новгороде.
Москвич преподает физику.
Тот, кто работает в Новгороде, преподает химию.
Дмитрий и Степан преподают не биологию.
Какой предмет и в каком городе преподает каждый?
Пример 2.
7 слайд
В задаче можно выделить три множества: учебных предметов, городов, учителей.
Каждое множество содержит по три элемента. Обозначим их вершинами графа (точками).
Иван
Дмитрий
Степан
Москва
Тула
Новгород
химия
биология
физика
8 слайд
По условию задачи будем соединять точки отрезками (сплошными линиями), если имеет место соответствие между данными элементами, или пунктирными линиями, если соответствия нет. Таким образом, рёбра нашего графа будут либо сплошные, либо пунктирные.
Построим рёбра, используя условие: Иван работает не в Москве,
а Дмитрий не в Новгороде.
Иван
Дмитрий
Степан
Москва
Тула
Новгород
химия
биология
физика
9 слайд
Иван
Дмитрий
Степан
Москва
Тула
Новгород
химия
биология
физика
Москвич преподает физику.
10 слайд
Анализируя полученные связи, делаем вывод: житель Тулы
преподает биологию.
Иван
Дмитрий
Степан
Москва
Тула
Новгород
химия
биология
физика
Иван
Дмитрий
Степан
Москва
Тула
Новгород
химия
биология
физика
Тот, кто работает в Новгороде, преподает химию.
11 слайд
Дмитрий и Степан преподают не биологию. Добавляем два
пунктирных ребра.
Иван
Дмитрий
Степан
Москва
Тула
Новгород
химия
биология
физика
Анализируя полученные связи, делаем вывод: биологию
преподает Иван.
Иван
Дмитрий
Степан
Москва
Тула
Новгород
химия
биология
физика
12 слайд
Снова смотрим на граф и анализируем связи. Иван не живет в
Москве, Иван преподает биологию. В Новгороде живет
преподаватель химии, значит Иван не живет В Новгороде.
Вывод: Иван живет в Туле. А Дмитрий и Степан в Туле не живут.
Иван
Дмитрий
Степан
Москва
Тула
Новгород
химия
биология
физика
И опять анализируем полученные связи. Иван и Дмитрий Не живут
в Новгороде. Следовательно, в Новгороде живет Степан. А тот,
кто живет В Новгороде, преподает химию. Делаем ещё 2 сплошных
линии.
Иван
Дмитрий
Степан
Москва
Тула
Новгород
химия
биология
физика
13 слайд
Анализируем рёбра графа. Иван живёт в Туле. Степан живёт
в Новгороде. Следовательно, в Москве живёт Дмитрий.
Химию преподает Степан. Биологию преподает Иван.
Следовательно, физику преподает Дмитрий. Проводим ещё 2
сплошных линии.
Иван
Дмитрий
Степан
Москва
Тула
Новгород
химия
биология
физика
На графе имеем три треугольника, вершины которого соединены
сплошными линиями. Вершины этих треугольников дают ответ
задачи.
14 слайд
Иван
Дмитрий
Степан
Москва
Тула
Новгород
химия
биология
физика
Получаем ответ (двигаясь по вершинам графа, образующим
сплошные треугольники): Иван живёт в Туле и преподает
биологию. Дмитрий живёт в Москве и преподает физику.
Степан живёт в Новгороде и преподает химию.
15 слайд
Используя метод графов, решите задачу самостоятельно.
Однажды на отдыхе за круглым столом оказались пятеро ребят родом из Москвы, Санкт-Петербурга, Новгорода, Перми и Томска: Юра, Толя, Алеша, Коля и Витя. Москвич сидел между томичом и Витей, санкт-петербуржец - между Юрой и Толей, а напротив него сидели пермяки Алеша. Коля никогда не был в Санкт-Петербурге, а Юра не бывал в Москве и Томске, а томич с Толей регулярно переписываются. Определите, в каком городе живет каждый из ребят.
Ответ: Толя живет в Москве, Витя - в Санкт-Петербурге, Юра - в Новгороде, Коля - в Перми, а Алеша - в Томске.
Рабочие листы
к вашим урокам
Скачать
6 655 033 материала в базе
Настоящий материал опубликован пользователем Финаева-Николотова Ирина Витальевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс профессиональной переподготовки
500/1000 ч.
Курс профессиональной переподготовки
600 ч.
Курс профессиональной переподготовки
300/600 ч.
Курс повышения квалификации
72/180 ч.
Мини-курс
6 ч.
Мини-курс
3 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.