Презентация на тему: ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ

ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
Пример решения:
Очевидно, что мы можем посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Двигаясь последовательно, мы рассчитаем индексы всех вершин.
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ
1/20
Средняя оценка: 4.5/5 (всего оценок: 79)
Код скопирован в буфер обмена
Скачать (219 Кб)
1

Первый слайд презентации

ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ

Изображение слайда
2

Слайд 2

Теоретические сведения Граф – это схема действий объектов. Объекты могут изображаться точками или геометрическими фигурами. Это вершины графа. Связи между объектами изображаются линиями. Это рёбра графа. Необходимо определить расстояние различных путей, ведущих из одного города в другой. 1. На основании таблицы нужно построить граф всех возможных путей перемещения из начального пункта в конечный пункт. 2. Обозначить на схеме расстояние между пунктами. 3. Определить расстояние по каждому возможному пути.

Изображение слайда
3

Слайд 3: Пример решения:

Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A). У вершины Д предками являются А и Б, значит индекс вершины Д равен 1+1=2.

Изображение слайда
4

Слайд 4: Очевидно, что мы можем посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Двигаясь последовательно, мы рассчитаем индексы всех вершин. Индекс вершины Ж и будет ответом задачи

Изображение слайда
5

Слайд 5

Решение задач ОГЭ №9

Изображение слайда
6

Слайд 6

На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж ? Ответ: 9 1 1 1 1 4 3 Задача 1 Пояснение: Обозначим на схеме количество путей из пункта А в любой другой пункт: 9

Изображение слайда
7

Слайд 7

На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж ? Ответ: 7 1 2 1 1 7 3 Задача 2 Пояснение:

Изображение слайда
8

Слайд 8

Ответ: 9 На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К ? 1 1 2 4 4 1 5 9 Задача 3 Пояснение:

Изображение слайда
9

Слайд 9

Ответ: 7 На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К ? 1 2 2 2 2 2 2 1 5 7 Задача 4 Пояснение:

Изображение слайда
10

Слайд 10

Решение задач ОГЭ №4

Изображение слайда
11

Слайд 11

Задача 1 Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и Е. Варианты ответов: 1) 4 2) 5 3) 6 4) 7 A B C D E A 2 5 1 B 2 1 C 5 1 3 2 D 1 3 E 2

Изображение слайда
12

Слайд 12

Ответ: 2 Пояснение: 1. На основании таблицы п остроим граф - схему дорог: По графу видно, что есть три маршрута из А в Е: АВСЕ: 2 + 1 + 2 = 5 АСЕ: 5 +2 = 7 ADCE: 1 + 3 +2 = 6 Кратчайший из них АВСЕ: 2 + 1 + 2 = 5

Изображение слайда
13

Слайд 13

Задача 2 Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и Е. Варианты ответов: 1) 4 2) 5 3) 6 4) 3 A B C D E A 2 3 1 B 2 1 2 C 3 1 3 2 D 1 3 E 2 2

Изображение слайда
14

Слайд 14

Ответ: 1 Пояснение: 1. Построим схему дорог: По графу видно, что есть четыре маршрута из А в Е: АВЕ: 2 + 2 = 4 АВСЕ: 2 + 1 + 2 = 5 АСЕ: 3 +2 = 5 ADCE: 1 + 3 +2 = 6 Кратчайший из них: АВЕ = 2 +2 = 4

Изображение слайда
15

Слайд 15

Задача 3 Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами В и Е. Варианты ответов: 1) 10 2) 9 3) 18 4) 8 A B C D E A 5 6 10 5 B 5 4 C 6 2 7 D 10 4 2 5 E 5 7 5

Изображение слайда
16

Слайд 16

Ответ: 2 Пояснение: 1. На основании таблицы п остроим граф - схему дорог: По графу видно, что есть два кратчайших маршрута из В в Е: ВАЕ: 5 + 5 = 10 В D Е: 4 + 5 = 9 Все остальные гораздо длиннее. Кратчайший из них  В D Е: 4 + 5 = 9

Изображение слайда
17

Слайд 17

Задача 4 Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и Е. Варианты ответов: 1) 5 2) 7 3) 8 4) 10 A B C D E A 2 5 2 B 2 2 C 5 2 4 3 D 2 4 E 3

Изображение слайда
18

Слайд 18

Ответ: 2 Пояснение: 1. На основании таблицы п остроим граф - схему дорог: По графу видно, что есть три маршрута из А в Е: АВСЕ: 2 + 2 + 3 = 7 АСЕ: 5 +3 = 8 ADCE: 2 + 4 +3 = 9 Кратчайший из них АВСЕ: 2 + 1 + 2 = 5

Изображение слайда
19

Слайд 19

Задача 5 Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами В и Е. Варианты ответов: 1) 7 2) 8 3) 9 4) 10 A B C D E A 7 1 4 B 7 2 5 C 2 3 D 1 5 3 5 E 4 5

Изображение слайда
20

Последний слайд презентации: ОГЭ Задания №4, 9 Информационные модели ГРАФЫ И МАТРИЦЫ

Ответ: 4 Пояснение: 1. На основании таблицы п остроим граф - схему дорог: По графу видно, что есть пять маршрутов из В в Е: В A Е: 7 + 4 = 11 B С D Е: 2 + 3 + 5 = 10 B DE: 5 + 5 = 10 BADE: 7 + 1 + 5 = 13 BDAE: 5 + 1 + 4 = 10 Одинаковые по длине кратчайшие маршруты: BCDE, BDE,  В DAE. Длина каждого равна 10.

Изображение слайда