Задание 1. Информатика. ЕГЭ. Статград. 01.04.2025-1

Просмотры: 230
Изменено: 1 апреля 2025

На рисунке схема дорог N-ского района изображена в виде графа, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

Номер пункта
1234567
1 **
2 ***
3* *
4** *
5** *
6* *
7*** 
 

Каждому населённому пункту на схеме соответствует номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам C и E на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Решение:

Python


from itertools import permutations

graph = {'A': set('BCF'),
         'B': set('AC'),
         'C': set('ABE'),
         'D': set('EFG'),
         'E': set('CDG'),
         'F': set('AD'),
         'G': set('ED')}
templ = {1: [4, 5],
         2: [3, 4, 7],
         3: [2, 7],
         4: [1, 2, 5],
         5: [1, 4, 6],
         6: [5, 7],
         7: [2, 3, 6]}

for p in permutations('ABCDEFG'):
    chk = {p[k-1]: set([p[i-1] for i in v]) for k, v in templ.items()}
    if chk == graph:
        print('1 2 3 4 5 6 7')
        print(*p)

Вывод программы

1 2 3 4 5 6 7
B E G C A F D
1 2 3 4 5 6 7
G C B E D F A

Ответ: \(24\)