Присоединиться

Информатика·Графы и таблицы·9–11 класс

Как сопоставить таблицу и схему дорог и найти кратчайший путь

Условие

На схеме показано, какие населённые пункты соединены дорогами, но длины не указаны: А соединён с Б, В, Г и Д; В соединён с Г и Е; Г соединён с Д (всего 7 дорог, все двусторонние). Те же самые дороги записаны в таблице с длинами в километрах, но пункты в ней обозначены П1–П6 в неизвестном порядке (0 — дороги нет, прочерк — диагональ). Строка П1: —, 0, 6, 0, 0, 0; строка П2: 0, —, 3, 8, 0, 0; строка П3: 6, 3, —, 5, 2, 0; строка П4: 0, 8, 5, —, 4, 0; строка П5: 0, 0, 2, 4, —, 7; строка П6: 0, 0, 0, 0, 7, —. Определите длину кратчайшего пути из Б в Е.

Ответ

15 км (маршрут Б–А–В–Е)

Решение по шагам

  1. Шаг 1. По чему вообще сопоставлять схему и таблицу

    Названия в таблице скрыты, но структура сети одна и та же. Значит, надёжный признак — степень пункта, то есть число дорог, которые из него выходят. У соответствующих друг другу пунктов степени обязаны совпадать.

    Таблицу удобно переписать:

    П1П2П3П4П5П6
    П1—06000
    П20—3800
    П363—520
    П4085—40
    П50024—7
    П600007—

  2. Шаг 2. Считаем степени в схеме и в таблице

    По схеме: А — 4 дороги (Б, В, Г, Д); Б — 1; В — 3 (А, Г, Е); Г — 3 (А, В, Д); Д — 2 (А, Г); Е — 1 (В).

    По таблице (число ненулевых клеток в строке): П1 — 1; П2 — 2; П3 — 4; П4 — 3; П5 — 3; П6 — 1.

    Наборы совпали: 4, 3, 3, 2, 1, 1. Сразу однозначно определяются два пункта: П3 = А (единственная степень 4) и П2 = Д (единственная степень 2).

Осталось ещё 3 шага — откроются после входа:

  • Шаг 3. Достраиваем соответствие по соседям
  • Шаг 4. Выписываем длины дорог
  • Шаг 5. Ищем кратчайший путь из Б в Е
Получить полное решение

Бесплатно · займёт минуту

Частые ошибки

  • Сопоставляют пункты «по порядку»: П1 = А, П2 = Б и так далее.

  • Останавливаются, определив только пункты с уникальными степенями, и не различают П1 и П6 по соседям.

  • Путают степень пункта с суммой длин его дорог.

  • Проверяют только два-три маршрута из Б в Е и не замечают прямой дороги А–В в 2 км.

  • Забывают, что в таблице каждая дорога записана дважды, и насчитывают 14 дорог вместо 7.

Другие задачи по теме «Графы и таблицы»

Сколько путей из А в К в графе с односторонними дорогами9–11 классКак по таблице найти количество дорог и общую длину сети9–11 классКак найти кратчайший путь между городами по схеме дорог9–11 классСколько путей из А в М не проходят через город Г9–11 классПодсчёт путей в ориентированном графе по таблице смежности9–11 класс
Похожая задача?Сфотографируйте своё условие — ИИ разберёт его по шагам так же