Задание 1: анализ информационных моделей (графы и таблицы)
Учимся переводить таблицу в граф, сопоставлять вершины и считать кратчайший путь — это первое задание КЕГЭ.
Информационная модель — это описание объекта или системы на формальном языке (таблица, граф, схема), которое сохраняет нужные для задачи свойства и отбрасывает лишнее.
Что проверяет задание 1
Задание 1 — базовый уровень, 1 первичный балл. На экране дан взвешенный граф: вершины (населённые пункты, обозначенные буквами или цифрами) и рёбра (дороги с длинами). Та же информация дублируется таблицей, но в таблице вершины переставлены и обозначены нейтрально (П1, П2, …). Ваша задача — понять, какая вершина таблицы какой вершине графа соответствует, и ответить на вопрос: чаще всего — найти длину кратчайшего пути между двумя пунктами или длину конкретного маршрута.
Суть задания — не вычисления, а сопоставление двух моделей одного объекта. Граф и таблица описывают одну и ту же сеть дорог; нужно «склеить» их по структуре связей.
Теория: граф и таблица смежности
Граф задают таблицей смежности: строки и столбцы — вершины, на пересечении — длина ребра (или пусто/прочерк, если прямой дороги нет). Для неориентированного графа таблица симметрична относительно главной диагонали.
Ключевая идея сопоставления — степень вершины (сколько у неё рёбер) и набор длин этих рёбер. Если у вершины графа три дороги длиной 2, 5 и 7, то в таблице ей соответствует строка ровно с тремя заполненными ячейками со значениями 2, 5, 7. Так вершины графа однозначно «садятся» на строки таблицы.
| Понятие | Что значит |
| Вершина | пункт сети (город, перекрёсток) |
| Ребро | дорога между двумя пунктами |
| Вес ребра | длина дороги (число в таблице) |
| Степень вершины | число дорог, выходящих из пункта |
Метод решения
- Посчитайте степень каждой вершины в графе (число рёбер) и в таблице (число заполненных ячеек в строке).
- Найдите «особые» вершины: с уникальной степенью или уникальным набором длин рёбер — их сопоставить проще всего.
- От уже сопоставленных вершин идите к соседям: проверяйте, совпадают ли длины общих рёбер.
- Когда соответствие найдено, ответьте на вопрос задачи (длина пути или кратчайший путь).
Если спрашивают именно кратчайший путь, его можно найти вручную перебором коротких маршрутов — вершин обычно 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 — это одно ребро; в таблице оно записано дважды.
- Неверно сопоставляют вершины и берут чужие длины. Всегда перепроверяйте степень: число дорог из пункта обязано совпасть.
- Считают руками и пропускают маршрут. Если вершин много — лучше запустить Дейкстру.
Итог
- Граф и таблица смежности — две записи одной сети; сопоставляйте вершины по степени и набору длин рёбер.
- Неориентированный граф даёт симметричную таблицу; ребро встречается дважды.
- Кратчайший путь надёжнее всего считать алгоритмом Дейкстры — код выше готов к подстановке.
Проверь себя
Три вопроса по уроку. Ответы никуда не идут — это для тебя.
1Граф неориентированный. Что обязательно верно для его таблицы смежности?
2По какому признаку проще всего сопоставить вершину графа со строкой таблицы?
3В таблице прямая дорога A–F равна 10, но через другие пункты можно доехать за 9. Каков кратчайший путь A→F?