Семинар ДООМ Применение графов при решении задач

Версия 17:58, 9 апреля 2008

Уважаемые коллеги, вашему вниманию предлагается план урока, который в рамках обучающего тура проводили участники команды «Лемниската» в 7 классе. План этого урока был составлен с участием руководителя команды Тихомировой Л.Н.

Цель урока:

• познакомить учащихся с термином «граф»

• ввести некоторые понятия теории графов

• показать применение теории графов на примерах решения некоторых задач

Ход урока.

I. Ребята, кто-нибудь из вас слышал о графах в математическом смысле этого слова? Что же такое графы? Графы – это схемы, состоящие из точек (вершин графа) и соединяющих эти точки отрезков прямых или кривых (ребра графа).

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

II. Для того чтобы научиться строить графы, решим следующую задачу.

Задача.

Известно, что у каждой из трех девочек фамилия начинается с той же буквы, что и имя. У Ани фамилия Анисимова. У Кати фамилия не Карева, а у Киры – не Краснова. Какая фамилия у каждой из девочек?

Решение.

По условию задачи составим граф, у которого вершины – имена и фамилии девочек. Сплошная линия будет обозначать, что девочке соответствует данная фамилия, а пунктирная – что не соответствует. Из условия задачи видно, что у Ани фамилия Анисимова (соединяем сплошной линией две соответствующие точки). Из этого следует, что у Кати и у Киры фамилия не Анисимова. Так как Катя – не Анисимова и не Карева, значит она Краснова. Остается, что у Киры фамилия Карева.

Задача.

В квартирах №1, №2, №3 живут три котенка: белый, черный, рыжий. В квартире №1, №2 живут не черные котята. Белый котенок живет не в квартире №1. В какой квартире какой котенок живет?

Решение.

По условию задачи составим граф, из которого следует решение задачи.