Без темы
<<  Решаем задачи «Домашняя аптечка» Роль и место психиатрической больницы в современной системе помощи  >>
Решение задач с помощью графов
Решение задач с помощью графов
Содержание
Содержание
ЧТО такое граф
ЧТО такое граф
К XVIII веку через реку, на которой стоял город Кенигсберг (ныне
К XVIII веку через реку, на которой стоял город Кенигсберг (ныне
Закономерности
Закономерности
Граф, который можно нарисовать , не отрывая карандаша от бумаги и
Граф, который можно нарисовать , не отрывая карандаша от бумаги и
Комбинаторика
Комбинаторика
Правило суммы:
Правило суммы:
Условие задачи:
Условие задачи:
В Стране Чудес построили еще один город — Г и несколько новых дорог
В Стране Чудес построили еще один город — Г и несколько новых дорог
Попугай Иннокентий знает следующие слова: филин, кот, таракан, поёт,
Попугай Иннокентий знает следующие слова: филин, кот, таракан, поёт,
В урне лежат 7 шаров 4 – черных и 3- белых
В урне лежат 7 шаров 4 – черных и 3- белых
7*6:2=21
7*6:2=21
Несколько мальчиков встретились на вокзале, чтобы поехать за город в
Несколько мальчиков встретились на вокзале, чтобы поехать за город в
Логические задачи
Логические задачи
Циклом в графе называется замкнутый путь, не проходящий дважды через
Циклом в графе называется замкнутый путь, не проходящий дважды через
Условие задачи
Условие задачи
Изобразим участников турнира точками Для каждой точки укажем ее имя
Изобразим участников турнира точками Для каждой точки укажем ее имя
Начать построение ребер следует с вершины В, так как это единственная
Начать построение ребер следует с вершины В, так как это единственная
Толя (5)
Толя (5)
Теперь однозначно определяются ребра вершины Т. С учетом ребра ВТ надо
Теперь однозначно определяются ребра вершины Т. С учетом ребра ВТ надо
Все возможные ребра теперь построены для вершин Ж, В, Т, а также для
Все возможные ребра теперь построены для вершин Ж, В, Т, а также для
ОТВЕТ: Леша играл с Толей, Ваней и Димой
ОТВЕТ: Леша играл с Толей, Ваней и Димой
Условие задачи
Условие задачи
Коля
Коля
Решение текстовых задач
Решение текстовых задач
Определение 1. Ребро графа называется ориентированным ребром, если
Определение 1. Ребро графа называется ориентированным ребром, если
Структура решения текстовых задач
Структура решения текстовых задач
1. Скорость велосипедиста 45 км/ч
1. Скорость велосипедиста 45 км/ч
Из физической формулы выразите переменную I
Из физической формулы выразите переменную I
Из разных городов навстречу друг другу движутся мотоцикл и автомобиль
Из разных городов навстречу друг другу движутся мотоцикл и автомобиль
Скорость велосипедиста 45 км/ч, а скорость автомобиля на 45 км/ч
Скорость велосипедиста 45 км/ч, а скорость автомобиля на 45 км/ч
Скорость мотоциклиста 45 км/ч, а скорость автомобиля в 2 раза больше
Скорость мотоциклиста 45 км/ч, а скорость автомобиля в 2 раза больше
Задачи на нахождение части от числа и числа по его части
Задачи на нахождение части от числа и числа по его части
?=2*3+2*3
?=2*3+2*3
Графы при решении уравнений
Графы при решении уравнений
Как рассчитать сложность задачи
Как рассчитать сложность задачи
1 этап
1 этап
1 этап
1 этап
Модель задачи та же , что и в предыдущей Используя те же данные можно
Модель задачи та же , что и в предыдущей Используя те же данные можно
Составим взаимно-обратные задачи
Составим взаимно-обратные задачи
с=а*в А=а1+а2 а1=а2+d С=(а1+а2)*в=(а1+d +a2)*в=(2а2+d)*в 120=(2х+30)*2
с=а*в А=а1+а2 а1=а2+d С=(а1+а2)*в=(а1+d +a2)*в=(2а2+d)*в 120=(2х+30)*2
?=2*5+2*3=16
?=2*5+2*3=16
Решение задач В12
Решение задач В12
3. Из одной точки круговой трассы, длина которой равна 14 км,
3. Из одной точки круговой трассы, длина которой равна 14 км,
5. Первую треть трассы велосипедист ехал со скоростью 12 км/ч, вторую
5. Первую треть трассы велосипедист ехал со скоростью 12 км/ч, вторую
7. Каждый из двух рабочих одинаковой квалификации может выполнить
7. Каждый из двух рабочих одинаковой квалификации может выполнить
10
10
Источники
Источники

Презентация: «Решение задач с помощью графов». Автор: Admin. Файл: «Решение задач с помощью графов.pptx». Размер zip-архива: 329 КБ.

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

содержание презентации «Решение задач с помощью графов.pptx»
СлайдТекст
1 Решение задач с помощью графов

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

Кононова И.В., учитель математики МОУ «Черлакская средняя общеобразовательная школа №2» Гурова Л. М., методист МБУ «Информационно-методический и ресурсный центр в сфере образования» Черлакская МР

1

2 Содержание

Содержание

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

2

3 ЧТО такое граф

ЧТО такое граф

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

3

4 К XVIII веку через реку, на которой стоял город Кенигсберг (ныне

К XVIII веку через реку, на которой стоял город Кенигсберг (ныне

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

4

5 Закономерности

Закономерности

Невозможно начертить граф с нечетным числом нечетных вершин. Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине. Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком». Фигура (граф), которую можно начертить не отрывая карандаш от бумаги, называется уникурсальной.

5

6 Граф, который можно нарисовать , не отрывая карандаша от бумаги и

Граф, который можно нарисовать , не отрывая карандаша от бумаги и

проводя каждое ребро один раз, называется эйлеровым графом

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

6

7 Комбинаторика

Комбинаторика

-раздел математики, рассматривающий вопросы(задачи), связанные с подсчётом числа всевозможных комбинаций из элементов данного конечного множества при сделанных исходных предположениях. Большинство задач решается с помощью двух правил: правило сложения и правило произведения

7

8 Правило суммы:

Правило суммы:

Правило произведения:

Если объект А можно выбрать m способами, а объект В – n способами, то выбор «либо А, либо В», можно сделать (m +n) способами

Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А;В) в указанном порядке можно сделать mn способами

8

9 Условие задачи:

Условие задачи:

В Стране Чудес есть три города: А, Б и В. Из города А в город Б ведет 6 дорог, а из города Б в город В — 4 дороги (см. рис.). Сколькими способами можно проехать от А до В?

9

10 В Стране Чудес построили еще один город — Г и несколько новых дорог

В Стране Чудес построили еще один город — Г и несколько новых дорог

Стране Чудес построили еще один город — Г и несколько новых дорог (см. рис.). Сколькими способами можно теперь добраться из города А в город В?

10

11 Попугай Иннокентий знает следующие слова: филин, кот, таракан, поёт,

Попугай Иннокентий знает следующие слова: филин, кот, таракан, поёт,

бежит, стучит, спит, говорливый, мудрый, усатый. Он может произносить такие фразы: прилагательное + существительное + глагол . Например, «Мудрый таракан поёт». Сколько разных фраз может сказать Кеша?

11

12 В урне лежат 7 шаров 4 – черных и 3- белых

В урне лежат 7 шаров 4 – черных и 3- белых

Из урны наугад выбирается сразу 2 шара. 1. Какова вероятность того, что взяли 2 белых шара? 2. Какова вероятность того что в урне останется один белый шар?

12

13 7*6:2=21

7*6:2=21

В турнире участвовало 7 команд, причем каждый сыграл с каждым по одной партии. Сколько всего сыграно партий?

13

14 Несколько мальчиков встретились на вокзале, чтобы поехать за город в

Несколько мальчиков встретились на вокзале, чтобы поехать за город в

лес. При встрече все они поздоровались друг с другом за руку. Сколько мальчиков поехали за город, если всего было 10 рукопожатий?

14

15 Логические задачи

Логические задачи

15

16 Циклом в графе называется замкнутый путь, не проходящий дважды через

Циклом в графе называется замкнутый путь, не проходящий дважды через

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

16

17 Условие задачи

Условие задачи

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

Требуется определить: с кем сыграл Леша.

Известно, что в настоящий момент: Ваня сыграл шесть партий; Толя сыграл пять партий; Леша и Дима сыграли по три партии; Семен и Илья сыграли по две партии; Женя сыграл одну партию.

17

18 Изобразим участников турнира точками Для каждой точки укажем ее имя

Изобразим участников турнира точками Для каждой точки укажем ее имя

(по первой букве имени игрока) и количество партий, сыгранные этим игроком

Толя (5)

Леша (3)

Ваня (6)

Дима (3)

Женя (1)

Семен (2)

Илья (2)

Число в скобках называют степенью вершины, оно показывает сколько ребер выходит из данной вершины

18

19 Начать построение ребер следует с вершины В, так как это единственная

Начать построение ребер следует с вершины В, так как это единственная

вершина, которая соединяется со всеми другими вершинами графа

Толя (5)

Леша (3)

Ваня (6)

Дима (3)

Женя (1)

Семен (2)

Илья (2)

Будем строить ребра графа с учетом степеней вершин

19

20 Толя (5)

Толя (5)

Леша (3)

Ваня (6)

Дима (3)

Женя (1)

Семен (2)

Илья (2)

Для вершин В и Ж построены все возможные ребра

Сделаем первые выводы:

20

21 Теперь однозначно определяются ребра вершины Т. С учетом ребра ВТ надо

Теперь однозначно определяются ребра вершины Т. С учетом ребра ВТ надо

построить четыре ребра

Толя (5)

Леша (3)

Ваня (6)

Дима (3)

Женя (1)

Семен (2)

Илья (2)

Построим следующие ребра

21

22 Все возможные ребра теперь построены для вершин Ж, В, Т, а также для

Все возможные ребра теперь построены для вершин Ж, В, Т, а также для

вершин С и И

Толя (5)

Ваня (6)

Леша (3)

Дима (3)

Женя (1)

Семен (2)

Илья (2)

Пора делать новые выводы

22

23 ОТВЕТ: Леша играл с Толей, Ваней и Димой

ОТВЕТ: Леша играл с Толей, Ваней и Димой

Требовалось определить: с кем сыграл Леша.

Толя (5)

Леша (3)

Ваня (6)

Дима (3)

Женя (1)

Семен (2)

Илья (2)

Граф к задаче построен

23

24 Условие задачи

Условие задачи

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

24

25 Коля

Коля

Вадим

Сергей

Андрей

Электрик

Шофер

Слесарь

Токарь

Начинаем анализировать полученную схему.

От каждого верхнего кружка должно исходить 4 линии к кружкам нижнего ряда,одна из которых сплошная(прочная связь) ,три-пунктирные. (разрывная связь). И от кружков нижнего ряда-аналогично.

От Сергея отходит 3 разрывные связи, значит, четвертая- прочная связь

Ответ готов: Вадим-токарь, Сергей-слесарь, Коля-электрик, Андрей-шофер

25

26 Решение текстовых задач

Решение текстовых задач

Основные понятия Основные сюжеты задач Задачи на движение Задачи на количественные отношения Задачи на производительность Задачи на проценты

26

27 Определение 1. Ребро графа называется ориентированным ребром, если

Определение 1. Ребро графа называется ориентированным ребром, если

одну из его вершин считать началом, а другую — концом этого ребра . Определение 2. Граф, у которого все ребра ориентированные, называется ориентированным графом.

27

28 Структура решения текстовых задач

Структура решения текстовых задач

28

29 1. Скорость велосипедиста 45 км/ч

1. Скорость велосипедиста 45 км/ч

Какое расстояние он пройдет за 2 часа? 2. Рабочий выпускает в день 45 деталей. Сколько деталей он выпустит за 2 дня? 3. 1 кг лимонов стоит 45 руб. Сколько стоит 2 кг лимонов?

С=а*в

Граф зависимости

29

30 Из физической формулы выразите переменную I

Из физической формулы выразите переменную I

30

31 Из разных городов навстречу друг другу движутся мотоцикл и автомобиль

Из разных городов навстречу друг другу движутся мотоцикл и автомобиль

Скорость мотоцикла 45 км/ч, а скорость автомобиля 90 км/ч. Найти скорость сближения.

Граф суммирования (вычитания)

31

32 Скорость велосипедиста 45 км/ч, а скорость автомобиля на 45 км/ч

Скорость велосипедиста 45 км/ч, а скорость автомобиля на 45 км/ч

больше. Найти скорость автомобиля

Граф разностного сравнения

32

33 Скорость мотоциклиста 45 км/ч, а скорость автомобиля в 2 раза больше

Скорость мотоциклиста 45 км/ч, а скорость автомобиля в 2 раза больше

Найти скорость автомобиля.

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

33

34 Задачи на нахождение части от числа и числа по его части

Задачи на нахождение части от числа и числа по его части

Задачи на проценты.

В классе 30 учащихся, из них 5 отличников. Какую часть составляют отличники?

А- отличников А1 – всего d – результат сравнения

34

35 ?=2*3+2*3

?=2*3+2*3

Из 4 800 г пряжи связали 16 шарфов. Сколько пряжи пойдет на 11 таких шарфов?

с2=а*в2 С1=а*в1, отсюда а=с1/в1

35

36 Графы при решении уравнений

Графы при решении уравнений

Графы нужны как средство выведения свойств уравнений, а уравнения решаются на основе свойств уравнений

36

37 Как рассчитать сложность задачи

Как рассчитать сложность задачи

?=2(кол-во ребер, выходящих из вершины с)*7(количество вершин в дереве)+2(кол-во ребер, выходящих их вершины а)*5(кол-во вершин)+2(2(кол-во ребер, выходящих их вершины а1)*3(кол-во вершин)=14+10+6=30

37

38 1 этап

1 этап

С=с1+с2 2 этап. С1= а1*в 3 этап. С2= а2*в 4 этап. С=а1*в+а2*в 5 этап. С= в*(а1+а2) 6 этап. С=2*(45+15)

38

39 1 этап

1 этап

а=а1+а2 2 этап. С= в*(а1+а2) 3 этап. С=2*(45+15)

39

40 Модель задачи та же , что и в предыдущей Используя те же данные можно

Модель задачи та же , что и в предыдущей Используя те же данные можно

составить задачу на другой сюжет, например на стоимость.

40

41 Составим взаимно-обратные задачи

Составим взаимно-обратные задачи

Или по формуле с=(а1+а2)*в 120=(45+15)*в 60в=120, в=2

41

42 с=а*в А=а1+а2 а1=а2+d С=(а1+а2)*в=(а1+d +a2)*в=(2а2+d)*в 120=(2х+30)*2

с=а*в А=а1+а2 а1=а2+d С=(а1+а2)*в=(а1+d +a2)*в=(2а2+d)*в 120=(2х+30)*2

42

43 ?=2*5+2*3=16

?=2*5+2*3=16

Задача I. Поезд идет со скоростью 40 км/ч. По наблюдению машиниста встречный поезд, длина которого 75 м, проходит мимо него за 3 с. Найти скорость движения встречного поезда. Задача II. Со станции одновременно в разных направлениях отправились два поезда. Через 3 с расстояние между ними стало 75 м. Найти скорость второго поезда, если скорость первого поезда – 40 км/ч.

С=75км/ч а1=40км/ч в=3с а2-? Км/ч с=(а1+а2)*в а2=50 км/ч

43

44 Решение задач В12

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

1. Расстояние между городами A и B равно 435 км. Из города А в город В со скоростью 60 км/ч выехал первый автомобиль, а через час после этого навстречу ему из города В выехал со скоростью 65 км/ч второй автомобиль. На каком расстоянии от города А автомобили встретятся? Ответ дайте в километрах. 2. Два пешехода отправляются одновременно в одном направлении из одного и того же места на прогулку по аллее парка. Скорость первого на 1,5 км/ч больше скорости второго. Через сколько минут расстояние между пешеходами станет равным 300 метрам?

44

45 3. Из одной точки круговой трассы, длина которой равна 14 км,

3. Из одной точки круговой трассы, длина которой равна 14 км,

одновременно в одном направлении стартовали два автомобиля. Скорость первого автомобиля равна 80 км/ч, и через 40 минут после старта он опережал второй автомобиль на один крут. Найдите скорость второго автомобиля. Ответ дайте в км/ч. 4. Теплоход, скорость которого в неподвижной воде равна 25 км/ч, проходит по течению реки и после стоянки возвращается в исходный пункт. Скорость течения равна 3 км/ч, стоянка длится 5 часов, а в исходный пункт теплоход возвращается через 30 часов после отплытия из него. Сколько километров прошел теплоход за весь рейс?

45

46 5. Первую треть трассы велосипедист ехал со скоростью 12 км/ч, вторую

5. Первую треть трассы велосипедист ехал со скоростью 12 км/ч, вторую

треть — со скоростью 16 км/ч, а последнюю треть — со скоростью 24 км/ч. Найдите среднюю скорость велосипедиста на протяжении всего пути. Ответ дайте в км/ч. 6. По морю параллельными курсами в одном направлении следуют два сухогруза: первый длиной 120 метров, второй — длиной 80 метров. Сначала второй сухогруз отстает от первого, и в некоторый момент времени расстояние от кормы первого сухогруза до носа второго сухогруза составляет 400 метров. Через 12 минут после этого уже первый сухогруз отстает от второго так, что расстояние от кормы второго сухогруза до носа первого равно 600 метрам. На сколько километров в час 2 скорость первого сухогруза меньше скорости второго?

46

47 7. Каждый из двух рабочих одинаковой квалификации может выполнить

7. Каждый из двух рабочих одинаковой квалификации может выполнить

заказ за 15 часов. Через 3 часа после того, как один из них приступил к выполнению заказа, к нему присоединился второй рабочий, и работу над заказом они довели до конца уже вместе. Сколько часов потребовалось на выполнение всего заказа? 8. Первая труба пропускает на 6 литров воды в минуту меньше, чем вторая труба. Сколько литров воды в минуту пропускает первая труба, если бак объемом 360 литров она заполняет на 10 минут медленнее, чем вторая труба?

47

48 10

10

Виноград содержит 9 1% влаги, а изюм — 7%. Сколько килограммов винограда требуется для получения 21 килограмма изюма? 11. Том Сойер и Гекльберри Финн красят забор длиной 0 метров. Каждый следующий день они красят больше, чем в предыдущий, на одно и то же число метров. Известно, что за первый и последний день в сумме они покрасили 20 метров забора. За сколько дней был покрашен весь забор? 12. У гражданина Петрова 1 августа 2000 года родился сын. По этому случаю он открыл в некотором банке вклад в 00 рублей. Каждый следующий год 1 августа он пополнял вклад на 00 рублей. По условиям договора банк ежегодно 31июля начислял 2 0 % на сумму вклада. Через 6 лет у гражданина Петрова родилась дочь, и он открыл в другом банке ещё один вклад, уже в 2200 рублей, и каждый следующий год пополнял этот вклад на 2200 рублей, а банк ежегодно начислял 4 4 % на сумму вклада. Через сколько лет после рождения сына суммы на каждом из двух вкладов сравняются, если деньги из вкладов не изымаются?

48

49 Источники

Источники

Жигачева Наталья Александровна. Графовое моделирование структур решений сюжетных задач в курсе алгебры 7 класса : Дис. ... канд. пед. наук : 13.00.02 : Омск, 2000 146 c. РГБ ОД, 61:00-13/1265-6 http://www.dslib.net/teoria-vospitania/zhigacheva.html Н.Г. Рыженко, Е.Г.Соломатова Структурная полнота систем задач в курсе математики 6 класса Н.Г. Рыженко Сложность и трудность структуры решения текстовой задачи

49

«Решение задач с помощью графов»
http://900igr.net/prezentacija/obg/reshenie-zadach-s-pomoschju-grafov-209605.html
cсылка на страницу

Без темы

252 презентации
Урок

ОБЖ

59 тем
Слайды
900igr.net > Презентации по ОБЖ > Без темы > Решение задач с помощью графов