Задача: ACC66D

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. | | A | B | C | D | E | | --- | --- | --- | --- | --- | --- | | A | | 4 | | | | | B | 4 | | 4 | | 1 | | C | | 4 | | 1 | 2 | | D | | | 1 | | 3 | | E | | 1 | 2 | 3 | | Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз. --- Номер задачи: ACC66D 📚 # Тема 04. Формальные описания реальных объектов (Графы и таблицы) На ОГЭ эта тема проверяет умение работать с графами: сопоставлять граф с таблицей смежности, находить кратчайший путь, считать степени вершин. --- ## 1. Основные понятия теории графов | Термин | Описание | |--------|----------| | **Граф** | Схема из точек (вершин) и линий (рёбер) между ними | | **Вершина** | Точка на схеме (город, пункт, узел) | | **Ребро** | Линия, соединяющая две вершины (дорога, связь) | | **Дуга** | Ребро со стрелкой — указывает направление | | **Вес ребра** | Число на ребре (расстояние, время, стоимость) | | **Степень вершины** | Количество рёбер, выходящих из вершины | | **Ориентированный граф** | Граф, где все рёбра — дуги (со стрелками) | > **Совет:** Степень вершины легко посчитать: просто считайте линии, которые "касаются" этой точки. --- ## 2. Таблица смежности (матрица весов) Таблица смежности — удобная запись графа в виде таблицы. - Строки и столбцы = вершины. - В ячейке [i][j] — вес ребра от i до j (или "–" / 0, если ребра нет). **Пример:** | | А | Б | В | Г | |---|---|---|---|---| | **А** | – | 5 | 3 | – | | **Б** | 5 | – | – | 2 | | **В** | 3 | – | – | 4 | | **Г** | – | 2 | 4 | – | Граф: А–Б(5), А–В(3), Б–Г(2), В–Г(4). > **Совет:** Если таблица симметрична относительно диагонали → граф неориентированный (дороги двусторонние). Можно смотреть только верхнюю или нижнюю половину. --- ## 3. Алгоритм сопоставления таблицы и графа Когда вершины в таблице называются П1, П2... а на графе — А, Б, В... **Алгоритм:** 1. Для каждой вершины **на графе** подсчитайте степень (количество рёбер). 2. Для каждой строки **в таблице** подсчитайте количество заполненных ячеек (не "–"). 3. Сопоставьте по степеням. Если только у одного объекта степень = 4 → найдено совпадение. 4. После нахождения одного — остальные определяются по рёбрам. > **Совет:** Начинайте с уникальных вершин — тех, у кого степень встречается только один раз. --- ## 4. Нахождение кратчайшего пути ### Метод перебора ("Дерево путей") Для небольших графов (4–6 вершин) — перебираем все пути вручную. **Пример.** Граф: А–Б(5), А–В(3), Б–Г(2), В–Г(4). Найти кратчайший путь А → Г. | Путь | Длина | |------|-------| | А → Б → Г | 5 + 2 = **7** | | А → В → Г | 3 + 4 = **7** | Оба пути дают 7 — кратчайший путь = **7**. ### Алгоритм Дейкстры (для сложных задач) 1. Присвоить начальной вершине метку **0**, всем остальным — **∞**. 2. Из текущей вершины "посетить" всех соседей, обновить их метки (текущая + вес ребра). 3. Выбрать вершину с **наименьшей** необработанной меткой — она становится текущей. 4. Повторять до достижения конечной вершины. > **Совет:** На ОГЭ граф обычно небольшой (5–7 вершин), поэтому полный перебор путей работает отлично. Алгоритм Дейкстры — запасной вариант. --- ## 5. Типичные задачи ### "Найдите кратчайший путь из А в Д" 1. Выпишите все возможные маршруты (следите за стрелками, если граф ориентированный!). 2. Сложите веса рёбер для каждого маршрута. 3. Выберите наименьший результат. ### "Какой вершине соответствует П3?" 1. Найдите степень П3 в таблице (количество заполненных ячеек в строке или столбце). 2. Найдите вершину на графе с такой же степенью. 3. Проверьте по рёбрам. --- ## 6. Типичные ошибки - **Считать движение против стрелки.** В ориентированном графе дуга А→Б означает: можно идти только из А в Б, но не наоборот! - **Не проверить все пути.** Короткий по виду путь может быть длиннее по весам. - **Перепутать степень и вес.** Степень — количество рёбер. Вес — число на ребре. - **Считать рёбра дважды.** В неориентированном графе ребро А–Б засчитывается и для А, и для Б. --- ## 7. Лайфхаки для ОГЭ > **Совет:** Выпишите степени всех вершин столбиком — это помогает быстро сопоставить таблицу и граф. > **Совет:** Перед тем как считать пути, убедитесь — граф ориентированный или нет? Это меняет всё. > **Совет:** Если нужно найти кратчайший путь "с пересадкой через X", сначала найдите кратчайший до X, потом от X до финиша. Сложите.