Книга-тренажер: «Базовая подготовка к ЕГЭ по информатике в компьютерной форме». Авторский курс - страница 3

Решение:

Из вершины B выходит 5 ребер, значит, в таблице соответствующий пункт должен иметь дороги в 5 других (строка должна содержать 5 заполненных клеток). Такой пункт в таблице один: П6. На графе из вершины Е выходит 4 ребра, значит, в таблице соответствующий пункт должен иметь дороги в 4 других (строка должна содержать 4 заполненные клетки). Такой пункт в таблице один: П4. Таким образом, нам нужно найти расстояние между П6 и П4. На пересечении П6 и П4 находится цифра 20.

Ответ: 20.

Пример 1.2

На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Известно, что длина дороги ВД меньше дороги ВЕ. Определите длину дороги ГЖ.

Решение: Для начала расставим количество путей, которые выходят из каждой вершины.

Минимальное число путей из вершин – это 2.

Им соответствует вершина А и Ж. Мы видим в таблице, что в П5 есть два пути. Поэтому предположим, что П5=А, тогда П4=Ж. Т. к. П5 пересекается в значении 10 с П6 и П6=3, то П6=Б. Аналогично получаем, что П7=Д. Далее П7 пересекается с П3, то П3=В. Т. к. П6 пересекается с П2, то П2=В, остается, что П3=Е. Осталась одна вершина – это П1=Г. Условие, что ВЕ> ВД, 23> 16. Это условие истинно, значит, наше предположение изначальное, что П5=А, а П4=Ж, а не наоборот – истинное. А если бы было ложное, тогда что? Тогда бы пришлось рисовать заново, предполагая, что П5=Ж, а П4=А. Смотрим по таблице пересечение П1 и П4 – это число 2.

Ответ: 2.

Пример 1.3

На рисунке слева схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.

Определите номера пунктов, соответствующих пунктам З и Ж на графе. В качестве ответа запишите два числа в порядке возрастания без разделителей – найденные номера.

Решение:

Пункт К соединяется с вершинами Г (4 вершины) и В (4 вершины). П8 соединяется как раз с двумя вершинами П1 и П2, каждая из которых имеет по 4 дороги, значит, П8=К. Т. к. П8 соединяется с П1 и П2 имеет четыре вершины, то можно предположить, что П1=В, а П2=Г. П1 соединяется с П5, и т. к. П5 имеет 2 вершины, то П5=З. Ранее выяснили, что П2=Г и П2 пересекается с П3, которая имеет 2 вершины, значит,