Задание 1: анализ информационных моделей (графы и таблицы)

Учимся переводить таблицу в граф, сопоставлять вершины и считать кратчайший путь — это первое задание КЕГЭ.

Информационная модель — это описание объекта или системы на формальном языке (таблица, граф, схема), которое сохраняет нужные для задачи свойства и отбрасывает лишнее.

Что проверяет задание 1

Задание 1 — базовый уровень, 1 первичный балл. На экране дан взвешенный граф: вершины (населённые пункты, обозначенные буквами или цифрами) и рёбра (дороги с длинами). Та же информация дублируется таблицей, но в таблице вершины переставлены и обозначены нейтрально (П1, П2, …). Ваша задача — понять, какая вершина таблицы какой вершине графа соответствует, и ответить на вопрос: чаще всего — найти длину кратчайшего пути между двумя пунктами или длину конкретного маршрута.

Суть задания — не вычисления, а сопоставление двух моделей одного объекта. Граф и таблица описывают одну и ту же сеть дорог; нужно «склеить» их по структуре связей.

Теория: граф и таблица смежности

Граф задают таблицей смежности: строки и столбцы — вершины, на пересечении — длина ребра (или пусто/прочерк, если прямой дороги нет). Для неориентированного графа таблица симметрична относительно главной диагонали.

Ключевая идея сопоставления — степень вершины (сколько у неё рёбер) и набор длин этих рёбер. Если у вершины графа три дороги длиной 2, 5 и 7, то в таблице ей соответствует строка ровно с тремя заполненными ячейками со значениями 2, 5, 7. Так вершины графа однозначно «садятся» на строки таблицы.

Метод решения

1. Посчитайте степень каждой вершины в графе (число рёбер) и в таблице (число заполненных ячеек в строке).
2. Найдите «особые» вершины: с уникальной степенью или уникальным набором длин рёбер — их сопоставить проще всего.
3. От уже сопоставленных вершин идите к соседям: проверяйте, совпадают ли длины общих рёбер.
4. Когда соответствие найдено, ответьте на вопрос задачи (длина пути или кратчайший путь).

Если спрашивают именно кратчайший путь, его можно найти вручную перебором коротких маршрутов — вершин обычно 6–8. Но надёжнее запустить алгоритм, особенно если граф плотный.

Разбор примера

Пусть дороги такие: A–B = 5, A–C = 3, B–D = 2, C–D = 7, C–E = 4, D–F = 6, E–F = 2. Вопрос: какова длина кратчайшего пути из A в F?

Перечислим разумные маршруты: A→C→E→F = 3+4+2 = 9; A→B→D→F = 5+2+6 = 13; A→C→D→F = 3+7+6 = 16. Минимум — 9. Чтобы не считать руками и не пропустить маршрут, применим алгоритм Дейкстры.

Решение на Python

Алгоритм Дейкстры из стандартной библиотеки писать не нужно — реализуем «руками», он короткий. На каждом шаге берём ещё не обработанную вершину с минимальным расстоянием и улучшаем расстояния до её соседей.

INF = float('inf')

# Рёбра неориентированного графа: (вершина1, вершина2): длина
edges = {
    ('A','B'): 5, ('A','C'): 3, ('B','D'): 2, ('C','D'): 7,
    ('C','E'): 4, ('D','F'): 6, ('E','F'): 2,
}

nodes = sorted({n for e in edges for n in e})
adj = {n: {} for n in nodes}
for (u, v), w in edges.items():
    adj[u][v] = w
    adj[v][u] = w          # граф неориентированный — ребро в обе стороны

def dijkstra(start):
    dist = {n: INF for n in nodes}
    dist[start] = 0
    used = set()
    while len(used) < len(nodes):
        cur = min((n for n in nodes if n not in used), key=lambda n: dist[n])
        used.add(cur)
        for nb, w in adj[cur].items():
            if dist[cur] + w < dist[nb]:
                dist[nb] = dist[cur] + w
    return dist

d = dijkstra('A')
print("Кратчайшие расстояния от A:", d)
print("Кратчайший путь A->F =", d['F'])

Вывод:

Кратчайшие расстояния от A: {'A': 0, 'B': 5, 'C': 3, 'D': 7, 'E': 7, 'F': 9}
Кратчайший путь A->F = 9

Подставьте сюда рёбра своего варианта (длины берите из таблицы или графа — без разницы, они совпадают) и сразу получите ответ. Главное — правильно перенести рёбра.

Типичные ошибки

• Путают «кратчайший путь» и «прямое ребро». Если в таблице A–F стоит 10, а через E выходит 9 — ответ 9, ведь спрашивают кратчайший путь, а не длину прямой дороги.
• Забывают про симметрию. Дорога A–B и B–A — это одно ребро; в таблице оно записано дважды.
• Неверно сопоставляют вершины и берут чужие длины. Всегда перепроверяйте степень: число дорог из пункта обязано совпасть.
• Считают руками и пропускают маршрут. Если вершин много — лучше запустить Дейкстру.

Итог

• Граф и таблица смежности — две записи одной сети; сопоставляйте вершины по степени и набору длин рёбер.
• Неориентированный граф даёт симметричную таблицу; ребро встречается дважды.
• Кратчайший путь надёжнее всего считать алгоритмом Дейкстры — код выше готов к подстановке.