Метод графов - один из способов решения логических задач

Теория графов в решении логических и вероятностных задач

Метод ГРАФОВ - один из способов решения логических задач.

Учитель математики МБОУ ТСОШ №3 Митрофанова Н.В.

Родоначальник теории графов

Можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?

Леонард Эйлер (1707-1783)

Эйлер вычислял без всякого видимого усилия,

как человек дышит или как орёл парит над землёй.

Доминик Араго

Графом в математике называется конечная совокупность точек , именуемых вершинами ; некоторые из них соединены друг с другом линиями , называемых ребрами графа.

Задача №1

• Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:

Земля – Меркурий;

Плутон – Венера;

Нептун – Сатурн;

Сатурн – Юпитер;

Земля – Плутон;

Плутон – Меркурий; Меркурий – Венера;

Юпитер – Марс;

Марс – Уран.

Уран – Нептун;

• Можно ли долететь на рейсовых ракетах с Земли до Марса?

Одинаковые, но по-разному нарисованные графы, называются изоморфными

Задача №2

• В одном городе шесть станций метро: Алмазная, Золотая, Лесная, Парковая, Садовая, Серебряная. Поезда следуют по маршрутам:
• Алмазная – Золотая,
• Золотая – Серебряная,
• Серебряная – Алмазная.
• Лесная – Садовая,
• Садовая – Парковая,
• Парковая – Лесная.

Можно ли с помощью этих поездов добраться со станции Парковая до станции Алмазная?

Графическое представление решения

• Граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек .
• Обозначать граф можно буквой «Г». Ребра могут быть прямолинейными и криволинейными; длины ребер и расположение точек произвольны.
• один и тот же граф.

ГРАФ

Граф

Нуль-граф

Изоморфный

Полный

Ориентированный

Плоский

Связный

Взвешенный

Однородный

Неориентированный

Дерево

Виды графов

Ориентированный граф (кратко орграф) — рёбрам которого присвоено направление.

Неориентированный граф - это граф, в котором нет направления линий.

Связный граф – граф, в котором существует путь.

Несвязный граф

Связный граф

Несвязный граф - нет ни одного пути.

Взвешенный граф – дуги или ребра имеют вес.

Несколько интересных задач 1. «Маршруты»

Несколько интересных задач 1. «Маршруты»

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

1. «Маршруты»

• Задача 2. Передвигаться можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? Какой маршрут самый короткий и какой — самый длинный.

Кратчайший путь-1-5-9;

самый длинный - 1-2-3-6-5-7-8-9 .

2. «Группы, знакомства»

• Однажды Андрей, Борис, Володя, Даша и Галя договорились вечером пойти в кино. Выбор кинотеатра и сеанса они решили согласовать по телефону. Было также решено, что если с кем-то созвониться не удастся, то поход в кино отменяется. Вечером у кинотеатра собрались не все, и поэтому посещение кино сорвалось. На следующий день стали выяснять, кто кому звонил. Оказалось, что Андрей звонил Борису и Володе, Володя звонил Борису и Даше, Борис звонил Андрею и Даше, Даша звонила Андрею и Володе, а Галя звонила Андрею, Володе и Борису. Кто не сумел созвониться и поэтому не пришёл на встречу?

Галя и Даша не сумели созвониться между собой (точки Г и Д не соединены отрезком) и поэтому в соответствии с договорённостью в кино не пришли.

Теория графов — одна из самых красивых и наглядных математических теорий.

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

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

• Для каждой пары вершин дерева существует единственный путь , их соединяющий. Этим свойством пользуются при нахождении всех предков, например, по мужской линии, любого человека, чья родословная представлена в виде генеалогического дерева , которое является «деревом» и в смысле теории графов.

3. «Транспортная задача»

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

4. «Логическая задача на дороги»

5. «Логическая задача на переливания»

• В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю.

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

6. «Задача про пенсионеров»

• В городе 48 % взрослого населения  — мужчины. Пенсионеры составляют 12,6 % взрослого населения, причём доля пенсионеров среди женщин равна 15%.Для социологического опроса выбран случайным образом мужчина, проживающий в этом городе. Найдите вероятность события «выбранный мужчина является пенсионером».
• Пусть х   — доля мужчин-пенсионеров среди всех мужчин.

Пенсионеры составляют 0,126 взрослого населения города, откуда получаем:

Т.о., вероятность того, что случайно выбранный мужчина

окажется пенсионером, равна 0,1.

Применение графов - творчество

• Решая практические задачи с помощью теории графов необходимо в каждом шаге, в каждом этапе их решения применить творчество.
• На первом этапе нужно суметь проанализировать и закодировать условие задачи.
• Второй этап – схематическая запись, которая состоит в геометрическом представлении графов, и на этом этапе элемент творчества очень важен потому, что далеко не просто найти соответствия между элементами условия и соответствующими элементами графа.
• Метод графов интересен, красив и нагляден.

Спасибо за внимание!

Творчество и графы позволяют:

• Вычислять без всякого видимого усилия.
• Наглядно обосновывать решение.
• Упрощать условия задачи.
• Получать удовольствие от решения задачи.
• Успешно решать логические и вероятностные задачи ВПР, ОГЭ и ЕГЭ по математике.