1. Таблицы и графы: однозначное соотнесение

Сопоставим вершины графа с номерами пунктов в таблице по количеству выходящих из них дорог.

На графе:

• из пунктов Б, Е и К выходит по одной дороге;
• из пункта Д выходят две дороги;
• из пункта А выходят три дороги;
• из пунктов В и Г выходят по четыре дороги.

В таблице:

• пункты $2$, $5$ и $6$ соединены только с одним пунктом;
• пункт $7$ соединён с двумя пунктами;
• пункт $3$ соединён с тремя пунктами;
• пункты $1$ и $4$ соединены с четырьмя пунктами.

Следовательно, $А=3,$ $Д=7,$ а пунктам В и Г соответствуют номера $1$ и $4$.

Определим, какой из них является пунктом В. На графе пункт В соединён сразу с двумя конечными пунктами — Б и Е. В таблице пункт $4$ соединён с двумя пунктами, из которых выходит только по одной дороге, — с пунктами $5$ и $6$.

Значит, $В=4,$ $Г=1.$

Пункт А соответствует номеру $3$, а пункт Г — номеру $1$. В таблице на пересечении строки $3$ и столбца $1$ указано расстояние $7$ км.

В графе только пункты $A$ и $C$ имеют по две дороги. Остальные пункты имеют по три дороги.

В таблице по две дороги выходят только из пунктов $1$ и $5$. Следовательно, ${A,C}={1,5}$.

Пункты $A$ и $C$ имеют общего соседа — пункт $F$. В таблице пункты $1$ и $5$ также имеют общего соседа — пункт $4$. Поэтому $F=4$.

Третьим соседом пункта $F$ является пункт $D$. В таблице пункт $4$ соединён с пунктами $1$, $5$ и $6$. Значит, $D=6$.

Пункт $D$ соединён с пунктами $E$, $B$ и $F$. В таблице пункт $6$ соединён с пунктами $3$, $4$ и $7$. Следовательно, ${E,B}={3,7}$.

Пункт $E$ соединён с пунктом $A$, имеющим только две дороги. В таблице пункт $7$ соединён с пунктом $5$, имеющим только две дороги. Поэтому $E=7,\quad A=5$.

Тогда $B=3,\quad C=1$.

Пункт $C$ соединён с пунктами $F$ и $G$. В таблице пункт $1$ соединён с пунктами $4$ и $8$. Так как $F=4$, получаем $G=8$.

Оставшемуся пункту $H$ соответствует номер $2$.

Таким образом, $C=1,\quad G=8,\quad H=2,\quad E=7$.

По таблице протяжённость дороги между пунктами $1$ и $8$ равна $49$ км, а между пунктами $2$ и $7$ — $19$ км.

Найдём сумму: $49+19=68$.

Сопоставим вершины графа с номерами пунктов в таблице по количеству дорог, выходящих из каждой вершины.

На графе:

• из пункта А выходит одна дорога;
• из пунктов В и Е выходят по две дороги;
• из пунктов Г и К выходят по три дороги;
• из пункта Б выходят четыре дороги;
• из пункта Д выходят пять дорог.

В таблице:

• пункт $3$ соединён только с одним пунктом;
• пункты $1$ и $2$ соединены с двумя пунктами;
• пункты $5$ и $7$ соединены с тремя пунктами;
• пункт $6$ соединён с четырьмя пунктами;
• пункт $4$ соединён с пятью пунктами.

Следовательно, $А=3,\quad Б=6,\quad Д=4$.

Пункт В соединён с пунктами Б и Д. В таблице из двух вершин степени $2$ пункт $2$ соединён с пунктами $6$ и $4$. Поэтому $В=2$.

Значит, оставшемуся пункту степени $2$ соответствует вершина Е: $Е=1$.

Таким образом, пункту Д соответствует номер $4$, а пункту Е — номер $1$.

В таблице на пересечении строки $4$ и столбца $1$ указано расстояние $9$ км.

На графе пункты $А$, $Н$, $Е$ и $D$ имеют по две дороги, а пункты $В$, $С$, $F$ и $G$ — по три дороги.

В таблице по две дороги выходят из пунктов $2$, $4$, $7$ и $8$, а по три дороги — из пунктов $1$, $3$, $5$ и $6$.

Пункт $F$ — единственная вершина степени $3$, соединённая с тремя вершинами степени $2$: $Н$, $Е$ и $D$.

В таблице этому условию соответствует пункт $5$, который соединён с пунктами $2$, $4$ и $7$. Следовательно, $F=5$.

На графе только пункты $А$ и $Н$ — соседние вершины степени $2$. В таблице из пунктов степени $2$ соединены между собой только пункты $4$ и $8$. Значит, ${А,Н}={4,8}$.

Пункт $Н$ соединён с пунктом $F$. Так как $F=5$, а из пунктов $4$ и $8$ с пунктом $5$ соединён только пункт $4$, получаем: $Н=4,\quad А=8$.

Пункт $А$ соединён с пунктами $Н$ и $В$. В таблице пункт $8$ соединён с пунктами $4$ и $3$. Следовательно, $В=3$.

Таким образом, $В=3,\quad А=8,\quad Н=4$.

По таблице протяжённость дороги между пунктами $3$ и $8$ равна $42$ км, а между пунктами $4$ и $8$ — $27$ км.

$42+27=69$.

Сопоставим вершины графа с номерами пунктов в таблице по количеству выходящих из них дорог.

На графе:

• из пунктов Б и Е выходит по одной дороге;
• из пунктов А, Д и К выходит по две дороги;
• из пунктов В и Г выходит по четыре дороги.

В таблице:

• пункты $4$ и $5$ соединены с одним пунктом;
• пункты $1$, $2$ и $3$ соединены с двумя пунктами;
• пункты $6$ и $7$ соединены с четырьмя пунктами.

Следовательно, ${\text{В},\text{Г}}={6,7}$.

Пункт Г соединён с тремя вершинами степени $2$: А, Д и К. В таблице пункт $6$ соединён с тремя пунктами степени $2$: $1$, $2$ и $3$. Поэтому $\text{Г}=6$.

Тогда второй вершине степени $4$ соответствует пункт В: $\text{В}=7$.

Пункт В соединён с двумя конечными вершинами Б и Е. В таблице пункт $7$ соединён с конечными вершинами $4$ и $5$. Кроме того, пункт $7$ соединён с пунктом $3$, имеющим степень $2$. Следовательно, $\text{А}=3$.

Таким образом, пункту А соответствует номер $3$, а пункту В — номер $7$.

В таблице на пересечении строки $3$ и столбца $7$ указана протяжённость дороги $12$ км.

Сопоставим вершины графа с номерами пунктов в таблице по количеству выходящих из них дорог.

На графе:

• из пунктов Б, Е и К выходит по одной дороге;
• из пункта Д выходят две дороги;
• из пункта А выходят три дороги;
• из пунктов В и Г выходят по четыре дороги.

В таблице:

• пункты $2$, $4$ и $5$ соединены только с одним пунктом;
• пункт $1$ соединён с двумя пунктами;
• пункт $3$ соединён с тремя пунктами;
• пункты $6$ и $7$ соединены с четырьмя пунктами.

Следовательно, $Д=1,\quad А=3,$ а пунктам В и Г соответствуют номера $6$ и $7$.

Пункт Д соединён с пунктами А и Г. В таблице пункт $1$ соединён с пунктами $3$ и $6$. Так как $А=3$, получаем: $Г=6.$

Пункт К имеет только одну дорогу и соединён с пунктом Г. В таблице из пунктов степени $1$ с пунктом $6$ соединён пункт $2$. Следовательно, $К=2.$

Таким образом, пункту К соответствует номер $2$, а пункту Г — номер $6$.

В таблице на пересечении строки $2$ и столбца $6$ указана протяжённость дороги $9$ км.

Сопоставим вершины графа с номерами пунктов в таблице по количеству выходящих из них дорог.

На графе пункт А соединён со всеми шестью остальными пунктами. В таблице только пункт $2$ соединён с шестью другими пунктами. Следовательно, $А=2$.

Пункты Б и К имеют по две дороги. В таблице по две дороги выходят из пунктов $1$ и $4$. Поэтому ${\text{Б},\text{К}}={1,4}$.

Помимо дорог, ведущих в пункт А, остальные пункты образуют цепочку: $$\text{Б}-\text{В}-\text{Г}-\text{Д}-\text{Е}-\text{К}.$$

В таблице соответствующая цепочка имеет вид: $1-3-5-7-6-4$ или в обратном порядке: $4-6-7-5-3-1$.

Следовательно, пунктам В и Е соответствуют номера $3$ и $6$: ${\text{В},\text{Е}}={3,6}$.

Пункту А соответствует номер $2$. По таблице протяжённость дороги между пунктами $2$ и $3$ равна $5$ км, а между пунктами $2$ и $6$ — $8$ км.

Найдём требуемую сумму: $5+8=13$.

На графе только из пункта $F$ выходят две дороги. Из каждого другого пункта выходят по три дороги.

В таблице только пункт $3$ соединён с двумя пунктами — $1$ и $7$. Следовательно, $F=3$, а пунктам $A$ и $B$, соседним с пунктом $F$, соответствуют номера $1$ и $7$.

Рассмотрим один из возможных вариантов: $A=1,\quad B=7$.

Пункт $A$ соединён с пунктами $F$, $C$ и $E$. В таблице пункт $1$ соединён с пунктами $3$, $4$ и $6$. Поэтому пунктам $C$ и $E$ соответствуют номера $4$ и $6$.

Пункт $B$ соединён с пунктами $F$, $G$ и $E$. В таблице пункт $7$ соединён с пунктами $3$, $2$ и $4$.

Общим соседом пунктов $A$ и $B$, кроме пункта $F$, является пункт $E$. В таблице общим соседом пунктов $1$ и $7$, кроме пункта $3$, является пункт $4$. Следовательно, $E=4$.

Тогда $C=6,\quad G=2$.

Получаем соответствие: $A=1,\quad B=7,\quad C=6,\quad G=2$.

По таблице протяжённость дороги между пунктами $G$ и $B$ равна протяжённости дороги между пунктами $2$ и $7$: $2$ км.

Протяжённость дороги между пунктами $C$ и $A$ равна протяжённости дороги между пунктами $6$ и $1$: $21$ км.

Найдём сумму: $2+21=23$.

При перестановке соответствий $A$ и $B$ слагаемые поменяются местами, но их сумма останется той же.

На графе только из пунктов $A$ и $B$ выходят по две дороги. Из остальных пунктов выходят по три дороги.

В таблице по две дороги выходят только из пунктов $2$ и $3$. Следовательно, ${A,B}={2,3}$.

Пункт $A$ вместе со своими соседями $C$ и $E$ образует треугольник: между пунктами $C$ и $E$ также есть дорога.

В таблице пункт $3$ соединён с пунктами $4$ и $7$, которые соединены между собой. Следовательно, $A=3$.

Пункт $2$ соединён с пунктами $1$ и $5$, между которыми дороги нет. Поэтому $B=2$.

Соседями пункта $A$ являются пункты $C$ и $E$, которым соответствуют номера $4$ и $7$.

Соседями пункта $B$ являются пункты $G$ и $H$, которым соответствуют номера $1$ и $5$.

На графе пункт $E$ соединён с пунктом $H$. В таблице из пунктов $4$ и $7$ с одним из пунктов $1$ и $5$ соединён только пункт $7$: он соединён с пунктом $1$. Следовательно, $E=7,\quad H=1$.

Тогда $C=4,\quad G=5$.

Таким образом, $A=3,\quad C=4,\quad B=2,\quad H=1$.

По таблице протяжённость дороги между пунктами $3$ и $4$ равна $13$ км, а между пунктами $2$ и $1$ — $8$ км.

Найдём сумму: $13+8=21$.

Сопоставим вершины графа с номерами пунктов в таблице по количеству выходящих из них дорог.

На графе:

• из пункта Е выходит одна дорога;
• из пункта А выходят две дороги;
• из пунктов Б, Г и Д выходят по три дороги;
• из пункта В выходят четыре дороги.

В таблице:

• пункт $1$ соединён с одним пунктом;
• пункт $3$ соединён с двумя пунктами;
• пункты $4$, $5$ и $6$ соединены с тремя пунктами;
• пункт $2$ соединён с четырьмя пунктами.

Следовательно, $Е=1,\quad А=3,\quad В=2$.

Пункт А соединён с пунктами Б и В. В таблице пункт $3$ соединён с пунктами $2$ и $6$. Так как $В=2$, получаем: $Б=6$.

Пункт Е соединён только с пунктом Д. В таблице пункт $1$ соединён только с пунктом $4$. Следовательно, $Д=4$.

Пункт В соединён с пунктами А, Б, Г и Д. В таблице пункт $2$ соединён с пунктами $3$, $6$, $5$ и $4$. Уже установлено, что $А=3$, $Б=6$, $Д=4$, поэтому $Г=5$.

Таким образом, $В=2,\quad Г=5$.

В таблице на пересечении строки $2$ и столбца $5$ указана протяжённость дороги $3$ км.

Сопоставим вершины графа с номерами пунктов в таблице по количеству выходящих из них дорог.

На графе из пунктов $B$, $C$ и $G$ выходят по две дороги, а из пунктов $A$, $D$, $E$ и $F$ — по три дороги.

В таблице по две дороги выходят из пунктов $1$, $3$ и $4$, а по три дороги — из пунктов $2$, $5$, $6$ и $7$.

На графе пункты $C$ и $G$ — единственные соседние вершины, из которых выходит по две дороги. В таблице такими вершинами являются пункты $1$ и $3$. Следовательно, ${C,G}={1,3}$.

Пункт $B$ — вершина с двумя дорогами, которая не соединена с другими вершинами степени $2$. Поэтому $B=4$.

Пункт $B$ соединён с пунктами $D$ и $F$. В таблице пункт $4$ соединён с пунктами $2$ и $7$. Значит, ${D,F}={2,7}$.

Пусть $C=1$. Тогда его соседями являются пункты $G$ и $F$. В таблице пункт $1$ соединён с пунктами $3$ и $2$. Следовательно, $G=3,\quad F=2$.

Тогда из равенства ${D,F}={2,7}$ получаем: $D=7$.

Пункт $F$ соединён с пунктами $B$, $C$ и $A$. В таблице пункт $2$ соединён с пунктами $4$, $1$ и $5$. Поэтому $A=5$.

Таким образом, $D=7,\quad B=4,\quad F=2,\quad A=5$.

По таблице протяжённость дороги между пунктами $7$ и $4$ равна $53$ км, а между пунктами $2$ и $5$ — $5$ км.

$53+5=58$.

Сопоставим вершины графа с пунктами таблицы по количеству выходящих из них дорог.

На графе из пунктов Б, Е и К выходит по одной дороге, из пункта Д — две дороги, из пункта А — три дороги, из пунктов В и Г — по четыре дороги.

В таблице пункты П1, П6 и П7 имеют по одной дороге, пункт П4 — две дороги, пункт П3 — три дороги, пункты П2 и П5 — по четыре дороги.

Следовательно, $А=\text{П3},\quad Д=\text{П4}$, а пунктам В и Г соответствуют П2 и П5.

Пункт Д соединён с пунктами А и Г. В таблице П4 соединён с П3 и П5. Так как $А=\text{П3}$, получаем: $Г=\text{П5}$.

Таким образом, дороге А–Г соответствует дорога П3–П5. В таблице её протяжённость равна $6$ км.

На графе из пунктов А, Г и К выходят по две дороги, а из пунктов Б, В, Д и Е — по три дороги.

В таблице по две дороги выходят из пунктов $2$, $3$ и $7$, а по три дороги — из пунктов $1$, $4$, $5$ и $6$.

Пункты Г и К — соседние вершины, из каждой из которых выходят по две дороги. В таблице из вершин степени $2$ соединены между собой пункты $3$ и $7$. Следовательно, ${\text{Г},\text{К}}={3,7}$.

Оставшейся вершине степени $2$ соответствует пункт А: $А=2$.

Пункт А соединён с пунктами Б и Д. В таблице пункт $2$ соединён с пунктами $1$ и $4$. Поэтому ${\text{Б},\text{Д}}={1,4}$.

Следовательно, дороге Б–Д соответствует дорога между пунктами $1$ и $4$. В таблице её протяжённость равна $7$ км.

На графе только из пункта $G$ выходят две дороги. Из остальных пунктов выходят по три дороги.

В таблице только пункт $3$ соединён с двумя пунктами. Следовательно, $G=3$.

Пункт $G$ соединён с пунктами $E$ и $B$. В таблице пункт $3$ соединён с пунктами $4$ и $5$. Значит, ${E,B}={4,5}$.

Пункты $E$ и $B$ имеют ещё одного общего соседа — пункт $C$. В таблице пункты $4$ и $5$, кроме пункта $3$, имеют общего соседа $1$. Следовательно, $C=1$.

Пункт $C$ соединён с пунктами $E$, $B$ и $D$. В таблице пункт $1$ соединён с пунктами $4$, $5$ и $7$. Поэтому $D=7$.

Оставшиеся соседи пункта $D$ — пункты $F$ и $A$. В таблице оставшиеся соседи пункта $7$ — пункты $2$ и $6$. Значит, ${F,A}={2,6}$.

Дороге $F\text{–}A$ соответствует дорога между пунктами $2$ и $6$. Её протяжённость равна $2$ км.

Дороге $D\text{–}C$ соответствует дорога между пунктами $7$ и $1$. Её протяжённость равна $8$ км. $2+8=10$.

На графе из пунктов $A$, $B$, $C$ и $D$ выходят по две дороги, а из пунктов $E$, $F$, $G$ и $H$ — по три дороги.

В таблице по две дороги выходят из пунктов $2$, $3$, $4$ и $5$, а по три дороги — из пунктов $1$, $6$, $7$ и $8$.

На графе пункты $B$ и $D$ — единственная пара соседних вершин, имеющих по две дороги. В таблице такими пунктами являются $2$ и $4$. Следовательно, ${B,D}={2,4}$.

Пункт $D$ соединён с пунктом $F$. В таблице пункт $4$ соединён с пунктом $8$, имеющим три дороги, а пункт $2$ — с пунктом $1$, имеющим три дороги.

На графе пункт $F$ соединён с двумя вершинами степени $3$: с пунктами $H$ и $E$. В таблице пункт $8$ также соединён с двумя вершинами степени $3$: с пунктами $1$ и $7$. Поэтому $D=4,\quad F=8$. Тогда $B=2,\quad H=1$.

Вершины степени $3$ на графе образуют цепочку $H-F-E-G$.

В таблице соответствующая цепочка имеет вид $1-8-7-6$.

Следовательно, $E=7,\quad G=6$.

По таблице протяжённость дороги между пунктами $G$ и $E$ равна протяжённости дороги между пунктами $6$ и $7$: $21$ км.

Протяжённость дороги между пунктами $D$ и $F$ равна протяжённости дороги между пунктами $4$ и $8$: $53$ км.

$21+53=74$.

На графе из пунктов Б и Е выходит по одной дороге, из пунктов А и Д — по две дороги, из пунктов Г и К — по три дороги, из пункта В — четыре дороги.

В таблице пункты $5$ и $6$ имеют по одной дороге, пункты $3$ и $7$ — по две дороги, пункты $1$ и $2$ — по три дороги, пункт $4$ — четыре дороги.

Следовательно, $В=4$.

Пункт А имеет две дороги и соединён с пунктом В, имеющим четыре дороги. В таблице из пунктов степени $2$ с пунктом $4$ соединён пункт $3$. Поэтому $А=3$.

Тогда оставшемуся пункту степени $2$ соответствует пункт Д: $Д=7$.

Пункт Д соединён с пунктами Г и К. В таблице пункт $7$ соединён с пунктами $1$ и $2$.

Пункт К, в отличие от пункта Г, соединён с пунктом В. В таблице из пунктов $1$ и $2$ с пунктом $4$ соединён пункт $2$. Следовательно, $К=2,\quad Г=1$.

Таким образом, дороге Д–К соответствует дорога между пунктами $7$ и $2$. В таблице её протяжённость равна $10$ км.

На графе из пунктов $A$, $B$ и $D$ выходят по две дороги, а из пунктов $C$, $E$, $F$ и $G$ — по три дороги.

В таблице по две дороги выходят из пунктов $1$, $5$ и $6$, а по три дороги — из пунктов $2$, $3$, $4$ и $7$.

На графе пункты $B$ и $D$ — соседние вершины, имеющие по две дороги. В таблице из вершин степени $2$ соединены между собой только пункты $1$ и $6$. Следовательно, ${B,D}={1,6}$.

Оставшейся вершине степени $2$ соответствует пункт $A$: $A=5$.

Пункт $A$ соединён с пунктами $C$ и $E$. В таблице пункт $5$ соединён с пунктами $3$ и $7$. Значит, ${C,E}={3,7}$.

Пункт $E$ соединён только с одной вершиной степени $3$ — пунктом $F$. Пункт $C$ соединён с двумя вершинами степени $3$ — пунктами $F$ и $G$.

В таблице пункт $3$ соединён только с одной вершиной степени $3$ — пунктом $4$, а пункт $7$ соединён с двумя вершинами степени $3$ — пунктами $2$ и $4$. Поэтому $E=3,\quad C=7,\quad F=4$.

Таким образом, дороге $C\text{–}F$ соответствует дорога между пунктами $7$ и $4$. Её протяжённость равна $39$ км.

Дороге $A\text{–}E$ соответствует дорога между пунктами $5$ и $3$. Её протяжённость равна $21$ км.

$39+21=60$.

На графе из пунктов А, Е, Ж и К выходят по две дороги, а из пунктов Б, В, Г и Д — по три дороги.

В таблице по две дороги выходят из пунктов $2$, $3$, $4$ и $6$, а по три дороги — из пунктов $1$, $5$, $7$ и $8$.

Пункт Е соединён с двумя вершинами степени $3$ — пунктами Д и Б, которые также соединены друг с другом.

В таблице этому условию соответствует пункт $2$: он соединён с пунктами $7$ и $8$, причём между пунктами $7$ и $8$ тоже есть дорога. Следовательно, $Е=2$.

Пункт А соединён с двумя вершинами степени $3$, которые не соединены между собой. В таблице этому условию соответствует пункт $4$, соединённый с пунктами $5$ и $7$. Значит, $А=4$.

Пункт Д соединён с пунктами Е, Б и А. Так как $Е=2$ и $А=4$, пункту Д соответствует номер $7$: $Д=7$.

Тогда пункту Б соответствует номер $8$.

Пункт Б соединён с пунктами Е, Д и В. В таблице пункт $8$ соединён с пунктами $2$, $7$ и $1$. Следовательно, $В=1$.

Таким образом, $Е=2,\quad В=1$.

Сопоставим вершины графа с номерами пунктов в таблице по количеству выходящих из них дорог.

На графе:

• из пунктов А, Б, Д и К выходят по две дороги;
• из пункта Г выходят три дороги;
• из пункта Е выходят четыре дороги;
• из пункта В выходят пять дорог.

В таблице:

• пункты $1$, $3$, $5$ и $7$ имеют по две дороги;
• пункт $2$ имеет три дороги;
• пункт $4$ имеет четыре дороги;
• пункт $6$ имеет пять дорог.

Следовательно, $В=6,\quad Г=2,\quad Е=4$.

Пункт Е соединён с пунктами В, Г, Д и К. В таблице пункт $4$ соединён с пунктами $6$, $2$, $7$ и $1$.

Пункт Д, в отличие от пункта К, соединён также с пунктом В. Из пунктов $1$ и $7$ только пункт $7$ соединён с пунктом $6$. Поэтому $Д=7,\quad К=1$.

Таким образом, дороге К–Е соответствует дорога между пунктами $1$ и $4$. В таблице её длина равна $10$ км.

Сопоставим вершины графа с пунктами таблицы по количеству выходящих из них дорог.

На графе:

• из пунктов Б, Е и К выходит по одной дороге;
• из пункта Д выходят две дороги;
• из пункта А выходят три дороги;
• из пунктов В и Г выходят по четыре дороги.

В таблице:

• пункты П2, П5 и П6 имеют по одной дороге;
• пункт П7 имеет две дороги;
• пункт П3 имеет три дороги;
• пункты П1 и П4 имеют по четыре дороги.

Следовательно, $А=\text{П3},\quad Д=\text{П7}$, а пунктам В и Г соответствуют П1 и П4.

Пункт Д соединён с пунктами А и Г. В таблице П7 соединён с П3 и П4. Так как $А=\text{П3}$, получаем: $Г=\text{П4}$.

Следовательно, $В=\text{П1}$.

Дороге А–В соответствует дорога между пунктами П3 и П1. В таблице её протяжённость равна $15$ км.