Данное задание основано на теме “Графы”. Чтобы понять это задание, необходимо разобраться для начала с этой темой. Графы — это визуальное представление информации в виде стрелок или линий. В этом задании дано табличное представление графа, где указано расстояние между населёнными пунктами.
Прежде всего надо понять, что графы бывают двух основных типов: ориентированный и неориентированный. Ориентированный имеет направление, начальное значение и конечное, соответственно по нему можно перемещаться только в одну сторону. Неориентированный граф не имеет направления, следовательно, по нему можно перемещаться в обе стороны.
В данном задание используются неориентированные графы. Значит можно перемещаться между населёнными пунктами в двух направлениях.
Задача
Дана таблица с данными (протяжённостью дорог) между населёнными пунктами:
К примеру, нам надо найти кратчайшее расстояние между населёнными пунктами A - E. Если будем смотреть и анализировать таблицу, то можем что-то просмотреть или не заметить очевидных путей. За счёт графа у нас всё будет нагляднее. Попробуем визуализировать данные из таблицы.
Решение
Для начала попробуем расставить все населённые пункты, можно это сделать хаотично, а можно по кругу.
После этого надо простроить дороги между населённые пунктами и подписать их протяжённость. Для этого необходимо воспользоваться данными из таблицы. Если на пересечении населённых пунктов есть число, то между ними есть дорога. Число это показывает протяжённость (расстояние между ними).
Дороги между населёнными пунктами мы построили, осталось подписать протяжённость между ними.
Попробуем найти кратчайший путь между пунктом A и D. Если мы посмотрим визуально, то увидим, что можно попасть из A в D разными путями. Попробуем выписать некоторые:
- A-B-D = 6 + 5 = 11
- A-B-C-D = 6 + 2 + 2 = 10
- A-B-E-D = 6 + 1 + 6 = 13
- A-E-D = 3 + 6 = 9
- A-E-B-C-D = 3 + 1 + 2 + 2 = 8
На удивление путь, в котором было больше всего населённых городов, является кратчайшем путём по протяжённости. Здесь мы нашли кратчайшее расстояние между пунктами. Как можем заметить это путь A-E-B-C-D и расстояние - 8.
Понравилась статья? Хочешь разбираться в информатике, программировании и уметь работать в разных программах? Тогда ставь лайк, подпишись на канал и поделись статьей с друзьями!
Читайте также:
- Информатика ОГЭ №5
- Информатика ОГЭ №6
- Информатика ОГЭ №7
#информатика #огэ #разбор #задания #решение #экзамен
