Четвертое задание в ОГЭ по информатике заключается в нахождении кратчайшего пути между населенными пунктами. Мы предлагаем два способа решения этой задачи, но они очень похожи, на самом деле. И как всегда будем разбирать на примере, так как каких-то теоретических знаний здесь не требуется, только внимательность и логика. 1 способ (построение дерева). Нужно найти кратчайший путь из пункта А в пункт Е, для этого надо перебрать все пути. Для того, чтобы не упустить ни одного варианта дороги, построим дерево: Всего получилось 5 дорог из пункта А в пункт Е...

Задачи на графы встречаются в ЕГЭ по информатике в разных форматах: в заданиях на маршруты, таблицы, схемы и анализ связей. Многие ученики их боятся, потому что слово «граф» звучит страшно и ассоциируется с чем-то из университетской математики. На деле большинство задач ЕГЭ на графы решаются одним методом — и когда он освоен, задача становится почти механической. Граф — это набор вершин (точек) и рёбер (связей между точками). Всё. Никакой магии. Когда вы рисуете схему городов с дорогами между ними, или рисуете связи между людьми в социальной сети — вы рисуете граф...