Задание 1

Для решения этой задачи необходимо сопоставить таблицу с графом и найти кратчайший путь между пунктами D и G.

1. Анализ графа и таблицы:

   • Определим количество дорог, выходящих из каждого пункта графа:
     • A: 2 дороги
     • B: 3 дороги
     • C: 2 дороги
     • D: 2 дороги
     • E: 1 дорога
     • F: 2 дороги
     • G: 1 дорога
   • Найдем пункты в таблице, у которых 2 дороги:
     • П1: 2 дороги (П2, П7)
     • П2: 2 дороги (П1, П7)
     • П4: 1 дорога (П6)
     • П5: 3 дороги (П3, П6, П7)
     • П6: 3 дороги (П3, П4, П5)
     • П7: 3 дороги (П1, П2, П5)
   • Следовательно, пункты A, C, D, F соответствуют П1, П2, П3, П4, П5, П6, П7. Пункты B, П5, П6, П7 имеют по 3 дороги, а E и G по одной.

2. Сопоставление графа и таблицы:

   • Посмотрим на таблицу и граф. У D и G по 1 соседу с 3 дорогами. В таблице это П5, П6, П7. D соединен с C и B. G соединен с B.
   • Посмотрим на таблицу. У П4 один сосед - П6. Значит П4 = E или G. Но у G один сосед с 3 дорогами, а у E нет. Значит П4 = E, а G = П7.
   • Тогда D = П3, так как у П3 один сосед с 3 дорогами (П5, П6, П7).
   • B = П5 или П6. C = П1 или П2. A = П2 или П1. F = П6 или П5.

3. Определение длин дорог:

   • Длина пути D-G: D=П3, G=П7. Длина пути П3-П7 = П3-П5-П7 или П3-П6-П7.
   • П3-П5 = 9, П5-П7 = 5. Итого 9+5 = 14.
   • П3-П6 = 12, П6-П7 = нет пути. Значит этот путь не подходит.
   • Длина пути D-B-G: D=П3, G=П7. B = П5 или П6.
   • Если B = П5, то П3-П5 = 9, П5-П7 = 5. Итого 9+5 = 14.
   • Если B = П6, то П3-П6 = 12, П6-П7 = нет пути. Значит этот путь не подходит.

4. Вывод:

   • Длина пути D-G = 14.

Ответ: 14