Определение длины дороги по графу и таблице
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
|---|---|---|---|---|---|---|---|
| П1 | 15 | 15 | 9 | 7 | |||
| П2 | 15 | ||||||
| П3 | 15 | 12 | 20 | ||||
| П4 | 9 | 12 | 14 | 10 | |||
| П5 | 7 | ||||||
| П6 | 14 | ||||||
| П7 | 20 | 10 |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта К в пункт Г. В ответе запишите целое число – так, как оно указано в таблице.
Как сопоставлять граф и таблицу
Вершина графа обозначает населённый пункт, а ребро — прямую дорогу между двумя пунктами. Длина дороги записана в соответствующей ячейке таблицы.
Степень вершины — число выходящих из неё дорог. На схеме нужно посчитать рёбра, а в строке таблицы — заполненные ячейки с расстояниями.
Пустая ячейка означает отсутствие прямой дороги, а не дорогу нулевой длины. Таблица для двусторонних дорог симметрична: расстояние из одного пункта в другой не зависит от направления.
Порядок действий
- Найдите вершины с уникальным числом дорог.
- Если степени совпадают, сравните соседей: их степени и связи между ними.
- Определите номера обоих концов искомой дороги.
- Прочитайте значение на пересечении нужных строки и столбца.
Полностью восстанавливать все обозначения не обязательно. Достаточно однозначно определить концы искомого ребра.
1. Сравним степени вершин
На схеме у Б, Е и К по одной дороге; у Д — две; у А — три; у В и Г — по четыре.
| Пункт в таблице | Соседние пункты | Число дорог |
|---|---|---|
| П1 | П2, П3, П4, П5 | 4 |
| П2 | П1 | 1 |
| П3 | П1, П4, П7 | 3 |
| П4 | П1, П3, П6, П7 | 4 |
| П5 | П1 | 1 |
| П6 | П4 | 1 |
| П7 | П3, П4 | 2 |
Единственная вершина степени 3 — А, поэтому ей соответствует П3. Единственная вершина степени 2 — Д, поэтому ей соответствует П7.
2. Найдём пункты Г и К
У пункта Д два соседа: А и Г. В строке П7 указаны дороги к П3 и П4. Поскольку А — это П3, пункт Г — это П4.
Пункт К имеет только одну дорогу и соединён с Г. В таблице единственный пункт с одной дорогой к П4 — П6. Значит, К соответствует П6.
3. Прочитаем длину дороги
Дорога К–Г соответствует дороге П6–П4. В таблице на пересечении строки П6 и столбца П4 стоит число 14. Следовательно, длина дороги равна 14 км.
Похожая задача 1. Дорога к конечному пункту
На схеме показаны дороги между четырьмя пунктами. В таблице перечислены все дороги с независимой нумерацией пунктов. Найдите длину дороги В–Г в километрах.
| Дорога | Длина, км |
|---|---|
| П1–П2 | 6 |
| П1–П3 | 8 |
| П2–П3 | 10 |
| П2–П4 | 13 |
Краткое решение. В — единственная вершина с тремя дорогами, ей соответствует П2. Г — единственная вершина с одной дорогой, ей соответствует П4. Длина дороги П2–П4 равна 13 км.
Ответ: 13.
Похожая задача 2. Связь двух центральных пунктов
Нумерация пунктов в таблице не связана с буквами на схеме. В таблице перечислены все дороги. Найдите длину дороги А–Б в километрах.
| Дорога | Длина, км |
|---|---|
| П1–П4 | 5 |
| П2–П3 | 11 |
| П2–П4 | 16 |
| П4–П5 | 9 |
Краткое решение. У А три дороги, поэтому А — П4. У Б две дороги, поэтому Б — П2. Для дороги П4–П2 в таблице указана длина 16 км.
Ответ: 16.
Похожая задача 3. Различаем вершины одинаковой степени
Схема и таблица описывают одну дорожную сеть, но обозначения пунктов выбраны независимо. В таблице перечислены все дороги. Найдите длину дороги В–Е в километрах.
| Дорога | Длина, км |
|---|---|
| П1–П2 | 8 |
| П1–П4 | 12 |
| П2–П3 | 7 |
| П2–П4 | 10 |
| П2–П5 | 6 |
| П4–П6 | 18 |
Краткое решение. А имеет степень 4 и соответствует П2; В имеет степень 3 и соответствует П4. Среди вершин степени 1 только Е соединена с В. В таблице единственный пункт с одной дорогой к П4 — П6. Поэтому искомая дорога — П4–П6, её длина 18 км.
Ответ: 18.