Разделы презентаций


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

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

Слайды и текст этой презентации

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

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

Слайд 2Теоретические сведения
Граф – это схема действий объектов. Объекты могут изображаться

точками или геометрическими фигурами. Это вершины графа.
Связи между объектами

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

1. На основании таблицы нужно построить граф всех возможных путей перемещения из начального пункта в конечный пункт.

2. Обозначить на схеме расстояние между пунктами.
3. Определить расстояние по каждому возможному пути.

Теоретические сведенияГраф – это схема действий объектов. Объекты могут изображаться точками или геометрическими фигурами. Это вершины графа.

Слайд 3Каждой вершине, начиная с начальной (A), поставим в соответствие индекс,

равный количеству путей, которыми можно попасть в эту вершину. Для

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

Слайд 4Очевидно, что мы можем посчитать индекс только тех вершин, индексы

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

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

Слайд 5Решение задач

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

Слайд 6Задача 1
Между населёнными пунктами A, B, C, D, E построены

дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего

пути между пунктами A и Е.

Варианты ответов:
1) 4 2) 5 3) 6 4) 7

Задача 1Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в

Слайд 7Ответ: 2
Пояснение:
1. На основании таблицы построим граф - схему дорог:
По

графу видно, что есть три маршрута из А в Е:


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

Слайд 8Задача 2
Между населёнными пунктами A, B, C, D, E построены

дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего

пути между пунктами A и Е.

Варианты ответов:
1) 4 2) 5 3) 6 4) 3

Задача 2Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в

Слайд 9Ответ: 1
Пояснение:
1. Построим схему дорог:
По графу видно, что есть четыре

маршрута из А в Е:
АВЕ: 2 + 2 =

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

Слайд 10Задача 3
Между населёнными пунктами A, B, C, D, E построены

дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего

пути между пунктами В и Е.

Варианты ответов:
1) 10 2) 9 3) 18 4) 8

Задача 3Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в

Слайд 11Ответ: 2
Пояснение:
1. На основании таблицы построим граф - схему дорог:
По

графу видно, что есть два кратчайших маршрута из В в

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

Слайд 12Задача 4
Между населёнными пунктами A, B, C, D, E построены

дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего

пути между пунктами A и Е.

Варианты ответов:
1) 5 2) 7 3) 8 4) 10

Задача 4Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в

Слайд 13Ответ: 2
Пояснение:
1. На основании таблицы построим граф - схему дорог:
По

графу видно, что есть три маршрута из А в Е:


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

Слайд 14Задача 5
Между населёнными пунктами A, B, C, D, E построены

дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего

пути между пунктами В и Е.

Варианты ответов:
1) 7 2) 8 3) 9 4) 10

Задача 5Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в

Слайд 15Ответ: 4
Пояснение:
1. На основании таблицы построим граф - схему дорог:
По

графу видно, что есть пять маршрутов
из В в Е:


ВAЕ: 7 + 4 =11
BСDЕ: 2 + 3 + 5 = 10
BDE: 5 + 5 = 10
BADE: 7 + 1 + 5 = 13
BDAE: 5 + 1 + 4 = 10

Одинаковые по длине кратчайшие маршруты:
BCDE, BDE, ВDAE. Длина каждого равна 10.

Ответ: 4Пояснение:1. На основании таблицы построим граф - схему дорог:По графу видно, что есть пять маршрутов из

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика