Задание 1 ЕГЭ по информатике

1. 1. У B ровно 3 соседа (степень 3), у пункта 2 в таблице заполнено 2 клетки (степень 2).
2. 2. Степени не совпадают → B ≠ 2.
3. 3. Значит номер B нужно искать среди строк с тремя заполненными клетками и набором весов {18, 24, 28}.
4. 4. Только одна строка подходит по всему набору весов — она и есть B.

Ответ: B соответствует той строке таблицы, где ровно три числа и это {18, 24, 28}; пункт 2 (степень 2) — не B.

1. 1. Шаг 1. Считаем степени на схеме. A соединена с B и C — степень 2. B соединена с A, C, D — 3. C: A, B, E — 3. D: B, E, F — 3. E: C, D, F — 3. F: D, E — 2.
2. 2. Шаг 2. Считаем степени в таблице по числу заполненных клеток: у пункта 1 три соседа, у 2 три, у 3 два, у 4 два, у 5 три, у 6 три.
3. 3. Шаг 3. Вершин степени 2 ровно две с каждой стороны: буквы A и F, номера 3 и 4. Значит, A и F — это 3 и 4 в каком-то порядке, а остальные четыре буквы — это 1, 2, 5, 6.
4. 4. Шаг 4. Различаем A и F по набору весов. Строка 3 содержит числа 3 и 2, строка 4 — числа 7 и 5. Весов на схеме нет, но есть другой признак: посмотрим, с кем соединены. Пункт 4 соединён с 1 и 6 — обе вершины степени 3. Пункт 3 соединён с 2 и 5 — тоже степени 3. Портреты пока одинаковы, идём дальше.
5. 5. Шаг 5. Различаем через вторых соседей. Соседи A — это B и C, а B и C соединены между собой. Соседи F — это D и E, и они тоже соединены. Симметрия сохраняется, но она кажущаяся: посмотрим на треугольники. В таблице 1 и 6 соединены (вес 9), 2 и 5 соединены (вес 6) — оба треугольника есть. Значит, различить A и F по одной лишь структуре нельзя, и нужен ещё один признак.
6. 6. Шаг 6. Признак находится в вопросе задания. Нас спрашивают длину A–B и D–E. Возьмём любой из двух вариантов и проверим, даёт ли он согласованную картину целиком. Пусть A = 4. Тогда соседи A — это 1 и 6, то есть {B, C} = {1, 6}. F = 3, его соседи 2 и 5, то есть {D, E} = {2, 5}.
7. 7. Шаг 7. Проверяем оставшиеся рёбра. По схеме B–D и C–E есть, а B–E и C–D нет. В таблице 1 соединена с 2 (вес 4), а с 5 — нет; 6 соединена с 5 (вес 8), а с 2 — нет. Значит, если B = 1, то D = 2, и тогда C = 6, E = 5. Все восемь рёбер сходятся: A–B это 4–1 (7), A–C это 4–6 (5), B–C это 1–6 (9), B–D это 1–2 (4), C–E это 6–5 (8), D–E это 2–5 (6), D–F это 2–3 (3), E–F это 5–3 (2).
8. 8. Шаг 8. Ответ: A–B = 7, D–E = 6, сумма 13. Перебор всех 720 вариантов нумерации показывает, что согласованное соответствие ровно одно: A = 4, B = 1, C = 6, D = 2, E = 5, F = 3. Симметрия из шага 5 была кажущейся — её разрушают веса рёбер.
9. 9. Шаг 9. Вывод для практики: начинайте со степеней, но не останавливайтесь на них. Окончательное решение всегда принимает полная проверка всех рёбер, и делать её надо до того, как записан ответ.

Ответ: A–B = 7, D–E = 6

1. 1.

   from itertools import permutations

   # рёбра схемы: только связи, весов на рисунке нет
   shema = [('A','B'), ('A','C'), ('B','C'), ('B','D'),

   ('C','E'), ('D','E'), ('D','F'), ('E','F')]

   # таблица: вес каждой дороги между номерами
   tablica = {frozenset((1,2)): 4, frozenset((1,4)): 7, frozenset((1,6)): 9,

   frozenset((2,3)): 3, frozenset((2,5)): 6, frozenset((3,5)): 2, frozenset((4,6)): 5, frozenset((5,6)): 8}

   bukvy = 'ABCDEF'
   for p in permutations(range(1, 7)):
       m = dict(zip(bukvy, p))
       if len(shema) != len(tablica):
           continue
       if all(frozenset((m[a], m[b])) in tablica for a, b in shema):
           print(m, 'AB =', tablica[frozenset((m['A'], m['B']))],

   'DE =', tablica[frozenset((m['D'], m['E']))])

2. 2. Шаг 1. Идея грубой силы. Соответствий всего 6! = 720 (для восьми вершин — 40 320), и компьютер проверяет их мгновенно. Никакой изобретательности не требуется: перебираем все нумерации и оставляем те, при которых каждое ребро схемы находится в таблице.
3. 3. Шаг 2. Почему frozenset. Дорога между 1 и 2 — та же, что между 2 и 1: граф неориентированный. Множество из двух номеров не зависит от порядка, а frozenset можно использовать как ключ словаря, в отличие от обычного множества.
4. 4. Шаг 3. Почему проверка длины. Совпадения числа рёбер недостаточно для равенства графов, но без него перебор мог бы принять соответствие, при котором в таблице есть лишняя дорога, отсутствующая на схеме. Сравнение количеств закрывает этот случай: если все рёбра схемы нашлись и общее число рёбер совпало, графы совпадают.
5. 5. Шаг 4. Программа печатает одну строку: соответствие A = 4, B = 1, C = 6, D = 2, E = 5, F = 3 и сразу ответы AB = 7 и DE = 6. Если бы решений оказалось несколько, программа напечатала бы все — и стало бы видно, совпадают ли ответы.
6. 6. Шаг 5. Когда этот способ выручает. На экзамене задание 1 базового уровня и решается за три минуты руками. Но если граф симметричный и степени не различают вершины, ручной разбор превращается в перебор случаев, а программа делает его за секунду. Двенадцать строк кода — разумная страховка для задания, которое стоит балл.
7. 7. Шаг 6. Мелкая, но важная деталь ввода: рёбра схемы выписывают по рисунку, а не по таблице. Если переписать их из таблицы, программа проверит таблицу саму на себя и напечатает все 720 перестановок или ни одной.

Ответ: Единственное соответствие; AB = 7, DE = 6

1. 1. Шаг 1. Ставим метку 0 у стартовой вершины A. Метка вершины — это длина наилучшего пути к ней из A, найденного к данному моменту.
2. 2. Шаг 2. Соседи A. По дороге длиной 7 получаем метку B = 7, по дороге длиной 5 — метку C = 5. Других соседей у A нет.
3. 3. Шаг 3. Выбираем вершину с наименьшей меткой из непросмотренных — это C = 5 — и размечаем её соседей. Через C: B получает 5 + 9 = 14, но у B уже стоит 7 — оставляем 7, меньшее. E получает 5 + 8 = 13.
4. 4. Шаг 4. Следующая наименьшая метка — B = 7. Через B: D получает 7 + 4 = 11, C уже просмотрена.
5. 5. Шаг 5. Следующая — D = 11. Через D: E получает 11 + 6 = 17, но у E уже 13 — оставляем 13. F получает 11 + 3 = 14.
6. 6. Шаг 6. Следующая — E = 13. Через E: F получает 13 + 2 = 15, но у F уже 14 — оставляем 14.
7. 7. Шаг 7. Ответ: кратчайший путь из A в F равен 14, и идёт он A → B → D → F (7 + 4 + 3). Путь A → C → E → F короче по числу дорог, но длиннее по километрам: 5 + 8 + 2 = 15.
8. 8.

   Шаг 8. Программа, которая делает то же самое:

   graf = {}
   for (u, v), w in {('A','B'):7, ('A','C'):5, ('B','C'):9, ('B','D'):4,

   ('C','E'):8, ('D','E'):6, ('D','F'):3, ('E','F'):2}.items():

       graf.setdefault(u, {})[v] = w
       graf.setdefault(v, {})[u] = w

   metki = {'A': 0}
   prosmotreno = set()
   while len(prosmotreno) < len(graf):
       v = min((x for x in metki if x not in prosmotreno), key=lambda x: metki[x])
       prosmotreno.add(v)
       for u, w in graf[v].items():
           if metki[v] + w < metki.get(u, 10**9):
               metki[u] = metki[v] + w
   print(metki)

9. 9. Шаг 9. Программа печатает метки всех вершин: A = 0, C = 5, B = 7, D = 11, E = 13, F = 14 ✔ Заметьте, что граф строится в обе стороны (graf[u][v] и graf[v][u]): дороги двусторонние, и забыть об этом — значит получить бесконечность там, где путь есть.
10. 10. Шаг 10. Ключевой момент разметки — строка сравнения: новая метка записывается, только если она меньше уже стоящей. Именно это и отличает поиск кратчайшего пути от простого сложения весов вдоль первого попавшегося маршрута.

Ответ: 14 (путь A → B → D → F)