ЕГЭ · ЗАДАНИЕ 1
Графы и таблицы · №31209
Таблица из условия ЕГЭ — протяжённости прямых дорог (км)
| Номер пункта | ||||||||
|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
| Номер пункта | 1 | 8 | 5 | 3 | ||||
| 2 | 39 | 53 | 21 | |||||
| 3 | 8 | 39 | 30 | |||||
| 4 | 53 | 30 | 2 | |||||
| 5 | 13 | 1 | ||||||
| 6 | 5 | 21 | 13 | |||||
| 7 | 3 | 2 | 1 | |||||
Граф из условия — какие пункты соединены дорогами
Задание. Сопоставьте буквы на графе с номерами в таблице. Определите, какова сумма протяжённостей дорог из пункта B в пункт C и из пункта A в пункт C. В ответ запишите только число.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 8
Разбор графа и таблицы
- В каждой строке таблицы посчитайте непустые клетки: это число соседей вершины. На графе степени вершин: A: 3; B: 3; C: 3; D: 3; E: 3; F: 2; G: 3.
- Начните с вершин с необычной степенью, затем проверьте их соседей. Букве и номеру должны соответствовать одинаковые связи со всеми уже найденными вершинами. Пересечение линий без отмеченной вершины не создаёт новую дорогу.
- Допустимых сопоставлений 2; симметрия графа не меняет искомую сумму. Ниже приведено одно из них. Проверьте в таблице каждое ребро из столбца «Соседи».
| Буква | Номер | Соседи на графе | Номера соседей |
|---|---|---|---|
| A | 6 | C, D, F | 1, 2, 5 |
| B | 7 | C, E, F | 1, 4, 5 |
| C | 1 | A, B, G | 6, 7, 3 |
| D | 2 | A, E, G | 6, 4, 3 |
| E | 4 | B, D, G | 7, 2, 3 |
| F | 5 | A, B | 6, 7 |
| G | 3 | C, D, E | 1, 2, 4 |
BC: строка 7, столбец 1, длина 3 км; AC: строка 6, столбец 1, длина 5 км.
Складываем только две указанные прямые дороги: 3 + 5 = 8 км. Искать кратчайший маршрут между этими пунктами не требуется.