Теория:
Задача №1
В таблице приведены расстояния между четырьмя посёлками. Если пересечение строки и столбца пусто, то между посёлками дороги нет. Изобразите схематически приведённую дорожную систему. С помощью графа определите кратчайший путь из посёлка А в D.
Поставим произвольно точки по количеству вершин: A, B, C, D.
Соединим указанные точки линиями и подпишем числовые значения. Желательно, чтобы линии (рёбра) в графе не пересекались.
Из А в D существуют два пути:
A — B — C — D = \(2\) + \(4\) + \(5\) = \(11\)
A — B — D = \(2\) + \(8\) = \(10\) — кратчайший путь из А в D.
Задача №2
Сколько существует трёхзначных чисел, составленных из цифр \(5\), \(6\), \(7\), при условии, что каждая цифра используется только один раз?
Для решения задачи составим граф.
Получим следующие числа: \(567\), \(576\), \(657\), \(675\), \(756\), \(765\). Всего \(6\) чисел.
Источники:
Изображения ©ЯКласс