ИНФОРМАЦИОННЫЕ МОДЕЛИ НА ГРАФАХ. ПУТИ В ГРАФАХ

ABCDE A B291 C10934 D81311 E16411

ТЕМА УРОКА: ПУТИ В ГРАФАХ

Граф Граф это набор узлов (вершин) и связей между ними (ребер). Сеть Сеть граф, в котором вершины связаны между собой по принципу «многие ко многим».

ABCD A0110 B1011 C111 D0110 A A C C D D B B Граф Схема дорог Матрица смежности 1 Петля Ребро Вершина

ГРАФЫ ориентированные неориентированные дуги рёбра

ABCD A1280 B 56 C854 D064 A A C C D D B B Взвешенный граф Весовая матрица Вес ребра 5

Взвешенный орграф A A C C D D B B ABCD A 8 B 56 C4 D4 Весовая матрица

нет да начало ввод X0, Y0, R, R1, X, Y D <= R1 вывод «Попал в «яблочко» вывод «Промахнулся» нет да D <= R вывод «Попал» конец Блок-схема – ориентированный граф Игра «Дартс»

ЕЩЕ РАЗ ПРОАНАЛИЗИРУЕМ ТАБЛИЦУ. КАКИЕ ОСОБЕННОСТИ В ТАБЛИЦЕ ВЫ ЗАМЕТИЛИ? ABCDE A B291 C10934 D81311 E16411

ТЕПЕРЬ ПРИСТУПИМ К ПОСТРОЕНИЮ ГРАФА. ABCDE A B291 C10934 D81311 E16411

ПРОВЕРИМ ПРАВИЛЬНОСТЬ ПОСТРОЕНИЯ ABCDE A B291 C10934 D81311 E16411 A B C E D

ОПРЕДЕЛИМ ВСЕ ПУТИ В ГРАФЕ И РАССТОЯНИЕ, ПРОЙДЕННОЕ НА ЭТОМ ПУТИ (ВЕС-РАССТОЯНИЕ В КМ.) A B C E D Будем делать обход по графу в алфавитном порядке, т.е. сначала все пути через АВ, АС, AD и т.д. 1. ABCDE – 25 км 2. ABCE – 15 км 3. ABDCE – 10 км 4. ACBDE – 31 км 5. ACDE – 24 км 6. ACE – 14 км 7. ADCE – 15 км 8. ADE – 19 км 9. AE – 16 км

ABCDE A B291 C10934 D81311 E16411 A B C E D

ЗАДАЧА ИЗ ДЕМОВЕРСИИ ГИА ПО ИНФОРМАТИКЕ И ИКТ 2015 ГОДА:

ABCDЕ A31 B42 C342 D1 Е22 ABCDЕ A311 B4 C342 D1 Е12 ABCDЕ A314 B42 C342 D1 Е422 ABCDЕ A1 B41 C442 D14 Е12 1)2)3)4) Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями. Решение задач Задача 2

Решение 1. Для каждой таблицы нарисуем соответствующий ей взвешенный граф. 1)2)3)4) A B C D E A B C D E A C D 2 B E A C D 1 B E ABCDЕ A31 B42 C342 D1 Е22 ABCDЕ A311 B4 C342 D1 Е12 ABCDЕ A314 B42 C342 D1 Е422 ABCDЕ A1 B41 C442 D14 Е12

Решение 2. Теперь по схемам определяем кратчайшие маршруты для каждой таблицы: 1: или, стоимость 7 или 2:, стоимость 7 3: 4:, стоимость 6 3. Условие «не больше 6» выполняется только для таблицы 3 4. Таким образом, правильный ответ – 3., стоимость 8

ПОДВЕДЕМ ИТОГИ: Мы узнали, что такое граф Можем классифицировать графы по типам: ориентированный, неориентированный Можем на основе табличной информационной модели построить граф и определить все пути в нем На основе анализа всех путей в графе мы можем делать заключение о том, какой путь самый короткий.

Босова Л. Л. Информатика: Учебник для 7 класса. Москва. БИНОМ. лаборатория знаний.2010 г; Босова Л. Л. Информатика: Учебник для 9 класса. Москва. БИНОМ. лаборатория знаний.2012 г; Босова Л. Л. Информатика: Рабочая тетрадь для 7 класса. Москва.БИНОМ. лаборатория знаний.2011 г; Босова Л.Л. Уроки информатики в 5-7 классах. Методическое пособие Москва.БИНОМ. лаборатория знаний.2010 г htm