kopilkaurokov.ru - сайт для учителей

Создайте Ваш сайт учителя Курсы ПК и ППК Видеоуроки Олимпиады Вебинары для учителей

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

Нажмите, чтобы узнать подробности

Мастер-класс «Применение теории графов к решению задач»

На изучение темы «Информационные модели на графах. Использование графов при решении задач»  отводится 2 часа. Эта тема входит в раздел представление информации. 

Теория возникновения графа:     Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783).Через город Кенигсберг протекает река Преголя. Она делится на два рукава и огибает остров. В XVIII веке в городе было семь мостов,

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


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

Вершины, из которых выходит нечетное число ребер, называют нечетными вершинами, а вершины, из которых выходит четное количество ребер, - четными.

Решая задачу про Кенигсбергские мосты, Эйлер установил, в частности, следующие  свойства  графа:

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

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

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

4)  Число нечетных вершин графа всегда четно.

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

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

Вы уже знаете о суперспособностях современного учителя?
Тратить минимум сил на подготовку и проведение уроков.
Быстро и объективно проверять знания учащихся.
Сделать изучение нового материала максимально понятным.
Избавить себя от подбора заданий и их проверки после уроков.
Наладить дисциплину на своих уроках.
Получить возможность работать творчески.

Просмотр содержимого документа
«Решение задач с помощью графа »

Мастер-класс  «Применение теории графов к решению задач»

Мастер-класс «Применение теории графов к решению задач»

«Чтоб мудро жизнь прожить  Знать надобно немало…»  О.Хайям  Цель:   сформировать представления о сферах применения графов, о способах решения задач с помощью графов; закрепить умение строить графы (деревья).   Задачи:

«Чтоб мудро жизнь прожить Знать надобно немало…» О.Хайям

Цель:

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

Задачи:

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

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

История вопроса Задача о семи Кёнигсбергских мостах

История вопроса

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

Основные понятия  При решении задачи о Кенигсбергских мостах Эйлер поступил следующим образом: он

Основные понятия

При решении задачи о Кенигсбергских мостах Эйлер поступил следующим образом: он "сжал" сушу в точки, а мосты "вытянул" в линии. Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют ГРАФОМ .

Точки А, В, С, D называют ВЕРШИНАМИ графа, а линии, которые соединяют вершины, - РЕБРАМИ графа. Вершины, из которых выходит нечетное число ребер, называются НЕЧЕТНЫМИ вершинами, а вершины, из которых выходит четное число ребер, называются ЧЕТНЫМИ .

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

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

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

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

Свойства графов

Решая задачу про Кенигсбергские мосты, Эйлер установил, в частности, следующие СВОЙСТВА графа:

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

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

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

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

Свойства графов Кроме трех свойств графа, которые установил Эйлер, решая задачу про Кенигсбергские мосты, он вывел еще два СВОЙСТВА :  4) Число нечетных вершин графа всегда четно.  5) Если в графе имеются нечетные вершины, то наименьшее число росчерков, которыми можно нарисовать граф, равно половине числа нечетных вершин этого графа. Например, если фигура имеет четыре нечетные вершины, то ее можно начертить самое меньшее двумя росчерками.

Свойства графов

Кроме трех свойств графа, которые установил Эйлер, решая задачу про Кенигсбергские мосты, он вывел еще два СВОЙСТВА :

4) Число нечетных вершин графа всегда четно.

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

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

Этот вопрос положил начало циклу новых увлекательных задач: если дана геометрическая фигура, как начертить ее на бумаге одним росчерком пера , не проводя дважды ни одну линию? Например: как проложить дорожки в дендропарке, чтобы посетители увидели все растения не проходя дважды по одной.

Этот вопрос положил начало циклу новых увлекательных задач:

если дана геометрическая фигура, как начертить ее на бумаге одним росчерком пера , не проводя дважды ни одну линию?

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

Вторая группа Первая группа Уникурсальная кривая

Вторая группа

Первая группа

Уникурсальная кривая

Соединить 9 точек 4 линиями не отрывая руки

Соединить 9 точек 4 линиями не отрывая руки

Укажите оптимальный маршрут, по которому трактор может убрать снег со всех дорог своего участка

Укажите оптимальный маршрут, по которому трактор может убрать снег со всех дорог своего участка

Укажите оптимальный маршрут, по которому трактор может убрать снег со всех дорог своего участка

Укажите оптимальный маршрут, по которому трактор может убрать снег со всех дорог своего участка

Примеры графов

Примеры графов

  • Изображение железных дорог на географических картах;
  • Схемы авиалиний
  • Схемы метро
  • Иерархия объектов (например структура школы)
  • Файлы системы компьютера
Схема железнодорожных станций Схема метро

Схема железнодорожных станций

Схема метро

Схема горнолыжных трасс Географическая карта

Схема горнолыжных трасс

Географическая карта

Блок – схемы программ для ЭВМ

Блок – схемы программ для ЭВМ

Схема авиалиний

Схема авиалиний

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

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

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

Графы используются :

В строительстве

для составления чертежей;

для расчета материала;

для расчета количества рабочих;

для расчетов устойчивости откоса

В физике

Анализ электрических цепей распознаётся методом графов, также применяется в классической электродинамике СТО, энергетике, радиоэлектронике и др.

В химии

Используется для составления формул

Для исследования стационарной кинетически ферментативных реакций

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

Финансы и кредит

«Теория графов в управлении организационными системами»

Экология (геоботаника)

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

Транспорт

Для расчета пассажиропотока

Медицина

Исследование биоритмов

Биология

Для анализа биологических структур и генных систем

Спорт

Разработка стратегии игры

С помощью построения графа решается ряд задач входящих в ЕГЭ и ОГЭ:

С помощью построения графа решается ряд задач входящих в ЕГЭ и ОГЭ:

Задача  В городе проводилось совещание врачей. От каждой поликлиники были приглашены 4 врача. Каждый из приглашенных работал в 2 поликлиниках и представлял на этом совещании обе поликлиники. Любая возможная комбинация двух поликлиник имело на этом совещании одного и только одного представителя. Сколько поликлиник в городе? Сколько врачей было приглашено на совещание? Ответ: 5 поликлиник;  10 врачей.

Задача

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

Ответ: 5 поликлиник;

10 врачей.

Поиск количества путей На рисунке изображена схема местности. Передвигаться из пункта в пункт можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? У какого из путей наименьшая длина? У какого наибольшая длина? 2 3 1 5 6 4 7 9 8

Поиск количества путей

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

2

3

1

5

6

4

7

9

8

2 1 3 Решение задачи 5 6 4 1 7 8 9 5 5 4 2 1 ярус 5 5 5 5 8 3 7 7 9 2 ярус 8 9 8 9 8 8 6 9 7 7 3 ярус 9 9 5 9 5 9 8 9 8 4 ярус 9 8 9 9 7 5 ярус Кратчайший путь: 1 5 9. Его длинна 2. Длина наиболее продолжительного пути 7: 1 2 3 6 5 7 8 9. Число путей 14 9 8 6 ярус 7 ярус 9

2

1

3

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

5

6

4

1

7

8

9

5

5

4

2

1 ярус

5

5

5

5

8

3

7

7

9

2 ярус

8

9

8

9

8

8

6

9

7

7

3 ярус

9

9

5

9

5

9

8

9

8

4 ярус

9

8

9

9

7

5 ярус

Кратчайший путь: 1 5 9. Его длинна 2.

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

Число путей 14

9

8

6 ярус

7 ярус

9

Проблема трех домов и трех колодцев Три соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу? Дорожки не могут проходить через колодцы и домики.

Проблема трех домов и трех колодцев

Три соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу? Дорожки не могут проходить через колодцы и домики.

Задача о 4 красках

Задача о 4 красках

Задача о нахождении минимального остовного дерева    N - городов, которые необходимо соединить дорогами, так, чтобы можно было добраться из любого города в любой другой

Задача о нахождении минимального остовного дерева

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

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

3,2, ∑ 5

1 ход

1 игрок

3,6, ∑ 9

9,2, ∑ 11

3,3, ∑ 6

3,3, ∑ 6

4,2, ∑ 6

2 ход

2 игрок

3,4, ∑ 7

3,9, ∑ 12

12,2, ∑ 14

3,18, 21

5,2, ∑ 7

4,3, ∑ 7

27,2, 29

4,6, ∑ 10

Правильное указание выигрывающего игрока и его ходов со строгим доказательством правильности (с помощью дерева игры)

Оценивается максимальным кол-вом баллов.

Выигрывает второй игрок.

Для доказательства рассмотрим неполное дерево игры

Числа соответствуют количеству камней на каждом этапе игры, в первой и второй кучах соответственно и их сумма.

Второй игрок выигрывает на четвертом ходу, после любого ответа первого игрока.

Дерево содержит все возможные варианты ходов первого игрока. Из него видно,

что при любом ходе первого игрока у второго имеется ход, приводящий к победе.

3 ход

1 игрок

12,3, ∑ 15

4,9, ∑ 13

5,3, ∑ 8

4,4, ∑ 8

4 ход

2 игрок

36,3, 39

15,3, 18

4,27, 31

12,9, 21

13,3, 16

12 ,9, ∑21

12,4, 16

12,4, 16

31

Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: “ Минимальная стоимость проезда из А в B не больше 6 ”. Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.  2) 1) 3) 4) A A B B C C D D 4 4 1 1 Е Е 4 1 4 1 2 2 A A A A A A B B B B B B C C C C C C 3 3 3 3 3 3 D D D D D D 1 Е 1 4 4 Е Е 1 4 Е 1 4 4 Е 4 Е 1 1 1 1 1 2 2 1 2 2 2 2 2 2 A A A A B B B B 3 3 1 3 1 1 1 2 4 4 4 4 C C C C 2 E E 2 E E 2 2 1 1 1 4 D D D D AC C B - 7 AC CE EB - 6 AC C B - 7 AE EC CB - 7 AD DC CB - 9 AD DC CE EB - 8 AC C B - 7 AC CE EB - 7

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

Укажите таблицу, для которой выполняется условие: “ Минимальная стоимость проезда

из А в B не больше 6 ”.

Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.

2)

1)

3)

4)

A

A

B

B

C

C

D

D

4

4

1

1

Е

Е

4

1

4

1

2

2

A

A

A

A

A

A

B

B

B

B

B

B

C

C

C

C

C

C

3

3

3

3

3

3

D

D

D

D

D

D

1

Е

1

4

4

Е

Е

1

4

Е

1

4

4

Е

4

Е

1

1

1

1

1

2

2

1

2

2

2

2

2

2

A

A

A

A

B

B

B

B

3

3

1

3

1

1

1

2

4

4

4

4

C

C

C

C

2

E

E

2

E

E

2

2

1

1

1

4

D

D

D

D

AC C B - 7

AC CE EB - 6

AC C B - 7

AE EC CB - 7

AD DC CB - 9

AD DC CE EB - 8

AC C B - 7

AC CE EB - 7

Рефлексия Выберите ответ: 1. На занятии я узнал что-то новое да нет 2. На занятии мне понравилось: история графов практические задания 3. Я применю это в своей практике да нет

Рефлексия

Выберите ответ:

1. На занятии я узнал что-то новое да нет

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

история графов практические задания

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


Получите в подарок сайт учителя

Предмет: Информатика

Категория: Презентации

Целевая аудитория: 6 класс

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

Автор: Чекунова Вера Борисовна

Дата: 21.04.2015

Номер свидетельства: 204268

Похожие файлы

object(ArrayObject)#863 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(69) "Урок в 9 классе "Комбинаторные задачи" "
    ["seo_title"] => string(39) "urok-v-9-klassie-kombinatornyie-zadachi"
    ["file_id"] => string(6) "222656"
    ["category_seo"] => string(10) "matematika"
    ["subcategory_seo"] => string(5) "uroki"
    ["date"] => string(10) "1436634901"
  }
}
object(ArrayObject)#885 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(171) "Конспект урока математики на тему: "Решение задач на увеличение и уменьшение в несколько раз" "
    ["seo_title"] => string(107) "konspiekt-uroka-matiematiki-na-tiemu-rieshieniie-zadach-na-uvielichieniie-i-umien-shieniie-v-nieskol-ko-raz"
    ["file_id"] => string(6) "125373"
    ["category_seo"] => string(16) "nachalniyeKlassi"
    ["subcategory_seo"] => string(5) "uroki"
    ["date"] => string(10) "1414958051"
  }
}
object(ArrayObject)#863 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(71) "решение комбинаторных задач в 5 классе "
    ["seo_title"] => string(45) "rieshieniie-kombinatornykh-zadach-v-5-klassie"
    ["file_id"] => string(6) "182964"
    ["category_seo"] => string(10) "matematika"
    ["subcategory_seo"] => string(5) "uroki"
    ["date"] => string(10) "1425660050"
  }
}
object(ArrayObject)#885 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(211) "Конспект урока по математике " Повторение сравнения. Решение задач" по программе "Начальная школа XXI века" в 1 классе "
    ["seo_title"] => string(131) "konspiekt-uroka-po-matiematikie-povtorieniie-sravnieniia-rieshieniie-zadach-po-proghrammie-nachal-naia-shkola-xxi-vieka-v-1-klassie"
    ["file_id"] => string(6) "199233"
    ["category_seo"] => string(16) "nachalniyeKlassi"
    ["subcategory_seo"] => string(5) "uroki"
    ["date"] => string(10) "1428551307"
  }
}
object(ArrayObject)#863 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(110) "Открытый урок  "Решение логических задач".  Урок-путешествие "
    ["seo_title"] => string(68) "otkrytyi-urok-rieshieniie-loghichieskikh-zadach-urok-putieshiestviie"
    ["file_id"] => string(6) "149510"
    ["category_seo"] => string(10) "matematika"
    ["subcategory_seo"] => string(5) "uroki"
    ["date"] => string(10) "1420214816"
  }
}


Получите в подарок сайт учителя

Видеоуроки для учителей

Курсы для учителей

ПОЛУЧИТЕ СВИДЕТЕЛЬСТВО МГНОВЕННО

Добавить свою работу

* Свидетельство о публикации выдается БЕСПЛАТНО, СРАЗУ же после добавления Вами Вашей работы на сайт

Удобный поиск материалов для учителей

Ваш личный кабинет
Проверка свидетельства