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

сформировать представления о сферах применения графов, о способах решения

задач с помощью графов; закрепить умение строить графы (деревья). 

Задачи:
Создать мотивационную базу для изучения материала.
показать красоту этого метода.
выбирать наиболее эффективные решения поставленной задачи.

при решении задач;  Метапредметные: формирование умения выделять существенные признаки объекта и

отношения между объектами; ИКТ-компетентность (умение строить схемы);  Личностные: формирование способности увязать учебное содержание с собственным жизненным опытом, понять значение информационного моделирования как метода познания окружающей действительности. 

поступил следующим образом: он "сжал" сушу в точки, а мосты

"вытянул" в линии. Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют ГРАФОМ.

линии, которые соединяют вершины, - РЕБРАМИ графа.
Вершины, из которых

выходит нечетное число ребер, называются НЕЧЕТНЫМИ вершинами,
а вершины, из которых выходит четное число ребер, называются ЧЕТНЫМИ.

следующие СВОЙСТВА графа:
Если в фигуре только четные вершины ,

то ее можно нарисовать одним росчерком, независимо от того, с какого места начинается черчение.

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

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

про Кенигсбергские мосты, он вывел еще два СВОЙСТВА:
4)

Число нечетных вершин графа всегда четно.
5) Если в графе имеются нечетные вершины, то наименьшее число росчерков, которыми можно нарисовать граф, равно половине числа нечетных вершин этого графа.


Например, если фигура имеет четыре нечетные вершины, то ее можно начертить самое меньшее двумя росчерками.

геометрическая фигура, как начертить ее на бумаге одним росчерком пера,

не проводя дважды ни одну линию?


Например: как проложить дорожки в дендропарке, чтобы посетители увидели все растения не проходя дважды по одной.

всех дорог своего участка

всех дорог своего участка

авиалиний
Схемы метро
Иерархия объектов (например структура школы)

Файлы системы компьютера

или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются

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

рабочих;
для расчетов устойчивости откоса
В физике
Анализ электрических цепей распознаётся методом графов,

также применяется в классической электродинамике СТО, энергетике, радиоэлектронике и др.
В химии
Используется для составления формул
Для исследования стационарной кинетически ферментативных реакций

(геоботаника)
Метод графов при составлении дихотомических ключей для определения

растений.
Транспорт
Для расчета пассажиропотока
Медицина
Исследование биоритмов
Биология
Для анализа биологических структур и генных систем
Спорт
Разработка стратегии игры

и ОГЭ:

были приглашены 4 врача. Каждый из приглашенных работал в 2

поликлиниках и представлял на этом совещании обе поликлиники. Любая возможная комбинация двух поликлиник имело на этом совещании одного и только одного представителя. Сколько поликлиник в городе? Сколько врачей было приглашено на совещание?

Задача

Ответ: 5 поликлиник;
10 врачей.

в пункт можно только в направлении стрелок. В каждом пункте

можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? У какого из путей наименьшая длина? У какого наибольшая длина?

продолжительного пути 7: 1 2 3 6 5 7 8

9.
Число путей 14

Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу? Дорожки не могут

проходить через колодцы и домики.

так, чтобы можно было добраться из любого города в любой

другой

кучки камней, в первой из которых 3, а во второй

– 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16 камней. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

3,18, ∑ 21

3,2, ∑ 5

строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними

станциями. Если пересечение строки и столбца пусто, то станции не являются соседними.
Укажите таблицу, для которой выполняется условие: “Минимальная стоимость проезда
из А в B не больше 6”.
Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.

1)

2)

3)

4)

AC C B - 7
AC CE EB - 7

AC C B - 7
AE EC CB - 7

AC C B - 7
AC CE EB - 6

AD DC CB - 9
AD DC CE EB - 8

нет
2. На занятии мне понравилось:
история графов

практические задания
3. Я применю это в своей практике да нет