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