Задание №1 — Анализ матрицы смежности

Решение:

Степени вершин схемы: А — 3, Б — 2, В — 3, Г — 3, Д — 2, Е — 3, К — 3, Л — 2, М — 3.

Число заполненных клеток в строках таблицы: 1 — 3, 2 — 3, 3 — 3, 4 — 3, 5 — 2, 6 — 2, 7 — 3, 8 — 2, 9 — 3.

Степень 2 имеют три вершины схемы — Б, Д и Л — и три пункта таблицы — 5, 6 и 8. Различим их так: Б лежит в треугольнике А—Б—К, Л лежит в треугольнике В—Л—М, а вот соседи Д (это Г и Е) между собой дорогой не соединены.

Проверяем в таблице:

• соседи пункта 6 — это 1 и 7, между ними есть дорога (12), значит, это треугольник;
• соседи пункта 8 — это 3 и 9, между ними есть дорога (33), значит, это тоже треугольник;
• соседи пункта 5 — это 2 и 4, клетка 2—4 пуста, значит, Д = 5.

Итак, тройки {1, 6, 7} и {3, 8, 9} отвечают тройкам {А, Б, К} и {В, Л, М} (в каком порядке — неважно). Дороги А—К и В—М — это как раз стороны этих треугольников, лежащие против вершин Б и Л, то есть дороги 1—7 и 3—9.

Их длины: 1—7 = 12 и 3—9 = 33.

Сумма: 12 + 33 = 45.

Ответ: 45