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

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

Цель :

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

Ход урока

1 Оргмомент

Записываем в тетради

Тринадцатое апреля

Классная работа

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

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

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

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

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

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

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

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