8) На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта А в пункт Г. В ответе запишите целое число – так как оно указано в таблице.

Для решения этой задачи нам нужно сопоставить точки на графе с соответствующими строками/столбцами в таблице. Будем анализировать степени вершин (количество дорог, выходящих из точки) на графе:

• Вершина А имеет степень 3 (соединена с Б, Г, Д).
• Вершина Б имеет степень 2 (соединена с А, В, Е).
• Вершина В имеет степень 3 (соединена с Б, Г, Е).
• Вершина Г имеет степень 4 (соединена с А, В, Д, К).
• Вершина Д имеет степень 2 (соединена с А, Г).
• Вершина Е имеет степень 2 (соединена с Б, В).
• Вершина К имеет степень 1 (соединена с Г).

Теперь посмотрим на таблицу и найдем строку или столбец, сумма длин дорог из которой соответствует степени вершины:

Анализ таблицы (построчно):

• П1: 7 (только одна дорога) - степень 1.
• П2: 7 + 8 + 3 + 4 = 22.
• П3: 8 + 11 + 6 = 25.
• П4: 11 + 5 = 16.
• П5: 3 + 6 + 5 + 9 = 23.
• П6: 4.
• П7: 9.

Важно: В таблице есть пустые клетки и клетки с серым фоном. Это означает, что между этими пунктами нет прямой дороги. На графе такая же ситуация - отсутствующие соединения.

Сопоставление:

1. П1 (дорога 7) имеет только одну связь. На графе К имеет степень 1. Значит, К соответствует П1.
2. П6 (дорога 4) имеет только одну связь. На графе Е имеет степень 2. Не подходит.
3. П7 (дорога 9) имеет только одну связь. На графе Е имеет степень 2. Не подходит.
4. П4 (дороги 11, 5) имеет две связи.
5. П6 (дорога 4) имеет одну связь.
6. П7 (дорога 9) имеет одну связь.

Давайте попробуем сопоставить по количеству связей на графе и данным в таблице.

Вершины на графе по степени:

• К: 1
• Д, Е: 2
• Б, В: 3
• А: 4

Проверяем строки/столбцы таблицы, где есть числа (не пустые и не серые):

• П1: 7 (1 значение) -> может быть К
• П6: 4 (1 значение) -> может быть К
• П7: 9 (1 значение) -> может быть К
• П2: 7, 8, 3, 4 (4 значения) -> может быть А
• П3: 8, 11, 6 (3 значения) -> может быть Б или В
• П4: 11, 5 (2 значения) -> может быть Д или Е
• П5: 3, 6, 5, 9 (4 значения) -> может быть А

Уточняем:

Если К = П1 (7), то эта дорога длиной 7.

Если Д или Е = П4 (11, 5), то эти дороги имеют длины 11 и 5. На графе Д и Е имеют степень 2, а у П4 только 2 дороги указаны (11 и 5).

Если Б или В = П3 (8, 11, 6), то эти пункты имеют 3 дороги.

Если А = П2 (7, 8, 3, 4) или П5 (3, 6, 5, 9). У А степень 4.

Пробуем сопоставить А и Г.

А имеет 4 связи, Г имеет 4 связи.

П2 и П5 имеют по 4 значения.

П3 и П5 имеют по 3 значения.

П4 имеет 2 значения.

П1, П6, П7 имеют по 1 значению.

Сопоставление вершин графа с пунктами таблицы:

• К (1 связь): может быть П1 (7), П6 (4), П7 (9).
• Д (2 связи): может быть П4 (11, 5).
• Е (2 связи): может быть П4 (11, 5).
• Б (3 связи): может быть П3 (8, 11, 6).
• В (3 связи): может быть П3 (8, 11, 6).
• А (4 связи): может быть П2 (7, 8, 3, 4) или П5 (3, 6, 5, 9).
• Г (4 связи): может быть П2 (7, 8, 3, 4) или П5 (3, 6, 5, 9).

Рассмотрим дорогу А-Г.

Если А = П2, а Г = П5, то дорога А-Г = 8 (из П2) и 6 (из П5). Не совпадает.

Если А = П5, а Г = П2, то дорога А-Г = 3 (из П5) и 7 (из П2). Не совпадает.

Если А = П2 (7, 8, 3, 4) и Г = П3 (8, 11, 6)

Из П2 есть дорога 8, из П3 есть дорога 8. Это возможно, если А=П2, Г=П3, дорога А-Г = 8.

Проверим это сопоставление:

• К (1 связь) -> П1 (7), П6 (4), П7 (9). Например, К=П1 (7).
• Д (2 связи) -> П4 (11, 5). Д=П4.
• Е (2 связи) -> П4 (11, 5). Е=П4.
• Б (3 связи) -> П3 (8, 11, 6). Б=П3.
• В (3 связи) -> П3 (8, 11, 6). В=П3.
• А (4 связи) -> П2 (7, 8, 3, 4) или П5 (3, 6, 5, 9). А=П2.
• Г (4 связи) -> П2 (7, 8, 3, 4) или П5 (3, 6, 5, 9). Г=П5.

Но! Если А=П2, Б=П3, В=П3, Г=П5, Д=П4, Е=П4, К=П1:

Дорога А-Г: В таблице П2-П5 = 3. На графе А-Г - ?

Снова пробуем сопоставить А и Г:

А (4 связи) и Г (4 связи). Оба пункта должны соответствовать строкам/столбцам с 4 значениями: П2 (7, 8, 3, 4) и П5 (3, 6, 5, 9).

Если А = П2, а Г = П5, то длина дороги А-Г равна значению П2-П5 в таблице, которое равно 3.

Если А = П5, а Г = П2, то длина дороги А-Г равна значению П5-П2 в таблице, которое равно 3.

Проверим это сопоставление:

• А = П2 (7, 8, 3, 4)
• Г = П5 (3, 6, 5, 9)

Значит, дорога между А и Г имеет протяженность 3.

Попробуем проверить остальные пункты:

• К (1 связь): П1 (7), П6 (4), П7 (9). Возьмем К = П1 (7).
• Д (2 связи): П4 (11, 5). Возьмем Д = П4.
• Е (2 связи): Если Д=П4, то Е не может быть П4.

Взглянем на граф:

Г соединено с А, В, Д, К.

А соединено с Б, Г, Д.

Сопоставим П2 и П5 с А и Г.

А=П2 (7, 8, 3, 4)

Г=П5 (3, 6, 5, 9)

Дорога А-Г = 3.

Теперь ищем соответствия для других вершин:

К (1 связь): П1(7), П6(4), П7(9). Пусть К=П1 (7).

Д (2 связи): П4(11, 5). Пусть Д=П4.

Е (2 связи): Если Д=П4, то Е не может быть П4. Е может быть другой строкой с 2 значениями, но таких нет.

Пересмотрим:

Вершины с 4 связями: А, Г. Строки с 4 значениями: П2 (7, 8, 3, 4) и П5 (3, 6, 5, 9).

Вершины с 3 связями: Б, В. Строка с 3 значениями: П3 (8, 11, 6).

Вершины с 2 связями: Д, Е. Строка с 2 значениями: П4 (11, 5).

Вершины с 1 связью: К. Строки с 1 значением: П1 (7), П6 (4), П7 (9).

Сопоставление:

• А и Г = П2 и П5 (в любом порядке).
• Б и В = П3 (только одна строка с 3 значениями).
• Д и Е = П4 (только одна строка с 2 значениями).
• К = П1 или П6 или П7 (одна из строк с 1 значением).

Найдем дорогу А-Г.

Если А = П2, а Г = П5, то дорога А-Г = 3 (значение в ячейке П2-П5).

Если А = П5, а Г = П2, то дорога А-Г = 3 (значение в ячейке П5-П2).

В обоих случаях дорога А-Г = 3.

Проверим остальные связи:

• А=П2 (7, 8, 3, 4)
• Г=П5 (3, 6, 5, 9)
• Б/В=П3 (8, 11, 6)
• Д/Е=П4 (11, 5)
• К=П1/П6/П7 (7/4/9)

Дорога А-Б:

Если А=П2, Б=П3, то дорога А-Б = 8 (П2-П3).

Дорога А-Д:

Если А=П2, Д=П4, то дорога А-Д = 4 (П2-П4).

Дорога Г-В:

Если Г=П5, В=П3, то дорога Г-В = 6 (П5-П3).

Дорога Г-К:

Если Г=П5, К=П1, то дорога Г-К = 9 (П5-П1).

Дорога В-Е:

Если В=П3, Е=П4, то дорога В-Е = 11 (П3-П4).

Проверим соответствие на графе:

А (связи с Б, Г, Д)

Г (связи с А, В, Д, К)

Дорога А-Г = 3.

Ответ: 3