Графы и сети Каверина Ольга Геннадьевна учитель информатики и ИКТ МБОУ «Новониколаевская СОШ 2» р.п. Новониколаевский Волгоградская область

Волгоград Волжский Камышин Михайловка Фролово Урюпинск Граф Карта Волгоградской области

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

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

A A C C D D B B A A C C D D B B D D B B A A C C Неориентированный граф

ABCD A0110 B0011 C0011 D0000 A A C C D D B B Ориентированный граф (орграф)

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

Между четырьмя местными аэропортами: ВОСТОРГ, ЗАРЯ, ОЗЕРНЫЙ и ГОРКА, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними: Аэропорт вылета Аэропорт прилета Время вылета Время прилета ВОСТОРГ ГОРКА 16:15 18:30 ОЗЕРНЫЙ ЗАРЯ 13:40 15:50 ОЗЕРНЫЙ ВОСТОРГ14:10 16:20 ГОРКАОЗЕРНЫЙ17:05 19:20 ВОСТОРГОЗЕРНЫЙ 11:15 13:20 ЗАРЯ ОЗЕРНЫЙ 16:20 18:25 ВОСТОРГ ЗАРЯ14:00 16:15 ЗАРЯГОРКА16:05 18:15 ГОРКАЗАРЯ 14:10 16:25 ОЗЕРНЫЙ ГОРКА 18:35 19:50 Путешественник оказался в аэропорту ВОСТОРГ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт ГОРКА. 1) 16:15 2) 18:15 3)18:30 4) 19:50 Решение задач Задача 1

1.Сначала заметим, что есть прямой рейс из аэропорта ВОСТОРГ в ГОРКУ с прибытием в 18:30: ВОСТОРГ ГОРКА 16:15 18:30 2.Посмотрим, сможет ли путешественник оказаться в ГОРКЕ раньше этого времени, если полетит через другой аэропорт, с пересадкой; рассмотрим все остальные рейсы, который прибывают в аэропорт ГОРКА: ЗАРЯГОРКА16:05 18:15 ОЗЕРНЫЙ ГОРКА 18:35 19:50 3.Это значит, что имеет смысл проверить только возможность перелета через аэропорт ЗАРЯ (через ОЗЕРНЫЙ явно не получится раньше, чем прямым рейсом); для этого нужно быть в ЗАРЕ не позже, чем в 16:05 4.Смотрим, какие рейсы прибывают в аэропорт ЗАРЯ раньше, чем в 16:05: ОЗЕРНЫЙ ЗАРЯ 13:40 15:50 5.Дальше проверяем рейсы, который приходят в ОЗЕРНЫЙ раньше, чем в 13:40 ВОСТОРГОЗЕРНЫЙ 11:15 13:20 6.Таким образом, мы «пришли» от конечного пункта к начальному, в обратном направлении 7.Поэтому оптимальный маршрут 18:15 ВОСТОРГГОРКА ОЗЕРНЫЙ ЗАРЯ 15:50 13:20 8.Правильный ответ – 2. Решение

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

Самостоятельная работа В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице. ABCD A45 B436 C3 D56 1)2)3)4) Задача 1

Самостоятельная работа Задача 2 Между населенными пунктами A, B, C, D, E построены дороги, протяженность которых приведена в таблице. Определите кратчайший путь между пунктами A и D (при условии, что передвигаться можно только по построенным дорогам). ABCDE A246 B21 C4151 D53 E613

1.Что такое граф? Из чего он состоит? 2.Какой граф называется неориентированным? 3.Что такое сеть? Какие характерные особенности имеет сеть? 4.Какой граф называется ориентированным? 5.Как по весовой матрице графа определить количество ребер (количество петель)? 6.Как можно обозначить отсутствие связей между вершинами при хранении весовой матрицы в памяти реального компьютера? Вопросы

Сегодня я узнал… Я выполнял задания… Я понял, что… Теперь я могу… Я научился…