Конспект урока в 7 классе по теме ""Решение задач с помощью графов" ( статистика)

Решение задач с помощью графов

Цель :

- Повторить основные понятия по теме: «Графы. Свойства графов»

- Развитие логического мышления через решение нестандартных задач, развитие математической речи

- Воспитание внимательности, интереса к предмету, расширение кругозора

1 Оргмомент

2.Фронтальный опрос по основным определениям и понятиям, связанными с графами.

3.Сообщение о Леонардо Эйлере

Леонард Эйлер (1707 – 1783) является одной из крупнейших фигур в истории науки. В 1727 году, когда ему едва исполнилось 20 лет, он был приглашен в Российскую Академию наук. Он изучал теологию, восточные языки и медицину, прежде чем целиком посвятил себя занятиям математикой, физикой и астрономией. Он добился блестящих успехов во всех этих областях и написал огромное количество работ. Первая работа о графах появилась в 1736 году в публикациях Петербургской Академии наук. К тому времени, когда он написал эту работу, он потерял зрение на один глаз, а к старости совсем ослеп, но даже это не остановило его. Уже довольно давно швейцарские математики, в частности математики его родного города Базеля, начали издавать полное собрание сочинений Эйлера, из которого пока опубликовано 50 томов. Первоначально предполагалось, что общее число томов будет близко к 100, но теперь уже думают, что оно окажется ближе к 200.

4. Решение задач.

Задача 1. Кёнигсбергские мосты.

Эйлер начал свою работу о графах с рассмотрения одной головоломки – так называемой « задачи о Кёнигсбергских мостах». Город Кёнигсберг ( ныне Калининград) расположен на берегах реки Прегель ( Преголи) и двух островах. Различные части города были соединены семью мостами. Вопрос заключался в том, можно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту?

Четыре части города обозначены буквами А, В,С и D. Так как нас интересуют только переходы по мостам, мы можем считать А, В, С, D вершинами некоторого графа, ребра которого отвечают соответствующим мостам. Этот граф изображен на рисунке :

Постарайтесь найти переходы , удовлетворяющие условию задачи

Дискуссия. При проведении обсуждения надо просить обучающихся аргументировать свой ответ, объясняя, почему они считают так, а не иначе. В ходе обсуждения можно подсказать, что задачу можно попытаться решить, если пробовать из любой точки (вершины) обвести этот граф, не отрывая карандаша от бумаги и проходя по каждому ребру только один раз, после чего вновь попасть в эту вершину. Если это удастся, то ответ на вопрос – да, возможно; если не удастся, то ответ – нет, невозможно.

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

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

Такую задачу можно рассматривать как род игры, и хотя кажется совершенно наивным развлечением, на самом деле в этом и состоит главное содержание многих головоломок и некоторых игр. Воспользуемся очень старой задачей

Задача 2. Перевозчик.

Перевозчику П было поручено перевезти через реку волка В, козу К и мешок капусты М. Его маленькая лодка за один раз могла перевезти только что-то одно. Кроме того, нельзя было оставлять волка наедине с козой или козу – с капустой. Как он должен поступить?

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

Рассмотрим все возможные здесь случаи. В первый рейс, очевидно, можно взять только козу: при этом группа П,В,К,М в исходной точке заменяются группой В, М.

Затем перевозчик возвращается один: мы получаем П,В М.Во второй рейс он может перевезти либо В, либо М, оставляя соответственно М или В. В обоих случаях он должен перевезти К обратно, и в исходной точке окажутся П,К,В или П,К,М, что допустимо. В следующую поездку он перевезет В или М, оставляя только К. Наконец, он возвращается один и перевозит К.

Таким образом, а этом предельно простом случае допустимы перемещения, указанные на рисунке:

Это показывает, что решение может быть получено двумя способами; каждый из них определяется некоторой цепью, соединяющей начальное положение П,В,К,М с конечным положением «пусто».

Совершенно аналогична задача о трех ревнивых мужьях

Задача 3. О трех ревнивых мужьях

Три сувпружеские пары в воскресенье подошли к реке, где они нашли маленькую лодку, которая не может поднять более двух человек одновременно. Переправа осложняется тем обстоятельством, чтовсе мужья ревнывы и ни один из них не может допустить, чтобы его жена оставалась без него в компании, где есть какой-нибудь другой мужчина. Как они должны поступить?

Задача 4.Драчливая семья

 К левому берегу реки подошла мама с пятью сыновьями 6, 7, 8, 9 и 10 лет. Есть трехместная лодка. Грести может только мама. Если на берегу без неё останутся дети с разницей в возрасте 1 год, они подерутся. Как маме переправить всех на правый берег так, чтобы никто не подрался?
Решение. Число означает ребёнка соответствующего возраста, + соединяет детей в лодке, рейс на правый берег, 7+9, , 7+9, .

Задача 5. Космическая переправа
 Юпитерианский фермер с выводком неразлучных звёздочек, пучеглазой гусеницей и хищным четырёхглазом должен переправить всех своих питомцев на ярмарку. В корабль вместе с ним может поместиться либо выводок, либо гусеница, либо четырёхглаз. Оставшись без присмотра, гусеница съест звёздочек, а четырёхглаз - гусеницу. Как фермеру переправить всех без потерь?

Решение. В – выводок звёздочек, Г – гусеница, Ч – четырёхглаз, рейс на другой берег, Г, , Г,.

Задача 6. Гоголь Н.В. «Мертвые души»

Охотник за мертвыми душами Павел Иванович Чичиков побывал у известных вам помещиков по одному разу у каждого. Он посещал их в следующем порядке : Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжогло, полковника Кошкарёва. Найдена схема, на которой Чичиков набросал взаимное расположение имений и проселочных дорог, соединяющих их.

Установите, какое имение кому принадлежит, если ни по одной дороге Чичиков не проезжал более одного раза.

Решение. По схеме видно, что путешествие Чичиков начал с имения Е, а закончил имением О. Замечаем, что в имения В и С ведут только по две дороги, поэтому по этим дорогам Чичиков должен проехать. Отметим их жирной линией ( рис.1.2). Определены участки маршрута, проходящие через А : АС и АВ. По дорогам АЕ, АК и АМ Чичиков не ездил. Перечеркнем их ( рис.1.2). Отметим жирной линией ЕД; перечеркнем ДК. Перечеркнем МО и МН; отметим жирной линией МF ; перечеркнем FО; отметим жирной линией FН, НК и КО ( рис.1.3). Найдем единственно возможный маршрут при данном условии.

Подведем первый итог: задача решена в ходе преобразования картинки. С рисунка 1.3 Остается считать ответ: имение Е принадлежит Манилову, Д – Коробочке, С – Ноздреву, А – Собакевичу, В – Плюшкину, М – Тентетникову, F – Бетрищеву, Н – Петуху, К – Констанжогло, О – Кошкареву.

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

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

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

Домашнее задание.

Решите задачу. Туристы ( отец, мать , сын и дочь) должны переправиться через реку. В их распоряжении есть маленькая лодка, которая вмещает одного взрослогшо или двух детей. Как организовать переправу, если и взрослые, и дети могут грести? Опишите подробно алгоритм их действий.

1) дети плывут на тот берег;
2) 1 ребенок возвращается обратно;
3) отец плывет на другую сторону;
4) возвращается 2 ребенок;
5) братья снова отправляются на тот берег;
6) 1 близнец плывет к матери;
7) мать плывет на другой берег;
8) 2 брат плывет к 1;
9) оба плывут к родителям.

1) дети плывут на тот берег;
2) 1 ребенок возвращается обратно;
3) отец плывет на другую сторону;
4) возвращается 2 ребенок;
5) братья снова отправляются на тот берег;
6) 1 близнец плывет к матери;
7) мать плывет на другой берег;
8) 2 брат плывет к 1;
9) оба плывут к родителям.

Начало формы

Пусть О и М — отец и мать, С и Д — мальчики. Алгоритм переправы может быть таким:
1)    О и М-»    5) О и М-»
2)    О 3)    С -»                7) Д-»
4)    М

Сначало 2 брата садятся в лодку и переплывают на другой берег, один брат остаётся на берегу, другой возращается к отцу и матери. Потом в лодку садится отец, переплывает и отдаёт её сыну, тот переплывает к матери и брату. Два брата садятся в лодку и переплывают реку, один брат остаётся с отцом, а другой плывёт к матери. Переплыв реку он даёт лодку матери. Она переплывает реку и даёт лодку сыну, тот плывёт за братом и они в двоём переплывают реку на лодке.Сначало 2 брата садятся в лодку и переплывают на другой берег, один брат остаётся на берегу, другой возращается к отцу и матери. Потом в лодку садится отец, переплывает и отдаёт её сыну, тот переплывает к матери и брату. Два брата садятся в лодку и переплывают реку, один брат остаётся с отцом, а другой плывёт к матери. Переплыв реку он даёт лодку матери. Она переплывает реку и даёт лодку сыну, тот плывёт за братом и они в двоём переплывают реку на лодке.Сначала отправить двух детей, первый ребенок высаживается, потом другой плывет обратно. Потом плывет мать, высаживается, отдаёт ребенку лодку. Тот плывёт за отцом, и они воссоединятся.)Сначала отправить двух детей, первый ребенок высаживается, потом другой плывет обратно. Потом плывет мать, высаживается, отдаёт ребенку лодку. Тот плывёт за отцом, и они воссоединятся.)Сначала отправить двух детей, первый ребенок высаживается, потом другой плывет обратно. Потом плывет мать, высаживается, отдаёт ребенку лодку. Тот плывёт за отцом, и они воссоединятся.)Конец формы